Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Greedy algorithms, H-colourings and a complexity-theoretic dichotomy.

Puricella, A. and Stewart, I. A. (2003) 'Greedy algorithms, H-colourings and a complexity-theoretic dichotomy.', Theoretical computer science., 290 (3). pp. 1897-1913.

Abstract

Let H be a fixed undirected graph. An H-colouring of an undirected graph G is a homomorphism from G to H. If the vertices of G are partially ordered then there is a generic non-deterministic greedy algorithm which computes all lexicographically first maximal H-colourable subgraphs of G. We show that the complexity of deciding whether a given vertex of G is in a lexicographically first maximal H-colourable subgraph of G is NP-complete, if H is bipartite, and ${\bf \Sigma}_2^p$-complete, if H is non-bipartite. This result complements Hell and Nesetril's seminal dichotomy result that the standard H-colouring problem is in P, if H is bipartite, and NP-complete, if H is non-bipartite. Our proofs use the basic techniques established by Hell and Nesetril, combinatorially adapted to our scenario.

Item Type:Article
Keywords:Computational complexity, Constraint satisfaction, Graph algorithms, Dicotomies.
Full text:PDF - Accepted Version (258Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1016/S0304-3975(02)00329-8
Record Created:10 Oct 2008
Last Modified:14 Jun 2011 16:31

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library