Name
Abstract | ||
|---|---|---|
A graph G = ( V , E ) is C probe if V can be partitioned into two sets, probes P and non-probes N, 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 C probe partition for G. The C unpartitioned probe problem consists of an input graph G and the question: Is G a C probe graph? 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 the full complexity dichotomy into NP-complete and polynomial for ( k , ¿ ) unpartitioned probe problems: they are NP-complete if k + ¿ ¿ 3 , and polynomial otherwise. This gives the first examples of graph classes C that can be recognized in polynomial time but whose probe graph classes are NP-complete. We prove the full complexity dichotomy into NP-complete and polynomial for ( k , ¿ ) unpartitioned probe problems.The established full complexity dichotomy answers negatively the SPGC conjecture of Le and Ridder, published in WG 2007.The established full complexity dichotomy answers a question of Chang, Hung and Rossmanith, published in DAM 2013. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.ipl.2015.11.004 | Information Processing Letters |
Keywords | Field | DocType |
Probe graphs,Partition problems,Graph algorithms | Discrete mathematics,Combinatorics,Graph power,Cubic graph,Integral graph,Factor-critical graph,Distance-regular graph,Graph minor,Mathematics,Voltage graph,Complement graph | Journal |
Volume | Issue | ISSN |
116 | 4 | 0020-0190 |
Citations | PageRank | References |
0 | 0.34 | 8 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Simone Dantas | 1 | 119 | 24.99 |
| Luérbio Faria | 2 | 5 | 3.53 |
| Celina M. H. de Figueiredo | 3 | 296 | 38.49 |
| Rafael B. Teixeira | 4 | 49 | 5.31 |