Even-hole-free graphs
Even-hole-free graphs
复制标题
无偶孔图
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Murilo Vicente Gonçalves
中科院分区：
文献类型：
--
作者：
Da Silva;Murilo Vicente Gonçalves
在这篇论文中，我们考虑了一类由排除偶孔（即偶长度的无弦环）所定义的简单图。这些图被称为无偶孔图。我们首先证明了每一个偶孔图都有一个邻域被三角化的节点。这意味着在一个有n个节点和m条边的无偶孔图中，最多有n+2m个最大团。它还提供了一种已知最快的算法，用于计算无偶孔图中的最大团。
In this thesis we consider the class of simple graphs defined by excluding even holes (i.e. chordless cycles of even length). These graphs are known as even-hole-free graphs. We first prove that every even-hole-free graph has a node whose neighborhood is triangulated. This implies that in an even-hole-free graph, with n nodes and m edges, there are at most n+2m maximal cliques. It also yields a fastest known algorithm for computing a maximum clique in an even-hole-free graph.
Afterwards we prove the main result of this thesis. The result is a decomposition theorem for even-hole-free graphs, that uses star cutsets and 2-joins. This is a significant strengthening of the only other previously known decomposition of even-hole-free graphs, by Conforti, Cornu´ejols, Kapoor and Vuˇskovi´c, that uses 2-joins and star, double star and triple star cutsets. It is also analogous to the decomposition of Berge (i.e. perfect) graphs with skew cutsets, 2-joins and their complements, by Chudnovsky, Robertson, Seymour and Thomas. In a graph that does not contain a 4-hole, a skew cutset reduces to a star cutset, and a 2-join in the complement implies a star cutset, so in a way it was expected that even-hole-free graphs can be decomposed with just the star cutsets and 2-joins.
A consequence of this decomposition theorem is an O(n19) recognition algorithm for even-hole-free graphs. The recognition of even-hole-free graphs was first shown to be polynomial by Conforti, Cornu´ejols, Kapoor and Vuˇskovi´c. They obtained an algorithm of complexity of about O(n40) by first preprocessing the input graph using a certain “cleaning” procedure, and then constructing a decomposition based recognition algorithm. The cleaning procedure was also the key to constructing a polynomial time recognition algorithm for Berge graphs. At that time it was observed by Chudnovsky and Seymour that once the cleaning is performed, one does not need a decomposition based algorithm, one can instead just look for the “bad structure” directly. Using this idea, as opposed to using the decomposition based approach, one gets significantly faster recognition algorithms for Berge graphs and balanced 0,±1 matrices. However, this approach yields an O(n31) recognition algorithm for even-hole-free graphs. So this is the first example of a decomposition based algorithm being significantly faster than the Chudnovsky/Seymour style algorithm.