The parameterised complexity of list problems on graphs of bounded treewidth

被引：4
|
作者：
Meeks, Kitty [1 ,2 ]
Scott, Alexander [1 ]
机构：
[1] Univ Oxford, Math Inst, Radcliffe Observ Quarter, Andrew Wiles Bldg,Woodstock Rd, Oxford OX2 6GG, England
[2] Univ Glasgow, Sch Math & Stat, 15 Univ Gardens, Glasgow G12 8QW, Lanark, Scotland
来源：
INFORMATION AND COMPUTATION | 2016年 / 251卷
关键词：
Parameterised complexity; Bounded treewidth; Graph colouring; List colouring; Hamilton path; NP-COMPLETENESS; CHROMATIC INDEX; TOTAL COLORINGS; EDGE;
D O I：
10.1016/j.ic.2016.08.001
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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 Fellows, Fomin, Lokshtanov, Rosamond, Saurabh, Szeider and Thomassen (2011). (C) 2016 Elsevier Inc. All rights reserved.
引用
收藏
页码：91 / 103
页数：13
相关论文
共 50 条
  • [31] Learning Bounded Treewidth Bayesian Networks
    Elidan, Gal
    Gould, Stephen
    JOURNAL OF MACHINE LEARNING RESEARCH, 2008, 9 : 2699 - 2731
  • [32] The complexity of dissociation set problems in graphs
    Orlovich, Yury
    Dolgui, Alexandre
    Finke, Gerd
    Gordon, Valery
    Werner, Frank
    DISCRETE APPLIED MATHEMATICS, 2011, 159 (13) : 1352 - 1366
  • [33] The Complexity of Ontology-Based Data Access with OWL2QL and Bounded Treewidth Queries
    Bienvenu, Meghyn
    Kikot, Stanislav
    Kontchakov, Roman
    Podolskii, Vladimir V.
    Ryzhikov, Vladislav
    Zakharyaschev, Michael
    PODS'17: PROCEEDINGS OF THE 36TH ACM SIGMOD-SIGACT-SIGAI SYMPOSIUM ON PRINCIPLES OF DATABASE SYSTEMS, 2017, : 201 - 216
  • [34] Filling the complexity gaps for colouring planar and bounded degree graphs
    Dabrowski, Konrad K.
    Dross, Francois
    Johnson, Matthew
    Paulusma, Daniel
    JOURNAL OF GRAPH THEORY, 2019, 92 (04) : 377 - 393
  • [35] Parameterised temporal exploration problems
    Erlebach, Thomas
    Spooner, Jakob T.
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2023, 135 : 73 - 88
  • [36] Parameterised Enumeration for Modification Problems
    Creignou, Nadia
    Ktari, Raida
    Meier, Arne
    Mueller, Julian-Steffen
    Olive, Frederic
    Vollmer, Heribert
    ALGORITHMS, 2019, 12 (09)
  • [37] Domination chain: Characterisation, classical complexity, parameterised complexity and approximability
    Bazgan, Cristina
    Brankovic, Ljiljana
    Casel, Katrin
    Fernau, Henning
    DISCRETE APPLIED MATHEMATICS, 2020, 280 : 23 - 42
  • [38] More results on the complexity of identifying problems in graphs
    Hudry, Olivier
    Lobstein, Antoine
    THEORETICAL COMPUTER SCIENCE, 2016, 626 : 1 - 12
  • [39] Improved Steiner tree algorithms for bounded treewidth
    Chimani, Markus
    Mutzel, Petra
    Zey, Bernd
    JOURNAL OF DISCRETE ALGORITHMS, 2012, 16 : 67 - 78
  • [40] Scheduling a Pipelined Operator Graph of Bounded Treewidth
    Li, Shuguang
    Xin, Xiao
    MATERIALS, MECHATRONICS AND AUTOMATION, PTS 1-3, 2011, 467-469 : 1102 - +
12345