TITLE:
Solving the k-Independent Sets Problem of Graphs by Gröbner Bases
AUTHORS:
Junyu Luo, Shengzhen Ding
KEYWORDS:
k-Independent Set, Maximal Independent Set, Gröbner Bases
JOURNAL NAME:
Open Journal of Discrete Mathematics,
Vol.13 No.3,
July
6,
2023
ABSTRACT: 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 for. 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 Gröbner bases of polynomial ideals. Since the number
of k-independent sets is finite, the
triangular equations composed by Gröbner 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 illustrate the effectiveness of this algebraic
computational method.