Comparability and permutation graphs

Comparability and permutation graphs

This module implements method related to Comparability graphs and Permutation graphs, that is, for the moment, only recognition algorithms.

Most of the information found here can alo be found in [Cleanup] or [ATGA].

The following methods are implemented in this module

is_comparability_MILP() Tests whether the graph is a comparability graph (MILP)
greedy_is_comparability() Tests whether the graph is a comparability graph (greedy algorithm)
greedy_is_comparability_with_certificate() Tests whether the graph is a comparability graph and returns certificates (greedy algorithm)
is_comparability() Tests whether the graph is a comparability graph
is_permutation() Tests whether the graph is a permutation graph.
is_transitive() Tests whether the digraph is transitive.

Author:

  • Nathann Cohen 2012-04

Graph classes

Comparability graphs

A graph is a comparability graph if it can be obtained from a poset by adding an edge between any two elements that are comparable. Co-comparability graph are complements of such graphs, i.e. graphs built from a poset by adding an edge between any two incomparable elements.

For more information on comparablity graphs, see the corresponding wikipedia page

Permutation graphs

Definitions:

  • A permutation \(\pi = \pi_1\pi_2\dots\pi_n\) defines a graph on \(n\) vertices such that \(i\sim j\) when \(\pi\) reverses \(i\) and \(j\) (i.e. when \(i<j\) and \(\pi_j < \pi_i\). A graph is a permutation graph whenever it can be built through this construction.
  • A graph is a permutation graph if it can be build from two parallel lines are the intersection graph of segments intersecting both lines.
  • A graph is a permutation graph if it is both a comparability graph and a co-comparability graph.

For more information on permutation graphs, see the corresponding wikipedia page.

Recognition algorithm for comparability graphs

Greedy algorithm

This algorithm attempts to build a transitive orientation of a given graph \(G\), that is an orientation \(D\) such that for any directed \(uv\)-path of \(D\) there exists in \(D\) an edge \(uv\). This already determines a notion of equivalence between some edges of \(G\) :

In \(G\), two edges \(uv\) and \(uv'\) (incident to a common vertex \(u\)) such that \(vv'\not\in G\) need necessarily be oriented the same way (that is that they should either both leave or both enter \(u\)). Indeed, if one enters \(G\) while the other leaves it, these two edges form a path of length two, which is not possible in any transitive orientation of \(G\) as \(vv'\not\in G\).

Hence, we can say that in this case a directed edge \(uv\) is equivalent to a directed edge \(uv'\) (to mean that if one belongs to the transitive orientation, the other one must be present too) in the same way that \(vu\) is equivalent to \(v'u\). We can thus define equivalence classes on oriented edges, to represent set of edges that imply each other. We can thus define \(C^G_{uv}\) to be the equivalence class in \(G\) of the oriented edge \(uv\).

Of course, if there exists a transitive orientation of a graph \(G\), then no edge \(uv\) implies its contrary \(vu\), i.e. it is necessary to ensure that \(\forall uv\in G, vu\not\in C^G_{uv}\). The key result on which the greedy algorithm is built is the following (see [Cleanup]):

Theorem – The following statements are equivalent :

  • \(G\) is a comparability graph
  • \(\forall uv\in G, vu\not\in C^G_{uv}\)
  • The edges of \(G\) can be partitionned into \(B_1,...,B_k\) where \(B_i\) is the equivalence class of some oriented edge in \(G-B_1-\dots-B_{i-1}\)

Hence, ensuring that a graph is a comparability graph can be done by checking that no equivalence class is contradictory. Building the orientation, however, requires to build equivalence classes step by step until an orientation has been found for all of them.

Mixed Integer Linear Program

A MILP formulation is available to check the other methods for correction. It is easily built :

To each edge are associated two binary variables (one for each possible direction). We then ensure that each triangle is transitively oriented, and that each pair of incident edges \(uv, uv'\) such that \(vv'\not\in G\) do not create a 2-path.

Here is the formulation:

\[\begin{split}\mbox{Maximize : }&\mbox{Nothing}\\ \mbox{Such that : }&\\ &\forall uv\in G\\ &\cdot o_{uv}+o_{vu} = 1\\ &\forall u\in G, \forall v,v'\in N(v)\text{ such that }vv'\not\in G\\ &\cdot o_{uv} + o_{v'u} - o_{v'v} \leq 1\\ &\cdot o_{uv'} + o_{vu} - o_{vv'} \leq 1\\ &\forall u\in G, \forall v,v'\in N(v)\text{ such that }vv'\in G\\ &\cdot o_{uv} + o_{v'u} \leq 1\\ &\cdot o_{uv'} + o_{vu} \leq 1\\ &o_{uv}\text{ is a binary variable}\\\end{split}\]

Note

The MILP formulation is usually much slower than the greedy algorithm. This MILP has been implemented to check the results of the greedy algorithm that has been implemented to check the results of a faster algorithm which has not been implemented yet.

Certificates

Comparability graphs

The yes-certificates that a graph is a comparability graphs are transitive orientations of it. The no-certificates, on the other hand, are odd cycles of such graph. These odd cycles have the property that around each vertex \(v\) of the cycle its two incident edges must have the same orientation (toward \(v\), or outward \(v\)) in any transitive orientation of the graph. This is impossible whenever the cycle has odd length. Explanations are given in the “Greedy algorithm” part of the previous section.

Permutation graphs

Permutation graphs are precisely the intersection of comparability graphs and co-comparability graphs. Hence, negative certificates are precisely negative certificates of comparability or co-comparability. Positive certificates are a pair of permutations that can be used through PermutationGraph() (whose documentation says more about what these permutations represent).

Implementation details

Test that the equivalence classes are not self-contradictory

This is done by a call to Graph.is_bipartite(), and here is how :

Around a vertex \(u\), any two edges \(uv, uv'\) such that \(vv'\not\in G\) are equivalent. Hence, the equivalence classe of edges around a vertex are precisely the connected components of the complement of the graph induced by the neighbors of \(u\).

In each equivalence class (around a given vertex \(u\)), the edges should all have the same orientation, i.e. all should go toward \(u\) at the same time, or leave it at the same time. To represent this, we create a graph with vertices for all equivalent classes around all vertices of \(G\), and link \((v, C)\) to \((u, C')\) if \(u\in C\) and \(v\in C'\).

A bipartite coloring of this graph with colors 0 and 1 tells us that the edges of an equivalence class \(C\) around \(u\) should be directed toward \(u\) if \((u, C)\) is colored with \(0\), and outward if \((u, C)\) is colored with \(1\).

If the graph is not bipartite, this is the proof that some equivalence class is self-contradictory !

Note

The greedy algorithm implemented here is just there to check the correction of more complicated ones, and it is reaaaaaaaaaaaalllly bad whenever you look at it with performance in mind.

References

[ATGA]Advanced Topics in Graph Algorithms, Ron Shamir, http://www.cs.tau.ac.il/~rshamir/atga/atga.html
[Cleanup](1, 2) A cleanup on transitive orientation, Orders, Algorithms, and Applications, 1994, Simon, K. and Trunz, P., ftp://ftp.inf.ethz.ch/doc/papers/ti/ga/ST94.ps.gz

Methods

sage.graphs.comparability.greedy_is_comparability(g, no_certificate=False, equivalence_class=False)

Tests whether the graph is a comparability graph (greedy algorithm)

This method only returns no-certificates.

To understand how this method works, please consult the documentation of the comparability module.

INPUT:

  • no_certificate – whether to return a no-certificate when the graph is not a comparability graph. This certificate is an odd cycle of edges, each of which implies the next. It is set to False by default.
  • equivalence_class – whether to return an equivalence class if the graph is a comparability graph.

OUTPUT:

  • If the graph is a comparability graph and no_certificate = False, this method returns True or (True, an_equivalence_class) according to the value of equivalence_class.
  • If the graph is not a comparability graph, this method returns False or (False, odd_cycle) according to the value of no_certificate.

EXAMPLE:

The Petersen Graph is not transitively orientable:

sage: from sage.graphs.comparability import greedy_is_comparability as is_comparability
sage: g = graphs.PetersenGraph()
sage: is_comparability(g)
False
sage: is_comparability(g, no_certificate = True)
(False, [9, 6, 1, 0, 4, 9])

But the Bull graph is:

sage: g = graphs.BullGraph()
sage: is_comparability(g)
True
sage.graphs.comparability.greedy_is_comparability_with_certificate(g, certificate=False)

Tests whether the graph is a comparability graph and returns certificates(greedy algorithm).

This method can return certificates of both yes and no answers.

To understand how this method works, please consult the documentation of the comparability module.

INPUT:

  • certificate (boolean) – whether to return a certificate. Yes-answers the certificate is a transitive orientation of \(G\), and a no certificates is an odd cycle of sequentially forcing edges.

EXAMPLE:

The 5-cycle or the Petersen Graph are not transitively orientable:

sage: from sage.graphs.comparability import greedy_is_comparability_with_certificate as is_comparability
sage: is_comparability(graphs.CycleGraph(5), certificate = True)
(False, [3, 4, 0, 1, 2, 3])
sage: g = graphs.PetersenGraph()
sage: is_comparability(g)
False
sage: is_comparability(g, certificate = True)
(False, [9, 6, 1, 0, 4, 9])

But the Bull graph is:

sage: g = graphs.BullGraph()
sage: is_comparability(g)
True
sage: is_comparability(g, certificate = True)
(True, Digraph on 5 vertices)
sage: is_comparability(g, certificate = True)[1].is_transitive()
True
sage.graphs.comparability.is_comparability(g, algorithm='greedy', certificate=False, check=True)

Tests whether the graph is a comparability graph

INPUT:

  • algorithm – chose the implementation used to do the test.
    • "greedy" – a greedy algorithm (see the documentation of the comparability module).
    • "MILP" – a Mixed Integer Linear Program formulation of the problem. Beware, for this implementation is unable to return negative certificates ! When certificate = True, negative certificates are always equal to None. True certificates are valid, though.
  • certificate (boolean) – whether to return a certificate. Yes-answers the certificate is a transitive orientation of \(G\), and a no certificates is an odd cycle of sequentially forcing edges.
  • check (boolean) – whether to check that the yes-certificates are indeed transitive. As it is very quick compared to the rest of the operation, it is enabled by default.

EXAMPLE:

sage: from sage.graphs.comparability import is_comparability
sage: g = graphs.PetersenGraph()
sage: is_comparability(g)
False
sage: is_comparability(graphs.CompleteGraph(5), certificate = True)
(True, Digraph on 5 vertices)

TESTS:

Let us ensure that no exception is raised when we go over all small graphs:

sage: from sage.graphs.comparability import is_comparability
sage: [len([g for g in graphs(i) if is_comparability(g, certificate = True)[0]]) for i in range(7)]
[1, 1, 2, 4, 11, 33, 144]
sage.graphs.comparability.is_comparability_MILP(g, certificate=False)

Tests whether the graph is a comparability graph (MILP)

INPUT:

  • certificate (boolean) – whether to return a certificate for yes instances. This method can not return negative certificates.

EXAMPLE:

The 5-cycle or the Petersen Graph are not transitively orientable:

sage: from sage.graphs.comparability import is_comparability_MILP as is_comparability
sage: is_comparability(graphs.CycleGraph(5), certificate = True)
(False, None)
sage: g = graphs.PetersenGraph()
sage: is_comparability(g, certificate = True)
(False, None)

But the Bull graph is:

sage: g = graphs.BullGraph()
sage: is_comparability(g)
True
sage: is_comparability(g, certificate = True)
(True, Digraph on 5 vertices)
sage: is_comparability(g, certificate = True)[1].is_transitive()
True
sage.graphs.comparability.is_permutation(g, algorithm='greedy', certificate=False, check=True)

Tests whether the graph is a permutation graph.

For more information on permutation graphs, refer to the documentation of the comparability module.

INPUT:

  • algorithm – chose the implementation used for the subcalls to is_comparability().
    • "greedy" – a greedy algorithm (see the documentation of the comparability module).
    • "MILP" – a Mixed Integer Linear Program formulation of the problem. Beware, for this implementation is unable to return negative certificates ! When certificate = True, negative certificates are always equal to None. True certificates are valid, though.
  • certificate (boolean) – whether to return a certificate for the answer given. For True answers the certificate is a permutation, for False answers it is a no-certificate for the test of comparability or co-comparability.
  • check (boolean) – whether to check that the permutations returned indeed create the expected Permutation graph. Pretty cheap compared to the rest, hence a good investment. It is enabled by default.

Note

As the True certificate is a Permutation object, the segment intersection model of the permutation graph can be visualized through a call to Permutation.show.

EXAMPLE:

A permutation realizing the bull graph:

sage: from sage.graphs.comparability import is_permutation
sage: g = graphs.BullGraph()
sage: _ , certif = is_permutation(g, certificate = True)
sage: h = graphs.PermutationGraph(*certif)
sage: h.is_isomorphic(g)
True

Plotting the realization as an intersection graph of segments:

sage: true, perm = is_permutation(g, certificate = True)
sage: p1 = Permutation([nn+1 for nn in perm[0]])
sage: p2 = Permutation([nn+1 for nn in perm[1]])
sage: p = p2 * p1.inverse()
sage: p.show(representation = "braid")

TESTS:

Trying random permutations, first with the greedy algorithm:

sage: from sage.graphs.comparability import is_permutation
sage: for i in range(20):
...       p = Permutations(10).random_element()
...       g1 = graphs.PermutationGraph(p)
...       isit, certif = is_permutation(g1, certificate = True)
...       if not isit:
...          print "Something is wrong here !!"
...          break
...       g2 = graphs.PermutationGraph(*certif)
...       if not g1.is_isomorphic(g2):
...          print "Something is wrong here !!"
...          break

Then with MILP:

sage: from sage.graphs.comparability import is_permutation
sage: for i in range(20):
...       p = Permutations(10).random_element()
...       g1 = graphs.PermutationGraph(p)
...       isit, certif = is_permutation(g1, algorithm = "MILP", certificate = True)
...       if not isit:
...          print "Something is wrong here !!"
...          break
...       g2 = graphs.PermutationGraph(*certif)
...       if not g1.is_isomorphic(g2):
...          print "Something is wrong here !!"
...          break
sage.graphs.comparability.is_transitive(g, certificate=False)

Tests whether the digraph is transitive.

A digraph is transitive if for any pair of vertices \(u,v\in G\) linked by a \(uv\)-path the edge \(uv\) belongs to \(G\).

INPUT:

  • certificate – whether to return a certificate for negative answers.
    • If certificate = False (default), this method returns True or False according to the graph.
    • If certificate = True, this method either returns True answers or yield a pair of vertices \(uv\) such that there exists a \(uv\)-path in \(G\) but \(uv\not\in G\).

EXAMPLE:

sage: digraphs.Circuit(4).is_transitive()
False
sage: digraphs.Circuit(4).is_transitive(certificate = True)
(0, 2)
sage: digraphs.RandomDirectedGNP(30,.2).is_transitive()
False
sage: digraphs.DeBruijn(5,2).is_transitive()
False
sage: digraphs.DeBruijn(5,2).is_transitive(certificate = True)
('00', '10')
sage: digraphs.RandomDirectedGNP(20,.2).transitive_closure().is_transitive()
True