Detecting Fixed Patterns in Chordal Graphs in Polynomial Time
Detecting Fixed Patterns in Chordal Graphs in Polynomial Time
复制标题
DOI：
10.1007/s00453-013-9748-5
复制
发表时间：
2013-01
期刊：
影响因子：
1.1
通讯作者：
R. Belmonte;P. Golovach;P. Heggernes;P. Hof;M. Kaminski;D. Paulusma
中科院分区：
文献类型：
--
作者：
R. Belmonte;P. Golovach;P. Heggernes;P. Hof;M. Kaminski;D. Paulusma
收缩性问题以两个图GandH作为输入，任务是决定H是否可以通过一系列边收缩从G获得。诱导子问题和诱导拓扑子问题是类似的，但前者允许边收缩和顶点删除，而后者只允许顶点删除和顶点解散。这三个问题都是NP-完全的，即使对于某些固定图H。我们表明，这些问题可以解决在多项式时间为每个fixedH时，输入图G是弦。我们的结果可以被认为是紧的，因为这些问题在弦图上是W[1]-困难的，当用H的大小参数化时。为了解决ContractibilityandInduced Minor问题，我们定义并使用了经典不相交路径问题的推广，其中我们要求从指定集合中选择每个kpaths的顶点。我们证明了这个变种是NP-完全的，即使当k =2，但它是多项式时间可解的弦图为每个fixedk。我们的算法诱导拓扑Minoris的基础上的另一个推广的不相交的路径scaledInducedDisjointPaths，其中的顶点从不同的路径可能不再相邻。我们表明，这个问题，这是已知的NP-完全当k =2，可以解决在多项式时间的弦图，即使当kis的一部分输入。我们的结果适合到一般框架的图包含问题，其目的是决定是否可以修改成另一个图的一系列指定的图形操作。允许边删除、边收缩、顶点删除和顶点分解这四种著名的操作的组合，得到以下十种包含关系：（诱导）子图、（诱导）拓扑子图、（诱导）子图、（诱导）生成子图、分解和收缩。我们的结果，结合现有的结果，解决了弦图上的十个相应的包容问题的复杂性。
TheContractibilityproblem takes as input two graphsGandH, and the task is to decide whetherHcan be obtained fromGby a sequence of edge contractions. TheInduced MinorandInduced Topological Minorproblems are similar, but the first allows both edge contractions and vertex deletions, whereas the latter allows only vertex deletions and vertex dissolutions. All three problems are NP-complete, even for certainfixedgraphsH. We show that these problems can be solved in polynomial time for every fixedHwhen the input graphGis chordal. Our results can be considered tight, since these problems are known to be W[1]-hard on chordal graphs when parameterized by the size ofH. To solveContractibilityandInduced Minor, we define and use a generalization of the classicDisjoint Pathsproblem, where we require the vertices of each of thekpaths to be chosen from a specified set. We prove that this variant is NP-complete even whenk=2, but that it is polynomial-time solvable on chordal graphs for every fixedk. Our algorithm forInduced Topological Minoris based on another generalization ofDisjoint PathscalledInduced Disjoint Paths, where the vertices from different paths may no longer be adjacent. We show that this problem, which is known to be NP-complete whenk=2, can be solved in polynomial time on chordal graphs even whenkis part of the input. Our results fit into the general framework of graph containment problems, where the aim is to decide whether a graph can be modified into another graph by a sequence of specified graph operations. Allowing combinations of the four well-known operations edge deletion, edge contraction, vertex deletion, and vertex dissolution results in the following ten containment relations: (induced) minor, (induced) topological minor, (induced) subgraph, (induced) spanning subgraph, dissolution, and contraction. Our results, combined with existing results, settle the complexity of each of the ten corresponding containment problems on chordal graphs.