A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs
A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs
复制标题
无爪图最大加权稳定集问题的新算法
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Gautier Stauffer
中科院分区：
文献类型：
--
作者：
G. Oriolo;Ugo Pietropaoli;Gautier Stauffer
在这篇文章中，我们介绍了一般图的最大加权稳定集（MWSS）的两个强大的图约化。我们表明，这些减少允许减少无爪图的MWSS中的一类准线图的MWSS，我们称之为双极自由。对于后一类，我们提供了一个新的算法分解定理在多项式时间内运行。然后，我们再次利用这个分解结果和我们的约简工具将问题转化为单个匹配问题或非循环辅助图中的最长路径计算（在后一部分中，我们使用Pulleyblank和Shepherd的一些结果[10]）。把所有的部分放在一起，本文的主要贡献是一个新的多项式时间算法的无爪图的mwss。对算法复杂度的粗略分析给出了O（n6）的时间界，其中n是图中的顶点数，我们希望通过更精细的分析可以改进。顺便说一句，我们证明了mwss问题可以有效地解决任何类的图，承认一个“合适的”分解成块的mwss是容易的。
In this paper, we introduce two powerful graph reductions for the maximum weighted stable set (mwss) in general graphs. We show that these reductions allow to reduce the mwss in claw-free graphs to the mwss in a class of quasi-line graphs, that we call bipolar-free. For this latter class, we provide a new algorithmic decomposition theorem running in polynomial time. We then exploit this decomposition result and our reduction tools again to transform the problem to either a single matching problem or a longest path computation in an acyclic auxiliary graph (in this latter part we use some results of Pulleyblank and Shepherd [10]). Putting all the pieces together, the main contribution of this paper is a new polynomial time algorithm for the mwss in claw-free graphs. A rough analysis of the complexity of this algorithm gives a time bound of O(n6), where n is the number of vertices in the graph, and which we hope can be improved by a finer analysis. Incidentally, we prove that the mwss problem can be solved efficiently for any class of graphs that admits a "suitable" decomposition into pieces where the mwss is easy.