×

The parameterised complexity of list problems on graphs of bounded treewidth. (English) Zbl 1353.68134

Summary: 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 W[1]-hard, even parameterised by pathwidth. These results resolve two open questions of M. R. Fellows et al. [Inf. Comput. 209, No. 2, 143–153 (2011; Zbl 1223.05070)].

MSC:

68Q25 Analysis of algorithms and problem complexity
05C15 Coloring of graphs and hypergraphs

Citations:

Zbl 1223.05070
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Noga, Alon, Restricted colorings of graphs, (Walker, K., Surveys in Combinatorics, 1993, Proceedings, 14th British Combinatorial Conference. Surveys in Combinatorics, 1993, Proceedings, 14th British Combinatorial Conference, London Mathematical Society Lecture Note Series, vol. 187 (1993), Cambridge University Press), 1-33 · Zbl 0791.05034
[2] Arnborg, Stefan; Proskurowski, Andrzej, Linear time algorithms for NP-hard problems restricted to partial \(k\)-trees, Discrete Appl. Math., 23, 11-24 (1989) · Zbl 0666.68067
[3] Behzad, M., Graphs and their chromatic numbers (1965), Michigan State University, Ph.D. thesis
[4] Bodlaender, Hans L., A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput., 25, 6, 1305-1317 (1996) · Zbl 0864.68074
[5] Bollobás, B.; Harris, A., List-colourings of graphs, Graphs Comb., 1, 115-127 (1985) · Zbl 0606.05027
[6] Borie, Richard B.; Parker, R. Gary; Tovey, Craig A., Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families, Algorithmica, 7, 555-581 (1992) · Zbl 0753.05062
[7] Borodin, O. V.; Kostochka, A. V.; Woodall, D. R., List edge and list total colourings of multigraphs, J. Comb. Theory, Ser. B, 71, 2, 184-204 (1997) · Zbl 0876.05032
[8] Bruhn, Henning; Lang, Richard; Stein, Maya, List edge-coloring and total coloring in graphs of low treewidth, J. Graph Theory, 81, 3, 272-282 (2016) · Zbl 1339.05114
[9] Chen, Jianer; Chor, Benny; Fellows, Mike; Huang, Xiuzhen; Juedes, David; Kanj, Iyad A.; Xia, Ge, Tight lower bounds for certain parameterized NP-hard problems, Inf. Comput., 201, 2, 216-231 (2005) · Zbl 1161.68476
[10] Courcelle, B., The monadic second-order logic of graphs I: recognizable sets of finite graphs, Inf. Comput., 85, 12-75 (1990) · Zbl 0722.03008
[11] Cǎlinescu, Gruia; Fernandes, Cristina G.; Reed, Bruce, Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width, J. Algorithms, 48, 333-359 (2003) · Zbl 1079.68069
[12] Downey, Rodney G.; Fellows, Michael R., Fundamentals of Parameterized Complexity, Texts in Computer Science (2013), Springer · Zbl 1358.68006
[13] Fellows, M.; Hermelin, D.; Rosamond, F.; Vialette, S., On the fixed-parameter intractability and tractability of multiple-interval graph properties, Theor. Comput. Sci., 410, 53-61 (2009)
[14] Fellows, Michael R.; Fomin, Fedor V.; Lokshtanov, Daniel; Rosamond, Frances; Saurabh, Saket; Szeider, Stefan; Thomassen, Carsten, On the complexity of some colorful problems parameterized by treewidth, Inf. Comput., 209, 143-153 (2011) · Zbl 1223.05070
[15] Flum, J.; Grohe, M., Parameterized Complexity Theory (2006), Springer
[16] Galvin, F., The list chromatic index of a bipartite multigraph, J. Comb. Theory, Ser. B, 63, 1, 153-158 (1995) · Zbl 0826.05026
[17] Garey, M. R.; Johnson, D. S.; Tarjan, R. Endre, The planar Hamilton circuit problem is NP-complete, SIAM J. Comput., 5, 704-714 (1976) · Zbl 0346.05110
[18] Häggkvist, Roland; Chetwynd, Amanda, Some upper bounds on the total and list chromatic numbers of multigraphs, J. Graph Theory, 16, 5, 503-516 (1992) · Zbl 0814.05038
[19] Holyer, Ian, The NP-completeness of edge-coloring, SIAM J. Comput., 10, 4, 718-720 (1981) · Zbl 0473.68034
[20] Isobe, Shuji; Zhou, Xiao; Nishizeki, Takao, Total colourings of degenerate graphs, Combinatorica, 27, 2, 167-182 (2007) · Zbl 1164.05024
[21] Jansen, Klaus; Scheffler, Petra, Generalized coloring for tree-like graphs, Discrete Appl. Math., 75, 135-155 (1997) · Zbl 0879.68076
[22] Kahn, Jeff, Asymptotics of the chromatic index for multigraphs, J. Comb. Theory, Ser. B, 68, 2, 233-254 (1996) · Zbl 0861.05026
[23] Krishnamoorthy, M. S., An NP-hard problem in bipartite graphs, SIGACT News, 7, 26 (1975)
[24] Leven, Daniel; Galil, Zvi, NP completeness of finding the chromatic index of regular graphs, J. Algorithms, 4, 1, 35-44 (1983) · Zbl 0509.68037
[25] Lokshtanov, Daniel; Marx, Dániel; Saurabh, Saket, Lower bounds based on the exponential time hypothesis, Bull. Eur. Assoc. Theor. Comput. Sci., 3, 105 (2013) · Zbl 1258.68068
[26] Marx, Dániel, NP-completeness of list coloring and precoloring extension on the edges of planar graphs, J. Graph Theory, 49, 313-324 (2005) · Zbl 1068.05024
[27] McDiarmid, Colin J. H.; Sánchez-Arroyo, Abdón, Total colouring regular bipartite graphs is NP-hard, Discrete Math., 124, 1-3, 155-162 (1994) · Zbl 0791.05042
[28] Seese, D., Tree-partite graphs and the complexity of algorithms, (Budach, Lothar, Fundamentals of Computation Theory. Fundamentals of Computation Theory, Lecture Notes in Computer Science, vol. 199 (1985), Springer: Springer Berlin/Heidelberg), 412-421 · Zbl 0574.68036
[29] Vizing, V. G., On an estimate of the chromatic class of a \(p\)-graph, Diskretn. Anal., 3, 25-30 (1964), (in Russian)
[30] Vizing, V. G., Some unsolved problems in graph theory, Usp. Mat. Nauk, 23, 117-134 (1968), (in Russian) · Zbl 0177.52301
[31] Zhou, Xiao; Matsuo, Yuki; Nishizeki, Takao, List total colorings of series-parallel graphs, J. Discret. Algorithms, 3, 47-60 (2005) · Zbl 1105.68090
[32] Zhou, Xiao; Nakano, Shin-ichi; Nishizeki, Takao, Edge-colouring partial \(k\)-trees, J. Algorithms, 21, 598-617 (1996) · Zbl 0864.68071
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.