论文标题
使用模块化分解计算图形覆盖良好的矢量空间
Computing Well-Covered Vector Spaces of Graphs using Modular Decomposition
论文作者
论文摘要
如果其所有最大独立集具有相同的基数，则图表覆盖了。 Plummer在1970年引入了这个经过良好研究的概念，并自然而然地将其推广到加权案例。鉴于图$ g $，如果其所有最大独立套件均具有相同的权重，则据说真实值的顶点权重函数$ W $被认为是$ g $的重量。图$ g $的所有覆盖权重的集合形成了实际数字领域的矢量空间，称为$ g $的覆盖矢量空间。由于识别覆盖良好的图的问题是$ \ mathsf {co} $ - $ \ MATHSF {np} $ - 完整，因此计算给定图的精心覆盖的向量空间的问题是$ \ MATHSF {CO} $ - $ \ $ \ MATHSF {np {np} $ - 硬。 Levit和Tankus在2015年表明，该问题在无爪图的类别中接受了多项式时间算法。在本文中，我们为该问题提供了两次一般减少，一个是基于抗邻国的，另一个基于模块化分解，再加上高斯消除。在这些结果的基础上，我们开发了一种多项式时间算法，用于计算给定无叉图的覆盖矢量空间，从而推广了Levit和Tankus的结果。我们的方法意味着可以在多项式时间内识别出精心覆盖的无叉图，并且在Cographs上也概括了一些已知结果。
A graph is well-covered if all its maximal independent sets have the same cardinality. This well studied concept was introduced by Plummer in 1970 and naturally generalizes to the weighted case. Given a graph $G$, a real-valued vertex weight function $w$ is said to be a well-covered weighting of $G$ if all its maximal independent sets are of the same weight. The set of all well-covered weightings of a graph $G$ forms a vector space over the field of real numbers, called the well-covered vector space of $G$. Since the problem of recognizing well-covered graphs is $\mathsf{co}$-$\mathsf{NP}$-complete, the problem of computing the well-covered vector space of a given graph is $\mathsf{co}$-$\mathsf{NP}$-hard. Levit and Tankus showed in 2015 that the problem admits a polynomial-time algorithm in the class of claw-free graph. In this paper, we give two general reductions for the problem, one based on anti-neighborhoods and one based on modular decomposition, combined with Gaussian elimination. Building on these results, we develop a polynomial-time algorithm for computing the well-covered vector space of a given fork-free graph, generalizing the result of Levit and Tankus. Our approach implies that well-covered fork-free graphs can be recognized in polynomial time and also generalizes some known results on cographs.
