research-article

The parameterised complexity of list problems on graphs of bounded treewidth

Authors:

Alexander ScottAuthors Info & Claims

Information and Computation, Volume 251, Issue C

Pages 91 - 103

https://doi.org/10.1016/j.ic.2016.08.001

Published: 01 December 2016 Publication History

Abstract

We consider the parameterised complexity of several list problems on graphs, with parameter treewidth or pathwidth. In particular, we show that List Edge Chromatic Number and List Total Chromatic Number are fixed parameter tractable, parameterised by treewidth, whereas List Hamilton Path is W1-hard, even parameterised by pathwidth. These results resolve two open questions of Fellows, Fomin, Lokshtanov, Rosamond, Saurabh, Szeider and Thomassen (2011).

References

[1]

Alon Noga, Restricted colorings of graphs, in: London Mathematical Society Lecture Note Series, vol. 187, Cambridge University Press, 1993, pp. 1-33.

Digital Library

[2]

Stefan Arnborg, Andrzej Proskurowski, Linear time algorithms for NP-hard problems restricted to partial k-trees, Discrete Appl. Math., 23 (1989) 11-24.

Digital Library

[3]

M. Behzad, Graphs and their chromatic numbers, Michigan State University, 1965.

[4]

Hans L. Bodlaender, A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput., 25 (1996) 1305-1317.

Digital Library

[5]

B. Bollobás, A. Harris, List-colourings of graphs, Graphs Comb., 1 (1985) 115-127.

Digital Library

[6]

Richard B. Borie, R. Gary Parker, Craig A. Tovey, Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families, Algorithmica, 7 (1992) 555-581.

Digital Library

[7]

O.V. Borodin, A.V. Kostochka, D.R. Woodall, List edge and list total colourings of multigraphs, J. Comb. Theory, Ser. B, 71 (1997) 184-204.

Digital Library

[8]

Henning Bruhn, Richard Lang, Maya Stein, List edge-coloring and total coloring in graphs of low treewidth, J. Graph Theory, 81 (2016) 272-282.

Digital Library

[9]

Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David Juedes, Iyad A. Kanj, Ge Xia, Tight lower bounds for certain parameterized NP-hard problems, Inf. Comput., 201 (2005) 216-231.

Digital Library

[10]

B. Courcelle, The monadic second-order logic of graphs I: recognizable sets of finite graphs, Inf. Comput., 85 (1990) 12-75.

Digital Library

[11]

Gruia C¿linescu, Cristina G. Fernandes, Bruce Reed, Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width, J. Algorithms, 48 (2003) 333-359.

Digital Library

[12]

Rodney G. Downey, Michael R. Fellows, Fundamentals of Parameterized Complexity, Springer, 2013.

Digital Library

[13]

M. Fellows, D. Hermelin, F. Rosamond, S. Vialette, On the fixed-parameter intractability and tractability of multiple-interval graph properties, Theor. Comput. Sci., 410 (2009) 53-61.

Digital Library

[14]

Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Frances Rosamond, Saket Saurabh, Stefan Szeider, Carsten Thomassen, On the complexity of some colorful problems parameterized by treewidth, Inf. Comput., 209 (2011) 143-153.

Digital Library

[15]

J. Flum, M. Grohe, Parameterized Complexity Theory, Springer, 2006.

Digital Library

[16]

F. Galvin, The list chromatic index of a bipartite multigraph, J. Comb. Theory, Ser. B, 63 (1995) 153-158.

Digital Library

[17]

M.R. Garey, D.S. Johnson, R. Endre Tarjan, The planar Hamilton circuit problem is NP-complete, SIAM J. Comput., 5 (1976) 704-714.

[18]

Roland Häggkvist, Amanda Chetwynd, Some upper bounds on the total and list chromatic numbers of multigraphs, J. Graph Theory, 16 (1992) 503-516.

Digital Library

[19]

Ian Holyer, The NP-completeness of edge-coloring, SIAM J. Comput., 10 (1981) 718-720.

[20]

Shuji Isobe, Xiao Zhou, Takao Nishizeki, Total colourings of degenerate graphs, Combinatorica, 27 (2007) 167-182.

Digital Library

[21]

Klaus Jansen, Petra Scheffler, Generalized coloring for tree-like graphs, Discrete Appl. Math., 75 (1997) 135-155.

Digital Library

[22]

Jeff Kahn, Asymptotics of the chromatic index for multigraphs, J. Comb. Theory, Ser. B, 68 (1996) 233-254.

Digital Library

[23]

M.S. Krishnamoorthy, An NP-hard problem in bipartite graphs, SIGACT News, 7 (1975) 26.

Digital Library

[24]

Daniel Leven, Zvi Galil, NP completeness of finding the chromatic index of regular graphs, J. Algorithms, 4 (1983) 35-44.

[25]

Daniel Lokshtanov, Dániel Marx, Saket Saurabh, Lower bounds based on the exponential time hypothesis, Bull. Eur. Assoc. Theor. Comput. Sci., 3 (2013).

[26]

Dániel Marx, NP-completeness of list coloring and precoloring extension on the edges of planar graphs, J. Graph Theory, 49 (2005) 313-324.

Digital Library

[27]

Colin J.H. McDiarmid, Abdón Sánchez-Arroyo, Total colouring regular bipartite graphs is NP-hard, Discrete Math., 124 (1994) 155-162.

Digital Library

[28]

D. Seese, Tree-partite graphs and the complexity of algorithms, in: Lecture Notes in Computer Science, vol. 199, Springer, Berlin/Heidelberg, 1985, pp. 412-421.

Digital Library

[29]

V.G. Vizing, On an estimate of the chromatic class of a p-graph, Diskretn. Anal., 3 (1964) 25-30.

[30]

V.G. Vizing, Some unsolved problems in graph theory, Usp. Mat. Nauk, 23 (1968) 117-134.

[31]

Xiao Zhou, Yuki Matsuo, Takao Nishizeki, List total colorings of series-parallel graphs, J. Discret. Algorithms, 3 (2005) 47-60.

[32]

Xiao Zhou, Shin-ichi Nakano, Takao Nishizeki, Edge-colouring partial k-trees, J. Algorithms, 21 (1996) 598-617.

Digital Library

Cited By

Chen HLai H(2023)On the Linear Arboricity of Graphs with Treewidth at Most FourGraphs and Combinatorics10.1007/s00373-023-02673-539:4Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1007/s00373-023-02673-5
Gima THanaka TKiyomi MKobayashi YOtachi Y(2022)Exploring the gap between treedepth and vertex cover through vertex integrityTheoretical Computer Science10.1016/j.tcs.2022.03.021918:C(60-76)Online publication date: 29-May-2022
https://dl.acm.org/doi/10.1016/j.tcs.2022.03.021

The parameterised complexity of list problems on graphs of bounded treewidth
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
    2. Graph theory
2. Theory of computation

Recommendations

On the complexity of some colorful problems parameterized by treewidth

In this paper, we study the complexity of several coloring problems on graphs, parameterized by the treewidth of the graph.1.The List Coloring problem takes as input a graph G, together with an assignment to each vertex v of a set of colors C"v. The ...
Tree-coloring problems of bounded treewidth graphs
Abstract
This paper studies the parameterized complexity of the tree-coloring problem and equitable tree-coloring problem. Given a graph $G = (V, E)$ and an integer $r \geq 1$ , we give an FPT algorithm to decide whether there is a tree-r-coloring of graph G when ...
On the Parameterised Complexity of String Morphism Problems

Given a source string u and a target string w, to decide whether w can be obtained by applying a string morphism on u (i. e., uniformly replacing the symbols in u by strings) constitutes an źźźź$\mathcal {NP}$-complete problem. We present a multivariate ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information and Computation

Information and Computation Volume 251, Issue C

December 2016

363 pages

ISSN:0890-5401

Issue’s Table of Contents

Copyright © Elsevier Inc.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 December 2016

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chen HLai H(2023)On the Linear Arboricity of Graphs with Treewidth at Most FourGraphs and Combinatorics10.1007/s00373-023-02673-539:4Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1007/s00373-023-02673-5
Gima THanaka TKiyomi MKobayashi YOtachi Y(2022)Exploring the gap between treedepth and vertex cover through vertex integrityTheoretical Computer Science10.1016/j.tcs.2022.03.021918:C(60-76)Online publication date: 29-May-2022
https://dl.acm.org/doi/10.1016/j.tcs.2022.03.021

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents