A well-known consequence of Brooks’ Theorem is that 3-Colouring, a.k.a. \(\textrm{CSP}(K_3)\) , is solvable in polynomial time for subcubic graphs. We begin our investigation by observing that \(\textrm{QCSP}(K_3)\) , a.k.a. Quantified 3-Colouring, is Pspace-complete on subcubic planar graphs. This allows us to give a complexity classification for bounded alternation \(\varSigma _{i}\) - \(\textrm{QCSP}(K_3)\) ( \(i\ge 3\) , odd) for \(\mathcal {H}\) -topological-minor-free graphs. For all such (maybe infinite) sets \(\mathcal {H}\) , we delineate between those for which \(\varSigma _{i}\) - \(\textrm{QCSP}(K_3)\) is solvable in polynomial time, and those for which it is \(\varSigma _{i-2}^{\textrm{P}}\) -hard. We continue our investigation of \(\textrm{QCSP}(K_3)\) on \(\mathcal {H}\) -subgraph-free graphs, contrasting with both \(\textrm{CSP}(K_3)\) , as well as the recently introduced C123-framework of [10]. Next, we turn our attention to \(P_5\) - and \(P_4\) -free graphs. We prove that \(\textrm{QCSP}(H)\) is in \(\textrm{NP}\) , for all finite graphs H, when the input is restricted to \(P_5\) -free graphs. For \(\textrm{QCSP}(K_3)\) , on \(P_4\) -free graphs, we are able to improve this to a polynomial time algorithm. Finally, we propose a certain template, the line graph of a subdivided star \(L(K^r_{1,4})\) , so that \(\textrm{QCSP}(L(K^r_{1,4}))\) behaves curiously on \(P_m\) -free graphs. When m is small, this problem is solvable in polynomial time. For some medium m, it is \(\textrm{NP}\) -complete, while for large enough m, it is Pspace-complete.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Quantified Colouring and H-Free Algorithmics

  • Kristina Asimi,
  • Tala Eagling-Vose,
  • Santiago Guzmán-Pro,
  • Barnaby Martin,
  • Yiming Qiu

摘要

A well-known consequence of Brooks’ Theorem is that 3-Colouring, a.k.a. \(\textrm{CSP}(K_3)\) , is solvable in polynomial time for subcubic graphs. We begin our investigation by observing that \(\textrm{QCSP}(K_3)\) , a.k.a. Quantified 3-Colouring, is Pspace-complete on subcubic planar graphs. This allows us to give a complexity classification for bounded alternation \(\varSigma _{i}\) - \(\textrm{QCSP}(K_3)\) ( \(i\ge 3\) , odd) for \(\mathcal {H}\) -topological-minor-free graphs. For all such (maybe infinite) sets \(\mathcal {H}\) , we delineate between those for which \(\varSigma _{i}\) - \(\textrm{QCSP}(K_3)\) is solvable in polynomial time, and those for which it is \(\varSigma _{i-2}^{\textrm{P}}\) -hard. We continue our investigation of \(\textrm{QCSP}(K_3)\) on \(\mathcal {H}\) -subgraph-free graphs, contrasting with both \(\textrm{CSP}(K_3)\) , as well as the recently introduced C123-framework of [10]. Next, we turn our attention to \(P_5\) - and \(P_4\) -free graphs. We prove that \(\textrm{QCSP}(H)\) is in \(\textrm{NP}\) , for all finite graphs H, when the input is restricted to \(P_5\) -free graphs. For \(\textrm{QCSP}(K_3)\) , on \(P_4\) -free graphs, we are able to improve this to a polynomial time algorithm. Finally, we propose a certain template, the line graph of a subdivided star \(L(K^r_{1,4})\) , so that \(\textrm{QCSP}(L(K^r_{1,4}))\) behaves curiously on \(P_m\) -free graphs. When m is small, this problem is solvable in polynomial time. For some medium m, it is \(\textrm{NP}\) -complete, while for large enough m, it is Pspace-complete.