Vertex separation

Vertex separation

This module implements several algorithms to compute the vertex separation of a digraph and the corresponding ordering of the vertices. It also implements tests functions for evaluation the width of a linear ordering.

Given an ordering \(v_1,\cdots, v_n\) of the vertices of \(V(G)\), its cost is defined as:

\[c(v_1, ..., v_n) = \max_{1\leq i \leq n} c'(\{v_1, ..., v_i\})\]

Where

\[c'(S) = |N^+_G(S)\backslash S|\]

The vertex separation of a digraph \(G\) is equal to the minimum cost of an ordering of its vertices.

Vertex separation and pathwidth

The vertex separation is defined on a digraph, but one can obtain from a graph \(G\) a digraph \(D\) with the same vertex set, and in which each edge \(uv\) of \(G\) is replaced by two edges \(uv\) and \(vu\) in \(D\). The vertex separation of \(D\) is equal to the pathwidth of \(G\), and the corresponding ordering of the vertices of \(D\), also called a layout, encodes an optimal path-decomposition of \(G\). This is a result of Kinnersley [Kin92] and Bodlaender [Bod98].

This module contains the following methods

path_decomposition()	Returns the pathwidth of the given graph and the ordering of the vertices resulting in a corresponding path decomposition
vertex_separation()	Returns an optimal ordering of the vertices and its cost for vertex-separation
vertex_separation_MILP()	Computes the vertex separation of \(G\) and the optimal ordering of its vertices using an MILP formulation
lower_bound()	Returns a lower bound on the vertex separation of \(G\)
is_valid_ordering()	Test if the linear vertex ordering \(L\) is valid for (di)graph \(G\)
width_of_path_decomposition()	Returns the width of the path decomposition induced by the linear ordering \(L\) of the vertices of \(G\)

Exponential algorithm for vertex separation

In order to find an optimal ordering of the vertices for the vertex separation, this algorithm tries to save time by computing the function \(c'(S)\) at most once once for each of the sets \(S\subseteq V(G)\). These values are stored in an array of size \(2^n\) where reading the value of \(c'(S)\) or updating it can be done in constant (and small) time.

Assuming that we can compute the cost of a set \(S\) and remember it, finding an optimal ordering is an easy task. Indeed, we can think of the sequence \(v_1, ..., v_n\) of vertices as a sequence of sets \(\{v_1\}, \{v_1,v_2\}, ..., \{v_1,...,v_n\}\), whose cost is precisely \(\max c'(\{v_1\}), c'(\{v_1,v_2\}), ... , c'(\{v_1,...,v_n\})\). Hence, when considering the digraph on the \(2^n\) sets \(S\subseteq V(G)\) where there is an arc from \(S\) to \(S'\) if \(S'=S\cap \{v\}\) for some \(v\) (that is, if the sets \(S\) and \(S'\) can be consecutive in a sequence), an ordering of the vertices of \(G\) corresponds to a path from \(\emptyset\) to \(\{v_1,...,v_n\}\). In this setting, checking whether there exists a ordering of cost less than \(k\) can be achieved by checking whether there exists a directed path \(\emptyset\) to \(\{v_1,...,v_n\}\) using only sets of cost less than \(k\). This is just a depth-first-search, for each \(k\).

Lazy evaluation of \(c'\)

In the previous algorithm, most of the time is actually spent on the computation of \(c'(S)\) for each set \(S\subseteq V(G)\) – i.e. \(2^n\) computations of neighborhoods. This can be seen as a huge waste of time when noticing that it is useless to know that the value \(c'(S)\) for a set \(S\) is less than \(k\) if all the paths leading to \(S\) have a cost greater than \(k\). For this reason, the value of \(c'(S)\) is computed lazily during the depth-first search. Explanation :

When the depth-first search discovers a set of size less than \(k\), the costs of its out-neighbors (the potential sets that could follow it in the optimal ordering) are evaluated. When an out-neighbor is found that has a cost smaller than \(k\), the depth-first search continues with this set, which is explored with the hope that it could lead to a path toward \(\{v_1,...,v_n\}\). On the other hand, if an out-neighbour has a cost larger than \(k\) it is useless to attempt to build a cheap sequence going though this set, and the exploration stops there. This way, a large number of sets will never be evaluated and a lot of computational time is saved this way.

Besides, some improvement is also made by “improving” the values found by \(c'\). Indeed, \(c'(S)\) is a lower bound on the cost of a sequence containing the set \(S\), but if all out-neighbors of \(S\) have a cost of \(c'(S) + 5\) then one knows that having \(S\) in a sequence means a total cost of at least \(c'(S) + 5\). For this reason, for each set \(S\) we store the value of \(c'(S)\), and replace it by \(\max (c'(S), \min_{\text{next}})\) (where \(\min_{\text{next}}\) is the minimum of the costs of the out-neighbors of \(S\)) once the costs of these out-neighbors have been evaluated by the algrithm.

Note

Because of its current implementation, this algorithm only works on graphs on less than 32 vertices. This can be changed to 64 if necessary, but 32 vertices already require 4GB of memory. Running it on 64 bits is not expected to be doable by the computers of the next decade \(:-D\)

Lower bound on the vertex separation

One can obtain a lower bound on the vertex separation of a graph in exponential time but small memory by computing once the cost of each set \(S\). Indeed, the cost of a sequence \(v_1, ..., v_n\) corresponding to sets \(\{v_1\}, \{v_1,v_2\}, ..., \{v_1,...,v_n\}\) is

\[\max c'(\{v_1\}),c'(\{v_1,v_2\}),...,c'(\{v_1,...,v_n\})\geq\max c'_1,...,c'_n\]

where \(c_i\) is the minimum cost of a set \(S\) on \(i\) vertices. Evaluating the \(c_i\) can take time (and in particular more than the previous exact algorithm), but it does not need much memory to run.

MILP formulation for the vertex separation

We describe below a mixed integer linear program (MILP) for determining an optimal layout for the vertex separation of \(G\), which is an improved version of the formulation proposed in [SP10]. It aims at building a sequence \(S_t\) of sets such that an ordering \(v_1, ..., v_n\) of the vertices correspond to \(S_0=\{v_1\}, S_2=\{v_1,v_2\}, ..., S_{n-1}=\{v_1,...,v_n\}\).

Variables:

• \(y_v^t\) – Variable set to 1 if \(v\in S_t\), and 0 otherwise. The order of \(v\) in the layout is the smallest \(t\) such that \(y_v^t==1\).
• \(u_v^t\) – Variable set to 1 if \(v\not \in S_t\) and \(v\) has an in-neighbor in \(S_t\). It is set to 0 otherwise.
• \(x_v^t\) – Variable set to 1 if either \(v\in S_t\) or if \(v\) has an in-neighbor in \(S_t\). It is set to 0 otherwise.
• \(z\) – Objective value to minimize. It is equal to the maximum over all step \(t\) of the number of vertices such that \(u_v^t==1\).

MILP formulation:

\[\begin{alignat}{2} \text{Minimize:} &z&\\ \text{Such that:} x_v^t &\leq x_v^{t+1}& \forall v\in V,\ 0\leq t\leq n-2\\ y_v^t &\leq y_v^{t+1}& \forall v\in V,\ 0\leq t\leq n-2\\ y_v^t &\leq x_w^t& \forall v\in V,\ \forall w\in N^+(v),\ 0\leq t\leq n-1\\ \sum_{v \in V} y_v^{t} &= t+1& 0\leq t\leq n-1\\ x_v^t-y_v^t&\leq u_v^t & \forall v \in V,\ 0\leq t\leq n-1\\ \sum_{v \in V} u_v^t &\leq z& 0\leq t\leq n-1\\ 0 \leq x_v^t &\leq 1& \forall v\in V,\ 0\leq t\leq n-1\\ 0 \leq u_v^t &\leq 1& \forall v\in V,\ 0\leq t\leq n-1\\ y_v^t &\in \{0,1\}& \forall v\in V,\ 0\leq t\leq n-1\\ 0 \leq z &\leq n& \end{alignat}\]

The vertex separation of \(G\) is given by the value of \(z\), and the order of vertex \(v\) in the optimal layout is given by the smallest \(t\) for which \(y_v^t==1\).

REFERENCES

[Bod98]

A partial k-arboretum of graphs with bounded treewidth, Hans L. Bodlaender, Theoretical Computer Science 209(1-2):1-45, 1998.

[Kin92]

The vertex separation number of a graph equals its path-width, Nancy G. Kinnersley, Information Processing Letters 42(6):345-350, 1992.

[SP10]

(1, 2) Lightpath Reconfiguration in WDM networks, Fernando Solano and Michal Pioro, IEEE/OSA Journal of Optical Communication and Networking 2(12):1010-1021, 2010.

AUTHORS

• Nathann Cohen (2011-10): Initial version and exact exponential algorithm
• David Coudert (2012-04): MILP formulation and tests functions

METHODS

class sage.graphs.graph_decompositions.vertex_separation.FastDigraph

Bases: object

x.__init__(...) initializes x; see help(type(x)) for signature

print_adjacency_matrix()

Displays the adjacency matrix of self.

sage.graphs.graph_decompositions.vertex_separation.is_valid_ordering(G, L)

Test if the linear vertex ordering \(L\) is valid for (di)graph \(G\).

A linear ordering \(L\) of the vertices of a (di)graph \(G\) is valid if all vertices of \(G\) are in \(L\), and if \(L\) contains no other vertex and no duplicated vertices.

INPUT:

• G – a Graph or a DiGraph.
• L – an ordered list of the vertices of G.

OUTPUT:

Returns True if \(L\) is a valid vertex ordering for \(G\), and False oterwise.

EXAMPLE:

Path decomposition of a cycle:

sage: from sage.graphs.graph_decompositions import vertex_separation
sage: G = graphs.CycleGraph(6)
sage: L = [u for u in G.vertices()]
sage: vertex_separation.is_valid_ordering(G, L)
True
sage: vertex_separation.is_valid_ordering(G, [1,2])
False

TEST:

Giving anything else than a Graph or a DiGraph:

sage: from sage.graphs.graph_decompositions import vertex_separation
sage: vertex_separation.is_valid_ordering(2, [])
Traceback (most recent call last):
...
ValueError: The input parameter must be a Graph or a DiGraph.

Giving anything else than a list:

sage: from sage.graphs.graph_decompositions import vertex_separation
sage: G = graphs.CycleGraph(6)
sage: vertex_separation.is_valid_ordering(G, {})
Traceback (most recent call last):
...
ValueError: The second parameter must be of type 'list'.

sage.graphs.graph_decompositions.vertex_separation.lower_bound(G)

Returns a lower bound on the vertex separation of \(G\)

INPUT:

• G – a digraph

OUTPUT:

A lower bound on the vertex separation of \(D\) (see the module’s documentation).

Note

This method runs in exponential time but has no memory constraint.

EXAMPLE:

On a circuit:

sage: from sage.graphs.graph_decompositions.vertex_separation import lower_bound
sage: g = digraphs.Circuit(6)
sage: lower_bound(g)
1

TEST:

Given anything else than a DiGraph:

sage: from sage.graphs.graph_decompositions.vertex_separation import lower_bound
sage: g = graphs.CycleGraph(5)
sage: lower_bound(g)
Traceback (most recent call last):
...
ValueError: The parameter must be a DiGraph.

sage.graphs.graph_decompositions.vertex_separation.path_decomposition(G, algorithm='exponential', verbose=False)

Returns the pathwidth of the given graph and the ordering of the vertices resulting in a corresponding path decomposition.

INPUT:

• G – a digraph
• algorithm – (default: "exponential") Specify the algorithm to use among
  • exponential – Use an exponential time and space algorithm. This algorithm only works of graphs on less than 32 vertices.
  • MILP – Use a mixed integer linear programming formulation. This algorithm has no size restriction but could take a very long time.
• verbose (boolean) – whether to display information on the computations.

OUTPUT:

A pair (cost, ordering) representing the optimal ordering of the vertices and its cost.

Note

Because of its current implementation, this exponential algorithm only works on graphs on less than 32 vertices. This can be changed to 54 if necessary, but 32 vertices already require 4GB of memory.

See also

• Graph.treewidth() – computes the treewidth of a graph

EXAMPLE:

The vertex separation of a cycle is equal to 2:

sage: from sage.graphs.graph_decompositions.vertex_separation import path_decomposition
sage: g = graphs.CycleGraph(6)
sage: pw, L = path_decomposition(g); pw
2
sage: pwm, Lm = path_decomposition(g, algorithm = "MILP"); pwm
2

TEST:

Given anything else than a Graph:

sage: from sage.graphs.graph_decompositions.vertex_separation import path_decomposition
sage: g = digraphs.Circuit(6)
sage: path_decomposition(g)
Traceback (most recent call last):
...
ValueError: The parameter must be a Graph.

sage.graphs.graph_decompositions.vertex_separation.test_popcount()

Correction test for popcount32.

EXAMPLE:

sage: from sage.graphs.graph_decompositions.vertex_separation import test_popcount
sage: test_popcount() # not tested

sage.graphs.graph_decompositions.vertex_separation.vertex_separation(G, verbose=False)

Returns an optimal ordering of the vertices and its cost for vertex-separation.

INPUT:

• G – a digraph
• verbose (boolean) – whether to display information on the computations.

OUTPUT:

A pair (cost, ordering) representing the optimal ordering of the vertices and its cost.

Note

Because of its current implementation, this algorithm only works on graphs on less than 32 vertices. This can be changed to 54 if necessary, but 32 vertices already require 4GB of memory.

EXAMPLE:

The vertex separation of a circuit is equal to 1:

sage: from sage.graphs.graph_decompositions.vertex_separation import vertex_separation
sage: g = digraphs.Circuit(6)
sage: vertex_separation(g)
(1, [0, 1, 2, 3, 4, 5])

TEST:

Given anything else than a DiGraph:

sage: from sage.graphs.graph_decompositions.vertex_separation import lower_bound
sage: g = graphs.CycleGraph(5)
sage: lower_bound(g)
Traceback (most recent call last):
...
ValueError: The parameter must be a DiGraph.

Graphs with non-integer vertices:

sage: from sage.graphs.graph_decompositions.vertex_separation import vertex_separation
sage: D=digraphs.DeBruijn(2,3)
sage: vertex_separation(D)
(2, ['000', '001', '100', '010', '101', '011', '110', '111'])

sage.graphs.graph_decompositions.vertex_separation.vertex_separation_MILP(G, integrality=False, solver=None, verbosity=0)

Computes the vertex separation of \(G\) and the optimal ordering of its vertices using an MILP formulation.

This function uses a mixed integer linear program (MILP) for determining an optimal layout for the vertex separation of \(G\). This MILP is an improved version of the formulation proposed in [SP10]. See the module's documentation for more details on this MILP formulation.

INPUTS:

• G – a DiGraph
• integrality – (default: False) Specify if variables \(x_v^t\) and \(u_v^t\) must be integral or if they can be relaxed. This has no impact on the validity of the solution, but it is sometimes faster to solve the problem using binary variables only.
• solver – (default: None) Specify a Linear Program (LP) solver to be used. If set to None, the default one is used. For more information on LP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.
• verbose – integer (default: 0). Sets the level of verbosity. Set to 0 by default, which means quiet.

OUTPUT:

A pair (cost, ordering) representing the optimal ordering of the vertices and its cost.

EXAMPLE:

Vertex separation of a De Bruijn digraph:

sage: from sage.graphs.graph_decompositions import vertex_separation
sage: G = digraphs.DeBruijn(2,3)
sage: vs, L = vertex_separation.vertex_separation_MILP(G); vs
2
sage: vs == vertex_separation.width_of_path_decomposition(G, L)
True
sage: vse, Le = vertex_separation.vertex_separation(G); vse
2

The vertex separation of a circuit is 1:

sage: from sage.graphs.graph_decompositions import vertex_separation
sage: G = digraphs.Circuit(6)
sage: vs, L = vertex_separation.vertex_separation_MILP(G); vs
1

TESTS:

Comparison with exponential algorithm:

sage: from sage.graphs.graph_decompositions import vertex_separation
sage: for i in range(10):
...       G = digraphs.RandomDirectedGNP(10, 0.2)
...       ve, le = vertex_separation.vertex_separation(G)
...       vm, lm = vertex_separation.vertex_separation_MILP(G)
...       if ve != vm:
...          print "The solution is not optimal!"

Comparison with different values of the integrality parameter:

sage: from sage.graphs.graph_decompositions import vertex_separation
sage: for i in range(10):  # long time (11s on sage.math, 2012)
....:     G = digraphs.RandomDirectedGNP(10, 0.2)
....:     va, la = vertex_separation.vertex_separation_MILP(G, integrality=False)
....:     vb, lb = vertex_separation.vertex_separation_MILP(G, integrality=True)
....:     if va != vb:
....:        print "The integrality parameter changes the result!"

Giving anything else than a DiGraph:

sage: from sage.graphs.graph_decompositions import vertex_separation
sage: vertex_separation.vertex_separation_MILP([])
Traceback (most recent call last):
...
ValueError: The first input parameter must be a DiGraph.

sage.graphs.graph_decompositions.vertex_separation.width_of_path_decomposition(G, L)

Returns the width of the path decomposition induced by the linear ordering \(L\) of the vertices of \(G\).

If \(G\) is an instance of Graph, this function returns the width \(pw_L(G)\) of the path decomposition induced by the linear ordering \(L\) of the vertices of \(G\). If \(G\) is a DiGraph, it returns instead the width \(vs_L(G)\) of the directed path decomposition induced by the linear ordering \(L\) of the vertices of \(G\), where

\[\begin{split}vs_L(G) & = \max_{0\leq i< |V|-1} | N^+(L[:i])\setminus L[:i] |\\ pw_L(G) & = \max_{0\leq i< |V|-1} | N(L[:i])\setminus L[:i] |\\\end{split}\]

INPUT:

• G – a Graph or a DiGraph
• L – a linear ordering of the vertices of G

EXAMPLES:

Path decomposition of a cycle:

sage: from sage.graphs.graph_decompositions import vertex_separation
sage: G = graphs.CycleGraph(6)
sage: L = [u for u in G.vertices()]
sage: vertex_separation.width_of_path_decomposition(G, L)
2

Directed path decomposition of a circuit:

sage: from sage.graphs.graph_decompositions import vertex_separation
sage: G = digraphs.Circuit(6)
sage: L = [u for u in G.vertices()]
sage: vertex_separation.width_of_path_decomposition(G, L)
1

TESTS:

Path decomposition of a BalancedTree:

sage: from sage.graphs.graph_decompositions import vertex_separation
sage: G = graphs.BalancedTree(3,2)
sage: pw, L = vertex_separation.path_decomposition(G)
sage: pw == vertex_separation.width_of_path_decomposition(G, L)
True
sage: L.reverse()
sage: pw == vertex_separation.width_of_path_decomposition(G, L)
False

Directed path decomposition of a circuit:

sage: from sage.graphs.graph_decompositions import vertex_separation
sage: G = digraphs.Circuit(8)
sage: vs, L = vertex_separation.vertex_separation(G)
sage: vs == vertex_separation.width_of_path_decomposition(G, L)
True
sage: L = [0,4,6,3,1,5,2,7]
sage: vs == vertex_separation.width_of_path_decomposition(G, L)
False

Giving a wrong linear ordering:

sage: from sage.graphs.graph_decompositions import vertex_separation
sage: G = Graph()
sage: vertex_separation.width_of_path_decomposition(G, ['a','b'])
Traceback (most recent call last):
...
ValueError: The input linear vertex ordering L is not valid for G.