## Archive for the ‘Graph Theory’ Category

### Interview with László Lovász

May 11, 2013

On November 28, 2011, Avi Wigderson interviewed László Lovász. A total of 27 short videos can be watched at the Simons Foundation website. I particularly liked the discussion on the LLL algorithm, and also on semidefinite relaxations.

__________

Related:

April 3, 2012

A directed graph (or digraph) is an ordered pair $D = (V, A)$, where $V$ is a non-empty finite set of elements called vertices, and $A$ is a finite set of elements called arcs, where an arc is an ordered pair of distinct vertices [1]. We call $V$ and $A$ the vertex set and the arc set, respectively. Note that $A \subseteq V \times V$. For an arc $(v_i, v_j)$, we call $v_i$ the tail, and $v_j$ the head, and say that the arc $(v_i, v_j)$ leaves vertex $v_i$ and enters vertex $v_j$.

For instance, consider the digraph depicted below

This digraph has 10 vertices and 15 arcs. How would we build this digraph in Haskell? A vertex could be represented by an integer, and an arc could be represented by an ordered pair of integers. However, in Mathematics we work with sets, whereas in Haskell we work with lists. Hence, we could represent the vertex set by a list of vertices, and the arc set by a list of edges.

Here is a simplistic implementation:

-- type synonyms
type Vertex  = Int
type Arc     = (Vertex,Vertex)
type Digraph = ([Vertex],[Arc])

-- create list of vertices
vs :: [Vertex]
vs = [1..10]

-- create list of arcs
as :: [Arc]
as = [(1,4),(1,5),(1,6),(2,4),(3,4),
(4,5),(5,6),(7,6),(8,1),(8,2),
(8,7),(9,8),(9,10),(10,2),(10,3)]

-- create digraph
digraph :: Digraph
digraph = (vs,as)

We load this script in GHCi and perform some simple testing:

*Main> -- list of vertices
*Main> vs
[1,2,3,4,5,6,7,8,9,10]
*Main> length vs
10
*Main> -- list of arcs
*Main> as
[(1,4),(1,5),(1,6),(2,4),(3,4),(4,5),(5,6),(7,6),
(8,1),(8,2),(8,7),(9,8),(9,10),(10,2),(10,3)]
*Main> length as
15
*Main> -- digraph
*Main> digraph
([1,2,3,4,5,6,7,8,9,10],[(1,4),(1,5),(1,6),
(2,4),(3,4),(4,5),(5,6),(7,6),(8,1),(8,2),
(8,7),(9,8),(9,10),(10,2),(10,3)])

We have thus created a digraph. What can we do with it? Is there anything of interest that we could compute?

__________

Neighborhoods

Given a digraph $D = (V, A)$, we call the following sets

$N_D^{+} (v) = \{ u \in V \mid (v, u) \in A\}$

$N_D^{-} (v) = \{ u \in V \mid (u, v) \in A\}$

the out-neighborhood of vertex $v$ and the in-neighborhood of vertex $v$, respectively [1]. The vertices in $N_D^{+} (v)$ and $N_D^{-} (v)$ are called the out-neighbors and the in-neighbors of vertex $v$, respectively.

In Haskell, we compute the out- and in-neighborhoods as follows:

-- compute out-neighborbood of a vertex
outNeighbors :: Digraph -> Vertex -> [Vertex]
outNeighbors (vs,as) v = map snd (filter (p v) as)
where p v (t,h) | t == v = True
| t /= v = False

-- compute in-neighborbood of a vertex
inNeighbors :: Digraph -> Vertex -> [Vertex]
inNeighbors (vs,as) v = map fst (filter (p v) as)
where p v (t,h) | h == v = True
| h /= v = False

Let us do some testing in GHCi:

*Main> -- list of all out-neighborhoods
*Main> map (outNeighbors digraph) vs
[[4,5,6],[4],[4],[5],[6],[],[6],[1,2,7],[8,10],[2,3]]
*Main> -- list of all in-neighborhoods
*Main> map (inNeighbors digraph) vs
[[8],[8,10],[10],[1,2,3],[1,4],[1,5,7],[8],[9],[],[9]]

__________

Degrees

Given a digraph $D = (V, A)$, we call the following cardinalities

$d_D^{+} (v) = |N_D^{+} (v)|$

$d_D^{-} (v) = |N_D^{-} (v)|$

the out-degree and the in-degree of vertex $v$, respectively [1]. We compute the out- and in-degrees in Haskell as follows:

-- compute out-degree of a vertex
outDegree :: Digraph -> Vertex -> Int
outDegree (vs,as) v = length (outNeighbors (vs,as) v)

-- compute in-degree of a vertex
inDegree :: Digraph -> Vertex -> Int
inDegree (vs,as) v = length (inNeighbors (vs,as) v)

Let us do some testing in GHCi:

*Main> -- out-degrees of all vertices
*Main> map (outDegree digraph) vs
[3,1,1,1,1,0,1,3,2,2]
*Main> -- in-degrees of all vertices
*Main> map (inDegree digraph) vs
[1,2,1,3,2,3,1,1,0,1]

__________

Concluding remarks

Here is the whole Haskell script:

-- type synonyms
type Vertex  = Int
type Arc     = (Vertex,Vertex)
type Digraph = ([Vertex],[Arc])

-- create list of vertices
vs :: [Vertex]
vs = [1..10]

-- create list of arcs
as :: [Arc]
as = [(1,4),(1,5),(1,6),(2,4),(3,4),
(4,5),(5,6),(7,6),(8,1),(8,2),
(8,7),(9,8),(9,10),(10,2),(10,3)]

-- create digraph
digraph :: Digraph
digraph = (vs,as)

-- compute out-neighborbood of a vertex
outNeighbors :: Digraph -> Vertex -> [Vertex]
outNeighbors (vs,as) v = map snd (filter (p v) as)
where p v (t,h) | t == v = True
| t /= v = False

-- compute in-neighborbood of a vertex
inNeighbors :: Digraph -> Vertex -> [Vertex]
inNeighbors (vs,as) v = map fst (filter (p v) as)
where p v (t,h) | h == v = True
| h /= v = False

-- compute out-degree of a vertex
outDegree :: Digraph -> Vertex -> Int
outDegree (vs,as) v = length (outNeighbors (vs,as) v)

-- compute in-degree of a vertex
inDegree :: Digraph -> Vertex -> Int
inDegree (vs,as) v = length (inNeighbors (vs,as) v)

We now know how to create digraphs in Haskell and compute simple things, like neighborhoods and degrees. What else would it be of interest to compute?

__________

References

[1] Jørgen Bang-Jensen, Gregory Z. Gutin, Digraphs: Theory, Algorithms and Applications (2nd edition), Springer, 2009.

### 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

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.