Computing Graph Roots Without Short Cycles
Computing Graph Roots Without Short Cycles
复制标题
计算没有短周期的图根
DOI：
10.4230/lipics.stacs.2009.1827
复制
发表时间：
2009
影响因子：
0.5
通讯作者：
Nguyen Ngoc Tuy
中科院分区：
文献类型：
--
作者：
Babak Farzad;L. Lau;V. B. Le;Nguyen Ngoc Tuy
G是图H的平方，如果两个顶点x，y在G中有一条边当且仅当x，y在H中的距离至多为2.给定H很容易计算它的平方H 2，然而Motwani和Sudan证明了确定一个给定的图G是否是某个图H（围长为3）的平方是NP-完全的。本文研究了小围长图的平方图的特征和识别问题，即对某个小围长图H，判定G是否= H2.这些结果几乎提供了一个二分法定理的复杂性的识别问题的平方根围。算法和图论的结果推广了以前的结果树平方根，并提供多项式时间算法来计算一个图平方根的小围长，如果它存在。还将讨论一些开放的问题和建议。
Gra ph G is the square of graph H if two vertices x, y have an edge in G if and only if x, y are of distance at most two in H. Given H it is easy to compute its square H 2 , however Motwani and Sudan proved that it is NP-complete to determine if a given graph G is the square of some graph H (of girth 3). In this paper we consider the characterization and recognition problems of graphs that are squares of graphs of small girth, i.e. to determine if G = H 2 for some graph H of small girth. The main results are These results almost provide a dichotomy theorem for the complexity of the recognition problem in terms of girth of the square roots. The algorithmic and graph theoretical results generalize previous results on tree square roots, and provide polynomial time algorithms to compute a graph square root of small girth if it exists. Some open questions and conjectures will also be discussed.