Logical Approaches to Computational Barriers

Towards a trichotomy for quantified H-coloring.

Speaker:
| Barnaby Martin |

Author(s): |
Barnaby Martin and Florent Madelaine |

Slot: |
Array, 11:10-11:30, col. 5 |

Hell and Nesetril proved that the H-colouring problem is NP-complete if, and only if, H is bipartite. In this paper, we investigate the complexity of the quantified H-colouring problem (a restriction of the quantified constraint satisfaction problem to undirected graphs). We introduce this problem using a new two player colouring game. We prove that the quantified H-colouring problem is: tractable, if H is bipartite; NP-complete, if H is not bipartite and not connected; and Pspace-complete, if H is connected and has a unique cycle, which is of odd length. We conjecture that the last case extends to all non-bipartite connected graphs.

websites: Arnold Beckmann | 2006-04-23 |