论文标题
用子图互补切割一棵树很难，除了一些小树
Cutting a tree with Subgraph Complementation is hard, except for some small trees
论文作者
论文摘要
对于Graph属性$π$，对$π$的子图互补是要找到输入图$ g $的子集$ s $的一个子集$ s $，从而通过补充$ s $引起的子格言来修改$ g $，从而在满足属性$π$的图形中导致图形。我们证明，对$ t $ free图的子图互补的问题是NP完整的，因为$ t $是一棵树，除了最多13个顶点的41棵树（如果图形为$ t $ - 如果不包含任何引起的$ t $ of $ t $）。该结果以及4个已知的多项式溶解案例（当$ t $在最多4个顶点上是一条路径时），留下了37个开放式案例。此外，我们证明这些严重问题没有接受指数时间假设的任何次指数时间算法。作为另一个结果，我们可以在多项式时间中求解对无PAW图的子图互补。
For a graph property $Π$, Subgraph Complementation to $Π$ is the problem to find whether there is a subset $S$ of vertices of the input graph $G$ such that modifying $G$ by complementing the subgraph induced by $S$ results in a graph satisfying the property $Π$. We prove that the problem of Subgraph Complementation to $T$-free graphs is NP-Complete, for $T$ being a tree, except for 41 trees of at most 13 vertices (a graph is $T$-free if it does not contain any induced copies of $T$). This result, along with the 4 known polynomial-time solvable cases (when $T$ is a path on at most 4 vertices), leaves behind 37 open cases. Further, we prove that these hard problems do not admit any subexponential-time algorithms, assuming the Exponential Time Hypothesis. As an additional result, we obtain that Subgraph Complementation to paw-free graphs can be solved in polynomial-time.
