Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871709 | Discrete Applied Mathematics | 2018 | 9 Pages |
Abstract
A graph G=(V,E) is Cprobe if V can be partitioned into two sets, probesP and non-probesN, where N is independent and new edges may be added between non-probes such that the resulting graph is in the graph class C. We say that (N,P) is a Cprobe partition for G. The Cpartitioned probe problem consists of an input graph G with a vertex partition (N,P) and the question: Is (N,P) a C probe partition for G? A (k,â)-partition of a graph G is a partition of its vertex set into at most k independent sets and â cliques. A graph is (k,â) if it has a (k,â)-partition. We prove that the Cpartitioned probe problem is polynomial for (1,2) and for (2,1)-graphs, and NP-complete for (2,2)-graphs. The results give the first graph class for which the partitioned probe problem is NP-complete, and the full complexity dichotomy into NP-complete and polynomial for (k,â)partitioned probe problems: they are NP-complete if k2+â2â¥8, and polynomial otherwise.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Simone Dantas, Luerbio Faria, Celina M.H. de Figueiredo, Rafael B. Teixeira,