Deciding 2-colorability via quantifier elimination

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.

About these ads

Tags: 2-Colorability, Algebraic Sets, Decision Problems, Feasibility, Graph Coloring, Graph Theory, Quantifier Elimination, Real Algebraic Geometry, REDLOG, REDUCE, Vertex Coloring

This entry was posted on September 1, 2011 at 22:26 and is filed under Algebraic Geometry, Graph Theory. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

One Response to “Deciding 2-colorability via quantifier elimination”

Jasmin Blanchette Says:
September 2, 2011 at 04:18 | Reply
Minor typo: “et alia” should have been “et alii”; the former is plural neutral and appropriate for things, while the latter is plural masculine and more suitable for people (unless all the coauthors are females).

Rod Carvalho

Deciding 2-colorability via quantifier elimination

Like this:

One Response to “Deciding 2-colorability via quantifier elimination”

Leave a Reply Cancel reply

Follow “Rod Carvalho”