Connected coloring completion for general graphs: Algorithms and complexity

Chor, Benny, Fellows, Michael, Ragan, Mark, Razgon, Igor, Rosamond, Frances and Snir, Sagi (2007). Connected coloring completion for general graphs: Algorithms and complexity. In: G. Lin, Computing and Combinatorics (COCOON 2007). 13th Annual International Computing and Combinatorics Conference (COCOON 2007), Banff, Alberta, Canada, (75-85). 16-19 July 2007. doi:10.1007/978-3-540-73545-8_10

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads

Author Chor, Benny
Fellows, Michael
Ragan, Mark
Razgon, Igor
Rosamond, Frances
Snir, Sagi
Title of paper Connected coloring completion for general graphs: Algorithms and complexity
Conference name 13th Annual International Computing and Combinatorics Conference (COCOON 2007)
Conference location Banff, Alberta, Canada
Conference dates 16-19 July 2007
Convener University of Alberta
Proceedings title Computing and Combinatorics (COCOON 2007)   Check publisher's open access policy
Journal name Lecture Notes in Computer Science   Check publisher's open access policy
Place of Publication Berlin, Germany
Publisher Springer
Publication Year 2007
Sub-type Fully published paper
DOI 10.1007/978-3-540-73545-8_10
ISBN 9783540735441
ISSN 0302-9743
Editor G. Lin
Volume 4598
Start page 75
End page 85
Total pages 11
Language eng
Abstract/Summary An r-component connected coloring of a graph is a coloring of the vertices so that each color class induces a subgraph having at most r connected components. The concept has been well-studied for r = 1, in the case of trees, under the rubric of convex coloring, used in modeling perfect phylogenies. Several applications in bioinformatics of connected coloring problems on general graphs are discussed, including analysis of protein-protein interaction networks and protein structure graphs, and of phylogenetic relationships modeled by splits trees. We investigate the r-Component Connected Coloring Completion (r-CCC) problem, that takes as input a partially colored graph, having k uncolored vertices, and asks whether the partial coloring can be completed to an r-component connected coloring. For r = 1 this problem is shown to be NP-hard, but fixed-parameter tractable when parameterized by the number of uncolored vertices, solvable in time O *(8 k ). We also show that the 1-CCC problem, parameterized (only) by the treewidth t of the graph, is fixed-parameter tractable; we show this by a method that is of independent interest. The r-CCC problem is shown to be W[1]-hard, when parameterized by the treewidth bound t, for any r ≥ 2. Our proof also shows that the problem is NP-complete for r = 2, for general graphs.
Subjects 080201 Analysis of Algorithms and Complexity
Keyword Algorithms
Q-Index Code E1
Q-Index Status Provisional Code
Institutional Status UQ
Additional Notes Proceedings published in 'Lecture Notes in Computer Science' Book series.

Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 10 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 0 times in Scopus Article
Google Scholar Search Google Scholar
Created: Tue, 10 Mar 2009, 10:52:02 EST by Gina Velli on behalf of Institute for Molecular Bioscience