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.
References
[1]
Adams, W. and Loustaunaus, P. (1991) An Introduction to Grobner Bases. American Mathematical Society, Washington DC.
[2]
Abello, J., Butenko, S., Pardalos, P.M. and Resende, M.G.C. (2001) Finding Independent Sets in a Graph Using Continuous Multi-Variable Polynomial Formulations. Journal of Global Optimization, 21, 111-137. https://doi.org/10.1023/A:1011968411281
[3]
Cox, D., Little, J. and O’Shea, D. (2006) Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. 3rd Edition, Springer, New York.
[4]
Moeller, H.M. (1993) On Decomposing Systems of Polynomial Equations with Finitely Many Solutions. Applicable Algebra in Engineering, Communication and Computing, 4, 217-230. https://doi.org/10.1007/BF01200146
[5]
Nayeem, S.M.A. and Pal, M. (2007) Genetic Algorithmic Approach to Find the Maximum Weight Independent Set of a Graph. Journal of Applied Mathematics and Computing, 25, 217-219. https://doi.org/10.1007/BF02832348
[6]
Márquez-Campos, G., Ojeda, I. and Tornero, J.M. (2015) On the Computation of the Apéry Set of Numerical Monoids and Affine Semigroups. Semigroup Forum, 91, 139-158. https://doi.org/10.1007/s00233-014-9631-y
[7]
Dong, R. and Wang, D.M. (2019) Computing Strong Regular Characteristic Pairs with Groebner Bases. arXiv: 1907.13537.
[8]
Huang, Z.Y., England, M., Davenport, J.H. and Paulson, L.C. (2016) Using Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition with Groebner Bases. 2016 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), Timisoara, 24-27 September 2016, 45-52. https://doi.org/10.1109/SYNASC.2016.020
[9]
Grolet, A. and Thouverez, F. (2015) Computing Multiple Periodic Solutions of Nonlinear Vibration Problems Using the Harmonic Balance Method and Groebner Bases. Mechanical Systems and Signal Processing, 52-53, 529-547. https://doi.org/10.1016/j.ymssp.2014.07.015
[10]
Zhou, N., Wu, J.Z. and Gao, X.Y. (2013) Algebraic Verification Method for SEREs Properties via Groebner Bases Approaches. Journal of Applied Mathematics, 2013, Article ID: 272781. https://doi.org/10.1155/2013/272781
[11]
Bondy, J.A. and Murty, U.S.R. (2008) Graph Theory. Springer, Berlin.
[12]
Hoede, C. and Li, X.L. (1994) Clique Polynomials and Independent Set Polynomials of Graphs. Discrete Mathematics, 125, 219-228. https://doi.org/10.1016/0012-365X(94)90163-5
![\"\"](\"Edit_2007ea01-dcbb-4cbb-bd75-67b681be10d8.png\")
