Skip to main content

Research Repository

Advanced Search

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

Puricella, A.; Stewart, I.A.

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


Authors

A. Puricella



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.

Citation

Puricella, A., & Stewart, I. (2003). Greedy algorithms, H-colourings and a complexity-theoretic dichotomy. Theoretical Computer Science, 290(3), 1897-1913. https://doi.org/10.1016/s0304-3975%2802%2900329-8

Journal Article Type Article
Publication Date 2003-01
Deposit Date Oct 10, 2008
Publicly Available Date Oct 10, 2008
Journal Theoretical Computer Science
Print ISSN 0304-3975
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 290
Issue 3
Pages 1897-1913
DOI https://doi.org/10.1016/s0304-3975%2802%2900329-8
Keywords Computational complexity, Constraint satisfaction, Graph algorithms, Dicotomies.

Files







You might also like



Downloadable Citations