首页    期刊浏览 2024年11月30日 星期六
登录注册

文章基本信息

  • 标题:Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters
  • 本地全文:下载
  • 作者:Tatsuhiko Hatanaka ; Takehiro Ito ; Xiao Zhou
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2017
  • 卷号:83
  • 页码:51:1-51:13
  • DOI:10.4230/LIPIcs.MFCS.2017.51
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:Let G be a graph such that each vertex has its list of available colors, and assume that each list is a subset of the common set consisting of k colors. For two given list colorings of G, we study the problem of transforming one into the other by changing only one vertex color assignment at a time, while at all times maintaining a list coloring. This problem is known to be PSPACE-complete even for bounded bandwidth graphs and a fixed constant k. In this paper, we study the fixed-parameter tractability of the problem when parameterized by several graph parameters. We first give a fixed-parameter algorithm for the problem when parameterized by k and the modular-width of an input graph. We next give a fixed-parameter algorithm for the shortest variant which computes the length of a shortest transformation when parameterized by k and the size of a minimum vertex cover of an input graph. As corollaries, we show that the problem for cographs and the shortest variant for split graphs are fixed-parameter tractable even when only k is taken as a parameter. On the other hand, we prove that the problem is W[1]-hard when parameterized only by the size of a minimum vertex cover of an input graph.
  • 关键词:combinatorial reconfiguration; fixed-parameter tractability; graph algorithm; list coloring; W[1]-hardness
国家哲学社会科学文献中心版权所有