Computability in Europe 2006
Logical Approaches to Computational Barriers
|Author(s):||Barnaby Martin and Florent Madelaine|
|Slot:||Tue, 11:10-11:30, Faraday J (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||
Warning: date(): It is not safe to rely on the system's timezone settings. You are *required* to use the date.timezone setting or the date_default_timezone_set() function. In case you used any of those methods and you are still getting this warning, you most likely misspelled the timezone identifier. We selected the timezone 'UTC' for now, but please set date.timezone to select your timezone. in /srv/www/htdocs-cs/cie06/conf-code.php on line 135