Posts Tagged ‘Feasibility’

Deciding 2-colorability via quantifier elimination

September 1, 2011

A vertex coloring of a graph G = (V,E) is a map \kappa : V \to C that assigns a color to each vertex of G. The coloring is proper if adjacent vertices are assigned distinct colors. The graph is 2-colorable if there exists a proper coloring whose color set C has two elements.

For instance, consider a graph G = (V,E) whose vertex set is V := \{1, 2, 3\} and whose edge set is E := \{\{1,2\}, \{1,3\}, \{2,3\}\}. A pictorial representation of this graph is depicted below

Note that this graph is complete. We can assign two distinct colors to any two vertices, but we cannot assign a color to the third vertex that will yield a proper coloring. Therefore, the graph is not 2-colorable. To illustrate, we use the color set C := \{\text{pink}, \text{blue}\} and generate all 2^3 = 8 possible vertex 2-colorings, as depicted below

Notice that none of these 2-colorings is proper, as expected.

As discussed by De Loera et alia [1], the graph vertex-coloring problem can be modeled using polynomial equations. We introduce variables x_1, x_2, x_3, where x_i = -1 if vertex i is assigned the color \text{pink}, and x_i = 1 if vertex i is assigned the color \text{blue}. Given an edge \{i,j\} \in E, we have that:

  • if both vertices are pink, we get x_i + x_j = -2.
  • if both vertices are blue, we get x_i + x_j = 2.
  • if the vertices have distinct colors, we get x_i + x_j = 0.

Thus, stating that adjacent vertices must be assigned distinct colors is equivalent to imposing the constraints x_i + x_j = 0 for all \{i,j\} \in E. We thus obtain a system of three equations

\begin{array}{rl} x_1 + x_2 &= 0\\ x_1 + x_3 &= 0\\ x_2 + x_3 &= 0\end{array}

where x_1, x_2, x_3 \in \{-1,1\}. This is still a combinatorial problem, though. We can transform it into an algebraic-geometric problem. Here is a truly beautiful trick [1]: the constraint x_i \in \{-1,1\} can be encoded as x_i^2 = 1 with x_i \in \mathbb{R}. How quaint!! We then obtain a system of six equations with polynomials in \mathbb{R}[x_1, x_2, x_3]

\begin{array}{rl} x_1 + x_2 &= 0\\ x_1 + x_3 &= 0\\ x_2 + x_3 &= 0\\ x_1^2 - 1 &= 0\\ x_2^2 - 1 &= 0\\ x_3^2 -1 &= 0\end{array}

whose solution set, which we denote by S, is algebraic [2]. The given graph is 2-colorable if and only if the system of polynomial equations above is feasible, i.e., if set S is nonempty [1]. The following REDUCE + REDLOG script uses quantifier elimination to decide if S is nonempty:

% feasibility via quantifier elimination

load_package redlog;
rlset ofsf;

% define polynomial functions
f1 := x1+x2;
f2 := x1+x3;
f3 := x2+x3;
f4 := x1^2-1;
f5 := x2^2-1;
f6 := x3^2-1;

% define existential formula
phi := ex({x1,x2,x3}, f1=0 and f2=0 and f3=0 and
                      f4=0 and f5=0 and f6=0);

% perform quantifier elimination
rlqe phi;

end;

This script produces the truth value false. Thus, the solution set S is empty, which means that the system of polynomial equations is infeasible. We conclude that the given graph is not 2-colorable.

__________

References

[1] Jesús De Loera, Jon Lee, Susan Margulies, Shmuel Onn, Expressing Combinatorial Optimization Problems by Systems of Polynomial Equations and the Nullstellensatz, 2007.

[2] Jacek Bochnak, Michel Coste, Marie-Françoise Roy, Real Algebraic Geometry, Springer, 1998.

Tags:, , , , , , , , , ,
Posted in Algebraic Geometry, Graph Theory | 1 Comment »

Feasibility via quantifier elimination II

August 29, 2011

Suppose we want to decide whether the following semialgebraic set

S := \{(x,y) \in \mathbb{R}^2 \mid x - y^2 + 1 \geq 0 \land -x - y^2 + 1 \geq 0\}

is nonempty. This is the same as determining whether the following system of polynomial inequalities

\begin{array}{rrl} g_1 (x, y) :=& x - y^2 + 1 &\geq 0\\ g_2 (x, y) :=& -x - y^2 +1 &\geq 0\end{array}

is feasible. We now define S_1 := \{(x,y) \in \mathbb{R}^2 \mid g_1 (x, y) \geq 0\}, and S_2 := \{(x,y) \in \mathbb{R}^2 \mid g_2 (x, y) \geq 0\}. Set S_1 is depicted below

and set S_2 is depicted below

Note that S = S_1 \cap S_2. We depict this intersection below

Visual inspection of the plot of the intersection S = S_1 \cap S_2 allows us to conclude that S in nonempty. Asserting that S is nonempty is the same as stating that the proposition

\exists{x}\exists{y} \left(g_1 (x,y) \geq 0 \land g_2 (x,y) \geq 0\right)

is true. We can determine the truth value of this proposition via quantifier elimination using the following REDUCE + REDLOG script:

% feasibility via quantifier elimination

load_package redlog;
rlset ofsf;

% define polynomial functions
g1 :=  x-y^2+1;
g2 := -x-y^2+1;

% define existential formula
phi := ex({x,y}, g1>=0 and g2>=0);

% perform quantifier elimination
rlqe phi;

end;

which produces the truth value true. This means that there exists a (x,y) that satisfies the polynomial inequalities, i.e., S is nonempty.

__________

Remark: the plots in this post were generated by Wolfram Alpha.

Tags:, , , , , ,
Posted in Algebraic Geometry | Leave a Comment »

Feasibility via quantifier elimination

August 27, 2011

Consider the system of polynomial equations and inequalities [1]

\begin{array}{rrl} f_1 (x_1, x_2) :=& x_1^2 + x_2^2 - 1 &= 0\\ g_1 (x_1, x_2) :=& 3 x_2 - x_1^3 - 2 &\geq 0\\ g_2 (x_1, x_2) :=& x_1 - 8 x_2^3 &\geq 0\end{array}

whose solution set is the following semialgebraic set

S := \{ (x_1,x_2) \in \mathbb{R}^2 \mid f_1 (x_1,x_2) = 0 \land g_1 (x_1,x_2) \geq 0 \land g_2 (x_1,x_2) \geq 0\}

Parrilo showed in [1] that this system is infeasible, i.e., set S is empty, using the Positivstellensatz [2]. Alternatively, one could use quantifier elimination to conclude infeasibility.

Consider the following proposition

\exists{x_1}\exists{x_2} \left(f_1 (x_1,x_2) = 0 \land g_1 (x_1,x_2) \geq 0 \land g_2 (x_1,x_2) \geq 0\right).

If this proposition is true, then the system is feasible and S is nonempty. If the proposition is false, then the system is infeasible and S is empty. We can determine the truth value of the proposition using REDUCE + REDLOG to perform quantifier elimination:

% feasibility via quantifier elimination

load_package redlog;
rlset ofsf;

% define polynomial functions
f1 := x1^2+x2^2-1;
g1 := 3*x2-x1^3-2;
g2 := x1-8*x2^3;

% define existential formula
phi := ex({x1,x2}, f1=0 and g1>=0 and g2>=0);

% perform quantifier elimination
rlqe phi;

end;

The output of this script is the following:

The proposition is false and, thus, the system is infeasible.

__________

References

[1] Pablo Parrilo, Sum of Squares Programs and Polynomial Inequalities.

[2] Jacek Bochnak, Michel Coste, Marie-Françoise Roy, Real Algebraic Geometry, Springer, 1998.

Tags:, , , , , ,
Posted in Algebraic Geometry | Leave a Comment »

Follow

Get every new post delivered to your Inbox.

Join 47 other followers