论文标题
通过模块化参数的某些图形问题的多项式图纹压缩
Polynomial Turing Compressions for Some Graph Problems Parameterized by Modular-Width
论文作者
论文摘要
用于参数化问题的多项式图灵压缩（PTC）$ l $是一台多项式时间Turing机器，可以访问oracle的问题$ l'$，因此输入参数范围的多项式每个查询都在每个查询中。同时，多项式（多个）压缩（PC）可以被视为PTC的限制变体，其中机器可以准确查询Oracle一次，并且必须输出与Oracle相同的答案。 Bodlaender等。 （ICALP 2008）以及Fortnow and Santhanam（Stoc 2008）在假设conp $ \ not \ subseteq $ np/poly下启动了PC令人印象深刻的硬度理论。由于PTC是PC的概括，因此我们将$ \ MATHCAL {C} $定义为具有PTC但没有PC的所有问题的集合，但在假设conp $ \ not \ subseteq $ np/poly下没有PC。基于PC的硬度理论，Fernau等。 （STACS 2009）在$ \ Mathcal {C} $中发现了第一个问题叶子外（$ k $）。但是，关于$ \ Mathcal {C} $的知之甚少，因为在过去的十年中，只有十二个问题属于复杂性类别。例如，有几个问题是开放的，例如CNF-SAT（$ n $）和$ k $ Path在$ \ Mathcal {C} $中，并且需要新颖的想法来更好地了解PTC和PC之间的基本差异。 在本文中，我们通过表明通过模块化（$ mw $）参数属于$ \ MATHCAL {C} $参数的几个问题来丰富有关$ \ Mathcal {C} $的知识。更具体地说，利用良好研究的结构图参数$ mw $的属性，我们演示了17个由$ mw $参数化的问题是$ \ nathcal {c} $，例如色度数（$ mw $）和汉密尔顿周期（$ mw $）。此外，我们开发了一种一般食谱，以证明针对大量问题的PTC存在，包括我们的17个问题。
A polynomial Turing compression (PTC) for a parameterized problem $L$ is a polynomial time Turing machine that has access to an oracle for a problem $L'$ such that a polynomial in the input parameter bounds each query. Meanwhile, a polynomial (many-one) compression (PC) can be regarded as a restricted variant of PTC where the machine can query the oracle exactly once and must output the same answer as the oracle. Bodlaender et al. (ICALP 2008) and Fortnow and Santhanam (STOC 2008) initiated an impressive hardness theory for PC under the assumption coNP $\not\subseteq$ NP/poly. Since PTC is a generalization of PC, we define $\mathcal{C}$ as the set of all problems that have PTCs but have no PCs under the assumption coNP $\not\subseteq$ NP/poly. Based on the hardness theory for PC, Fernau et al. (STACS 2009) found the first problem Leaf Out-tree($k$) in $\mathcal{C}$. However, very little is known about $\mathcal{C}$, as only a dozen problems were shown to belong to the complexity class in the last ten years. Several problems are open, for example, whether CNF-SAT($n$) and $k$-path are in $\mathcal{C}$, and novel ideas are required to better understand the fundamental differences between PTCs and PCs. In this paper, we enrich our knowledge about $\mathcal{C}$ by showing that several problems parameterized by modular-width ($mw$) belong to $\mathcal{C}$. More specifically, exploiting the properties of the well-studied structural graph parameter $mw$, we demonstrate 17 problems parameterized by $mw$ are in $\mathcal{C}$, such as Chromatic Number($mw$) and Hamiltonian Cycle($mw$). In addition, we develop a general recipe to prove the existence of PTCs for a large class of problems, including our 17 problems.
