图的k-独立集与Grbner基求解

Solving the k-independent Sets Problem of Graphs by Grbner Bases

本文给出一种求解任一具有n个顶点的有限图G的极大独立集和独立数的代数计算方法.该方法是通过将求解G的极大独立集问题加强为对每个1≤k≤n求解G的k-独立集问题来给出的.首先证明了G中k-独立集的存在性等价于一个多元多项式方程组的解的存在性,使得可以通过使用多项式理想的Grbner来判断所得方程组解的存在性并进一步求解方程组.由于k-独立集存在时只有有限多个,得到的Grbner基构成的方程组是很容易求解的三角形方程组,G的极大独立集和独立数在求解最多n个方程组即可得到.最后,通过实例验证了代数计算方法的有效性.

The aim of this paper is to given an algebraic computational method for finding maximal independent sets as well as the independent number of an arbitrary finite graph of n vertices G by strengthening the problem of finding maximal independent sets of G to the problem of finding k- independent sets in G for1≤k≤n. It is shown that the existence of k-independent sets in G is equivalent to the existence of solutions of a system of multivariate polynomial equations. It follows that the problem of finding k-independent sets can be realized by using Grobner bases of polynomial ideals. Since the number of k-independent sets is finite, the triangular equations composed by Grobner bases are easier to be solved. Consequently, the maximal independent sets and the independent number of G are obtained after solving at most n such equations. Finally, the numerical example is presented to illustrated the effectiveness of this algebraic computational method.