Deprecated: Function split() is deprecated in /srv/www/htdocs-cs/cie06/db-code.php on line 73

Deprecated: Function split() is deprecated in /srv/www/htdocs-cs/cie06/db-code.php on line 80
CiE 2006 - Regular Talk: - Towards a trichotomy for quantified H-coloring.
Computability in Europe 2006
Logical Approaches to Computational Barriers

Print current page  Print this page

Regular Talk:
Towards a trichotomy for quantified H-coloring.


Deprecated: Function split() is deprecated in /srv/www/htdocs-cs/cie06/db-code.php on line 249
Speaker: Barnaby Martin
Author(s): Barnaby Martin and Florent Madelaine
Presentation: CiE2006_Talk.pdf
Slot: Tue, 11:10-11:30, Faraday J (col. 5)

Abstract

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
2006-04-23 Valid HTML 4.01! Valid CSS! eXTReMe Tracker hit counters by www.free-counters.net