On the complexity of reconstructing H‐free graphs from their Star Systems
On the complexity of reconstructing H‐free graphs from their Star Systems
复制标题
关于从恒星系统重建无 H 图的复杂性
DOI：
10.1002/jgt.20544
复制
发表时间：
2011
影响因子：
0.9
通讯作者：
J. A. Telle
中科院分区：
文献类型：
--
作者：
F. Fomin;Jan Kratochvíl;D. Lokshtanov;Federico Mancini;J. A. Telle
在星星系统问题中，我们给出了一个集合系统，并询问它是否可由某个图的闭邻域的多集实现，即给定n元集合V的子集S1，S2，.，Sn，是否存在一个图G =（V，E），其中{N[v]：v∈V} = {S1，S2，..，Sn}？对于一个固定的图H，无H星星系统问题是星星系统问题的一个变体，其中询问给定的集合系统是否可由不包含H的图的闭邻域实现作为导出子图。研究了无H星星系统问题的计算复杂性。我们证明了当H是至多四个顶点上的路或圈时，该问题是多项式时间可解的。作为对这一结果的补充，我们证明了如果H属于某一大类图，则无H的星星系统问题是NP完全的。特别地，当H是至少五个顶点上的圈或路时，该问题是NP完全的。这就产生了路径和循环的完全二分法。版权所有© 2010 John Wiley & Sons，Ltd. 68：113 - 124，2011
In the Star System problem we are given a set system and asked whether it is realizable by the multi‐set of closed neighborhoods of some graph, i.e. given subsets S1, S2, …, Sn of an n‐element set V does there exist a graph G = (V, E) with {N[v]: v∈V} = {S1, S2, …, Sn}? For a fixed graph H the H‐free Star System problem is a variant of the Star System problem where it is asked whether a given set system is realizable by closed neighborhoods of a graph containing no H as an induced subgraph. We study the computational complexity of the H‐free Star System problem. We prove that when H is a path or a cycle on at most four vertices the problem is polynomial time solvable. In complement to this result, we show that if H belongs to a certain large class of graphs the H‐free Star System problem is NP‐complete. In particular, the problem is NP‐complete when H is either a cycle or a path on at least five vertices. This yields a complete dichotomy for paths and cycles. Copyright © 2010 John Wiley & Sons, Ltd. 68:113‐124, 2011