Parameterized complexity of optimizing list vertex-coloring through reconfiguration
Parameterized complexity of optimizing list vertex-coloring through reconfiguration
复制标题
通过重新配置优化列表顶点着色的参数化复杂度
DOI：
10.1007/978-3-031-27051-2_24
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Yuma Tamura and Xiao Zhou
中科院分区：
文献类型：
--
作者：
Yusuke Yanagisawa;Akira Suzuki;Yuma Tamura and Xiao Zhou
In the combinatorial reconfiguration framework, we study the relationship between two feasible solutions of a combinatorial search problem under a prescribed reconfiguration rule. In this paper, we deal with theOpt-List Coloring Reconfigurationproblem. Given a graphG, a list functionL, a listL-coloring \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f_0$$\end{document} ofGand an integerp,Opt-List Coloring Reconfigurationasks for finding a listL-coloring \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f_\texttt{sol}$$\end{document} ofGsuch that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f_\texttt{sol}$$\end{document} can be transformed from \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f_0$$\end{document} in a step-by-step fashion and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f_\texttt{sol}$$\end{document} uses at mostpcolors. We first observe that the problem remains NP-hard for empty graphs even if every vertex of a given graph has a list of size two. Moreover, we prove that the problem is PSPACE-complete for bipartite graphs with bounded bandwidth and pathwidth two, even if the numberkof colors that can be used in the reconfiguration process is bounded by some constant. On the positive side, we give an FPT algorithm parameterized bykfor graphs of pathwidth one. We also design an FPT algorithm parameterized by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k + \textsf{vc}$$\end{document}, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsf{vc}$$\end{document} is vertex cover number of a given graph.
In the combinatorial reconfiguration framework, we study the relationship between two feasible solutions of a combinatorial search problem under a prescribed reconfiguration rule. In this paper, we deal with theOpt-List Coloring Reconfigurationproblem. Given a graphG, a list functionL, a listL-coloring \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f_0$$\end{document} ofGand an integerp,Opt-List Coloring Reconfigurationasks for finding a listL-coloring \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f_\texttt{sol}$$\end{document} ofGsuch that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f_\texttt{sol}$$\end{document} can be transformed from \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f_0$$\end{document} in a step-by-step fashion and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f_\texttt{sol}$$\end{document} uses at mostpcolors. We first observe that the problem remains NP-hard for empty graphs even if every vertex of a given graph has a list of size two. Moreover, we prove that the problem is PSPACE-complete for bipartite graphs with bounded bandwidth and pathwidth two, even if the numberkof colors that can be used in the reconfiguration process is bounded by some constant. On the positive side, we give an FPT algorithm parameterized bykfor graphs of pathwidth one. We also design an FPT algorithm parameterized by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k + \textsf{vc}$$\end{document}, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsf{vc}$$\end{document} is vertex cover number of a given graph.