Solving the k-Independent Sets Problem of Graphs by Gröbner Bases

Junyu Luo, Shengzhen Ding

Department of Mathematics, Science and Statistics University of Zhaoqing, Zhaoqing, China.

DOI: 10.4236/ojdm.2023.133008                

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.

Keywords

k-Independent Set, Maximal Independent Set, Gröbner Bases

1. Introduction

$ℂ\left[X\right]$ is the polynomials which are defined on the field of complex numbers with variables $X=\left(x_1\mathrm{,}{x}_2\mathrm{,}\cdots \mathrm{,}{x}_n\right)$ , $S=\left\{f_1\mathrm{,}{f}_2\mathrm{,}\cdots \mathrm{,}{f}_m\right\}\subset ℂ\left[X\right]$ is a polynomial set contains m polynomials with n variables, let $\langle S\rangle$ denotes the ideal which is generated by the polynomial set S. We consider the system of polynomial equations:

$f_1=0,f_2=0,\cdots ,f_m=0.$ (1)

A well-known fact in computational algebra is that [1] , when the monomial order $\prec$ is given, calculating a Gröbner bases G of the ideal $\langle S\rangle$ could solves the following three problems simultaneously:

i) The system of Equations (1) has no solution if and only if G contains a non-zero constant.

ii) The system of Equations (1) has only finitely many solutions if and only if for each $x_i\mathrm{,1}\le i\le n$ , there exists $g_i\in G$ such that the leading monomial of $g_i$ is of the form $x_i^{n_i}$ , where $n_i>0$ .

iii) Since any monomial sequence $\prec$ is an eliminative sequence, in the case where the system of Equations (1) has a solution and only finitely many solutions G gives a very simple “trapezoidal” system of equations equivalent to the system (1), i.e. It can be solved by a successively variational back-substitution manner.

The problem of finding a extremely independent set in graph theory is usually solved using optimization methods. The literature [2] transforms the problem of finding a extremely independent set into an optimization problem for the solution of multivariate polynomial equations. In this paper, we enhance the existing literature from the simple problem of finding a extremely independent set to a more general one. In this paper, we enhance the problem of finding a extremely independent set from the existing literature to the more general problem of determining the existence and solution of an independent set with k vertices, and use the Gröbner basis to give a solution to this problem. The Gröbner basis is used to give an efficient solution. Precisely, for any given finite graph G and $k\ge 1$ , we first transform the problem of the existence of an independent set with k vertices in G into the problem of the existence of solutions (actually 0 - 1 solutions with coordinates 0 or 1) to a system of multivariate polynomial equations. Noting that there are only finitely many such 0 - 1 solutions (if they exist), by virtue of i), ii) and iii) above, we can compute the Gröbner basis to give an efficient discriminant and solution path for the independent set of a graph G with k vertices, and thus find the number of independent and maximal independent sets of the graph. Due to the fact that the techniques for computing the Gröbner basis of polynomials are now very well established any of the computational algebra programs such as Maple, Macaulay 2, CoCoA, etc. [3] [4] can calculate the ideal Gröbner basis for a given polynomial group. Beside, there are now more recent algorithms for calculating Gröbner bases such as F4, F5. Therefore, the method obtained in this paper can be applied directly to any finite graph without involving the complexity of existing algorithms for computing Gröbner bases. It does not involve the complexity of existing algorithms for computing Gröbner bases, nor does it discuss the comparison with existing optimization algorithms that only find very large independent sets.

2. Preliminaries

This section briefly introduces the knowledge about independent sets in graph theory needed later and the existing literature [5] on solving graphs by optimization methods for the main methods and results on very large independent sets.

Given a graph $G=\left(V\mathrm{,}E\right)$ , where $V=\left\{v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_n\right\}$ is the set of vertices of G and $E=\left\{e_{ij}:=\left(v_i,v_j\right):v_i,v_j\in V,i\ne j\right\}$ is the set of edges of G.

Definition 1. Let G be a simple graph and S a non-empty subset of V. If any two points in S are not adjacent, then S is defined as an extremely independent set of G. If G has no independent set $S^{\prime }$ such that $\left|S^{\prime }\right|>\left|S\right|$ , then S is an extremely independent set of the graph G. The number of vertices contained in the extremely independent set of a graph G is called the independence number of the graph G.

Let the following graph $G=\left(V\mathrm{,}E\right)$ be a simple graph and $A={\left[a_{ij}\right]}_{n\times n}$ be the adjacency matrix of the graph G, where

$a_{ij}=\{\begin{array}{ll}0,\hfill & e_{ij}\notin E\hfill \\ 1,\hfill & e_{ij}\in E.\hfill \end{array}$

In particular, $a_{ii}=0,i=1,2,\cdots ,n$ . Let $A_i$ denote the i-th row of the matrix A. Using the notation in the literature [2] , for a subset S of the graph G, define the vector $x^s={\left(x_1\mathrm{,}{x}_2\mathrm{,}\cdots \mathrm{,}{x}_n\right)}^{\text{T}}$ ,where

$x_i=\{\begin{array}{ll}0,\hfill & v_i\notin S,\hfill \\ 1,\hfill & v_i\in S,\hfill \end{array}$

Then

$A_i{x}^s={\displaystyle {\sum }_{j=1}^n}{a}_{ij}{x}_j,$

denotes the sum of the number of edges connected to the point $v_i$ in the subset S.

Theorem 1. [6] A point set $S\subset V$ is an independent set of the graph $G=\left(V\mathrm{,}E\right)$ if and only if ${\left(x^s\right)}^{\text{T}}A{x}^s=0$ .

3. Gröbner Basis Discriminant for k-Independent Sets of Graphs and Their Existence

Given a graph $G=\left(V\mathrm{,}E\right)$ with n vertices, it is clear that G has a extremely independent set. But we would like to know for which $1\le k\le n$ there exists an independent set in G with k vertices. In this section we translate the problem of existence and solution of k-independent sets into the solution of systems of multivariate polynomial equations by drawing on the literature [7] for solving very 0 - 1 polynomial programming methods for extremely independent sets and gives an efficient discriminant for graphs containing k-independent sets using the Gröbner basis.

Adopting the notation used in Section 2, by expanding the left-hand side of the equation ${\left(x^s\right)}^{\text{T}}A{x}^s=0$ from Theorem 1 in the previous section, we obtain that

${\left(x^s\right)}^{\text{T}}A{x}^s={\displaystyle {\sum }_{i,j}^n}{a}_{ij}{x}_i{x}_j=0,$ (2)

where $a_{ij}$ is a non-negative integer and $a_{ij}\ne 0$ if and only if $e_{ij}\in E$ . In particular, $a_{ii}=0$ . It follows from Theorem 1 that there exists a one-to-one correspondence between the set of independent sets of the graph G and the set of 0 - 1 solutions (i.e. solutions with coordinates 0 or 1) of the multivariate polynomial equation

${\displaystyle {\sum }_{i,j}^n}{a}_{ij}{x}_i{x}_j=0$

The definition of the vector $x^s$ and the 0 - 1 assignment rule for its coordinates $x_i$ imply that the k vertices $v_{i_1}\mathrm{,}{v}_{i_2}\mathrm{,}\cdots ,v_{i_k}$ form an independent set of G must have $x_{i_1}+x_{i_2}+\cdots +x_{i_k}=k$ .

Definition 2. Let $S\subseteq G$ be an independent set of a graph G. If $\left|S\right|=k$ , where $1\le k\le \left|V\right|=n$ , then S is said to be a k-independent set of a graph G.

Here we use the classical Gröbner basis method [1] for discriminating the existence of solutions to systems of polynomial equations to give an efficient discriminant for the existence of k-independent sets.

Theorem 2. $\forall k,1\le k\le \left|V\right|=n$ ,consider the following system of equations determined by a polynomial over a complex field $ℂ$ :

$\left(S_k\right)$ $(\begin{array}{l}{\left(x^s\right)}^{\text{T}}A{x}^s={\displaystyle {\sum }_{i,j}^n{a}_{ij}{x}_i{x}_j}=0,a_{ii}=0,i=1,2,\cdots ,n,a_{ij}\ne 0\iff e_{ij}\in E,\\ {\displaystyle {\sum }_{i=1}^n{x}_i}-k=0,\\ x_i\left(x_i-1\right)=0,i=1,2,\cdots ,n.\end{array}$

i) Graph G has k-independent sets if and only if the system of equations $S_k$ has a solution.

ii) If the system of equations $\left(S_k\right)$ has solutions, then all solutions of $S_k$ are given for all k-independent sets of G.

iii) Let I be the ideal generated by all the first terms of the equations of $\left(S_k\right)$ in the multivariate polynomial ring $R=ℂ\left[x_1\mathrm{,}{x}_2\mathrm{,}\cdots \mathrm{,}{x}_n\right]$ . Then the system of equations $\left(S_k\right)$ has a solution if and only if the Gröbner basis of the ideal I does not contain non-zero constants.

Proof: i) By Theorem 1 a set $S\subseteq G$ is an independent set of the graph $G=\left(V,E\right)$ if and only if ${\left(x^s\right)}^{\text{T}}A{x}^s=0$ . Then we now only need to verify the sufficient necessity of k-independent sets. If the graph G has a k-independent set, then

${\displaystyle {\sum }_{i=1}^n{x}_i}-k=0$ (3)

has a solution and thus the system of equations $\left(S_k\right)$ has a solution. Conversely, if the system of equations $\left(S_k\right)$ has a solution, then the Equation (3) must have a solution, i.e. there exists an independent set with k vertices. Thus, the graph G has a k-independent set.

ii) If the equation $\left(S_k\right)$ has a solution, then for a solution of $\left(S_k\right)$ , take the set of vertices corresponding to $x_i$ which takes the value 1. The set of vertices is a k-independent set of the graph G by the definition of the vector $x^s$ . Alternatively, for a k-independent set of the graph G, the corresponding vector $x^s={\left(x_1\mathrm{,}{x}_2\mathrm{,}\cdots \mathrm{,}{x}_n\right)}^{\text{T}}$ satisfies

${\displaystyle {\sum }_{i=1}^n{x}_i}-k=0,x_i\left(x_i-1\right)=0,i=1,2,\cdots ,n.$

And by the conclusion of Theorem 1, Equation (2) holds, and therefore the system of equations $\left(S_k\right)$ holds. Thus the vector corresponding to this independent set is a solution of the system of equations $\left(S_k\right)$ . The solutions of the system of equations $\left(S_k\right)$ and the independent sets of the graph G correspond one-to-one, i.e. all solutions of the system of equations $\left(S_k\right)$ give all k-inde- pendent sets of G.

iii) The solution of the system of equations $\left(S_k\right)$ and the solution of the Gröbner basis of the ideal I are identical by the nature of the Gröbner basis. If the equation system $\left(S_k\right)$ has a solution, then $V\left(I\right)\ne \varnothing$ , i.e. $G\ne \left\{1\right\}$ , so that the solution of the Gröbner basis of the ideal I does not contain non-zero constants; If the Gröbner basis of the ideal I does not contain non-zero constants, then we have $V\left(I\right)\ne \varnothing$ and thus the system of equations $\left(S_k\right)$ has a solution [8] [9] [10] .

4. Gröbner Based Methods for Finding k-Independent Sets, Independence Numbers and Maximal Independence Sets of Graphs

This section gives the Gröbner basis method for finding the k-independent set of a graph, the number of independents and the extremely independent set according to Theorem 2 in Section 3. Using the notation used in the previous two sections.

4.1. Method for Finding the k-Independent Set of a Graph

According to the previous discussion, if the system of equations $\left(S_k\right)$ has a solution, all k-independent sets of the graph G can be obtained by solving the system of equations $\left(S_k\right)$ . Although there are many ways to solve a multivariate polynomial, note that if the system of equations $\left(S_k\right)$ has a solution, then its solutions are all 0 - 1 solutions (i.e. solutions with coordinates 0 or 1) and the number of solutions must be finite. It follows from the literature [1] that, for a given sequence $x_n\succ x_{n-1}\succ \cdots \succ x_1$ of eliminative monomials, an approximate Gröbner basis for the ideal I gives a system of equations equivalent to the system of equations $\left(S_k\right)$ in the form:

$\left({S^{\prime }}_k\right)$ $(\begin{array}{ll}{x}_n^{{\gamma }_n}+g_n\left(x_1,x_2,\cdots ,x_n\right)=0\hfill & g_{n+1}\left(x_1,x_2,\cdots x_n\right)=0\hfill \\ x_{n-1}^{{\gamma }_{n-1}}+g_{n-1}\left(x_1,\cdots ,x_{n-1}\right)=0\hfill & ⋮\hfill \\ ⋮\hfill & g_t\left(x_1,x_2,\cdots ,x_n\right)=0\hfill \\ x_2^{{\gamma }_2}+g_2\left(x_1,x_2\right)=0\hfill & \hfill \\ x_1^{{\gamma }_1}+g_1\left(x_1\right)=0\hfill & \hfill \end{array}$

Thus, after computing an approximate Gröbner basis for the ideal I under the eliminative monadic order $x_n\succ x_{n-1}\succ \cdots \succ x_1$ , all k-independent sets of the graph G can be found by back substitution. In a practical application of Theorem 2 and this conclusion, we can determine whether a graph G has a k-inde- pendent set by first calling the program for calculating Gröbner bases in Maple, and if so, we can obtain all k-independent sets of G by solving the system of equations $\left({S^{\prime }}_k\right)$ with the program for solving the system of equations $\left({S^{\prime }}_k\right)$ .

4.2. Methods for Finding the Number of Independents and the Extremely Independent Set of a Graph

The k-independent set of a graph (if it exists) is not necessarily unique. But since the number of vertices in the independent set of each finite graph is finite, the number of vertices in the k-independent set k has a maximum. This maximum value is the number of vertices in the maximal independent set of the graph, i.e. the number of independent vertices of the graph G. Following we give a method for finding the number of independence of a graph G based on Theorem 2.

Theorem 3. k is an independent number of the graph G if and only if the system of equations $\left(S_k\right)$ has a solution ,but the system of equations $\left(S_{k+1}\right)$ has no solution.

Proof $\Rightarrow$ If k is the independence number of the graph G, then it follows that the number of vertices contained in the extremely independent set of the graph G is k. By the conclusion of 1) in Theorem 2 we know that the system of equations $\left(S_k\right)$ has a solution. By the definition of independence, the number of vertices in an independent set in graph G is at most k. Therefore, there is no independent set with $k+1$ vertices in graph G. Hence, equation

${\displaystyle {\sum }_{i=1}^n{x}_i}-\left(k+1\right)=0$

has no solution, so the system of equations $\left(S_{k+1}\right)$ has no solution.

$\Leftarrow$ If the system of equations $\left(S_k\right)$ has a solution and the system of equations $\left(S_{k+1}\right)$ has no solution, by the conclusion of i) in Theorem 2 we have that there exists a k-independent set but not a $\left(k+1\right)$ -independent set of the graph G. This means that the maximum number of vertices contained in the independent set of the graph G can only be k. So by definition of an independent number, k is an independent number of the graph G.

A solution to the problem of finding the number of independents can be obtained from Theorem 3, i.e. We can achieve the independence numbers by computing the k-independence sets in the order from small to large or from large to small, and thus obtain the extremely independent set of the graph G.

5. Experiment

Consider Figure 1 below [11] [12] , a finite graph $G=\left(V,E\right)$ , where the set of vertices $V=\left\{v_1,v_2,v_3,v_4,v_5\right\}$ and the set of edges $E=\left\{e_{12},e_{15},e_{23},e_{24},e_{25},e_{34},e_{45}\right\}$ .

In the following we apply the calculations gained earlier to compute the k-independent set, the number of independent sets and the extremely independent set of the graph G respectively. Where the adjacency matrix is as follows:

$A=\left[\begin{array}{lllll}0\hfill & 1\hfill & 0\hfill & 0\hfill & 1\hfill \\ 1\hfill & 0\hfill & 1\hfill & 1\hfill & 1\hfill \\ 0\hfill & 1\hfill & 0\hfill & 1\hfill & 0\hfill \\ 0\hfill & 1\hfill & 1\hfill & 0\hfill & 1\hfill \\ 1\hfill & 1\hfill & 0\hfill & 1\hfill & 0\hfill \end{array}\right]$ .

Figure 1. Graph $G=\left(V,E\right)$ .

We now calculate the k-independent set using the order from smallest to largest for k.

1-independent set

$\left(S_1\right)$ $(\begin{array}{l}{\left(x^s\right)}^{\text{T}}A{x}^s=2x_1{x}_2+2x_1{x}_5+2x_2{x}_3+2x_2{x}_4+2x_2{x}_5+2x_3{x}_4+2x_4{x}_5=0,\\ x_1+x_2+x_3+x_4+x_5-1=0,x_1\left(x_1-1\right)=0,x_2\left(x_2-1\right)=0,\\ x_3\left(x_3-1\right)=0,x_4\left(x_4-1\right)=0,x_5\left(x_5-1\right)=0.\end{array}$

An approximate Gröbner basis for the ideal $I_{S_1}$ is obtained by the procedure for calculating the Gröbner basis in Maple.

$\begin{array}{l}{G}_1=\{x_1^2-x_1\mathrm{,}{x}_1{x}_2\mathrm{,}{x}_2^2-x_2\mathrm{,}{x}_1{x}_3\mathrm{,}{x}_2{x}_3\mathrm{,}{x}_3^2-x_3\mathrm{,}{x}_4{x}_1\mathrm{,}{x}_2{x}_4\mathrm{,}{x}_3{x}_4\mathrm{,}\\ x_4^2-x_4\mathrm{,}{x}_1+x_2+x_3+x_4+x_5-1\}.\end{array}$

The system of equations $\left({S^{\prime }}_1\right)$ equivalent to the system of equations $\left(S_1\right)$ is given by $G_1$ as

$\left({S^{\prime }}_1\right)$ $(\begin{array}{l}{x}_5+x_4+x_3+x_2+x_1-1=0,x_4^2-x_4=0,x_3^2-x_3=0,x_2^2-x_2=0,x_1^2-x_1=0,\\ x_1{x}_2=0,x_1{x}_3=0,x_2{x}_3=0,x_4{x}_1=0,x_2{x}_4=0,x_3{x}_4=0.\end{array}$

Calling the program in Maple that solves the system of equations for the system of equations $\left({S^{\prime }}_1\right)$ to obtain all 1-independent sets

$\begin{array}{l}\left\{x_1=1,x_2=0,x_3=0,x_4=0,x_5=0\right\},\left\{v_1\right\}\\ \left\{x_1=0,x_2=1,x_3=0,x_4=0,x_5=0\right\},\left\{v_2\right\}\\ \left\{x_1=0,x_2=0,x_3=1,x_4=0,x_5=0\right\},\left\{v_3\right\}\\ \left\{x_1=0,x_2=0,x_3=0,x_4=1,x_5=0\right\},\left\{v_4\right\}\\ \left\{x_1=0,x_2=0,x_3=0,x_4=0,x_5=1\right\},\left\{v_5\right\}.\end{array}$

2-independent sets

$\left(S_2\right)$ $(\begin{array}{l}{\left(x^s\right)}^{\text{T}}A{x}^s=2x_1{x}_2+2x_1{x}_5+2x_2{x}_3+2x_2{x}_4+2x_2{x}_5+2x_3{x}_4+2x_4{x}_5=0,\\ x_1+x_2+x_3+x_4+x_5-2=0,x_1\left(x_1-1\right)=0,x_2\left(x_2-1\right)=0,\\ x_3\left(x_3-1\right)=0,x_4\left(x_4-1\right)=0,x_5\left(x_5-1\right)=0.\end{array}$

An approximate Gröbner basis for the ideal $I_{S_2}$ is obtained by the procedure for calculating the Gröbner basis in Maple.

$G_2=\left\{x_1^2-x_1,x_2,x_1{x}_3-x_3-x_1+1,x_3^2-x_3,x_4+x_3-1,x_1+x_5-1\right\}.$

The system of equations $\left({S^{\prime }}_2\right)$ equivalent to the system of equations $\left(S_2\right)$ is given by $G_2$ as

$\left({S^{\prime }}_2\right)$ $(\begin{array}{l}{x}_5+x_1-1=0,x_4+x_3-1=0,x_3^2-x_3=0,x_2=0,x_1^2-x_1=0,\\ x_1{x}_3-x_3-x_1+1=0.\end{array}$

Similarly for the system of equations $\left({S^{\prime }}_2\right)$ is solved to obtain all 2-inde- pendent sets

$\begin{array}{l}\left\{x_1=1,x_2=0,x_3=1,x_4=0,x_5=0\right\},\left\{v_1,v_3\right\}\\ \left\{x_1=1,x_2=0,x_3=0,x_4=1,x_5=0\right\},\left\{v_1,v_4\right\}\\ \left\{x_1=0,x_2=0,x_3=1,x_4=1,x_5=1\right\},\left\{v_3,v_5\right\}\end{array}$

3-independent sets

$\left(S_3\right)$ $(\begin{array}{l}{\left(x^s\right)}^{\text{T}}A{x}^s=2x_1{x}_2+2x_1{x}_5+2x_2{x}_3+2x_2{x}_4+2x_2{x}_5+2x_3{x}_4+2x_4{x}_5=0,\\ x_1+x_2+x_3+x_4+x_5-3=0,x_1\left(x_1-1\right)=0,x_2\left(x_2-1\right)=0,\\ x_3\left(x_3-1\right)=0,x_4\left(x_4-1\right)=0,x_5\left(x_5-1\right)=0.\end{array}$

Calculating a Gröbner basis of the ideal $\left(S_3\right)$ yields its Gröbner basis $G=\left\{1\right\}$ , containing non-zero constants, so by the conclusion of Theorem 2 in iii) we know that the system of equations $\left(S_3\right)$ is non-solvable. So the graph does not exist as a 3-independent set.

The system of equations $\left(S_2\right)$ has a solution but the system of equations $\left(S_3\right)$ has no solution. By the conclusion of Theorem 3, the number of independents of the graph G is 2, and the independent sets are as follows:

1-independent sets $\left\{v_1\right\}\mathrm{,}\left\{v_2\right\}\mathrm{,}\left\{v_3\right\}\mathrm{,}\left\{v_4\right\}\mathrm{,}\left\{v_5\right\}$ ;

2-independent sets $\left\{v_1\mathrm{,}{v}_3\right\}\mathrm{,}\left\{v_1\mathrm{,}{v}_4\right\}\mathrm{,}\left\{v_3\mathrm{,}{v}_5\right\}$ .

The independence number of a graph G is 2. The set of all 2-independents is the extremely independent set of the graph.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

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