Parity Constrained Acyclic Orientations

Finding acyclic orientations of an undirected graph is easy. Basically, every total ordering of the node set specifies one. However, if we prescribe the parity of  outdegree of each node, then we get a much more elusive problem. Formally, we look for a polynomial time algorithm for the following problem:

P1: Given an undirected graph G(V,E) and a subset T of its nodes, find an acyclic orientation of G such that the outdegree of each node v is odd if and only if it is in T. (We call such an orientation T-odd.)

An important special case is when we look for “odd acyclic orientations“:

P2: Given an undirected graph G(V,E), decide whether there is an acyclic orientation of G such that the outdegree of each but one node is odd.

Obviously, every acyclic orientation has at least one “sink”: a node without outgoing arcs. The decision problem addressed here is whether we can orient an undirected graph such that there is only one sink and all other nodes have an odd number of outgoing arcs.

As far as I know, it is still an open question, whether this decision problem has a deterministic polynomial time solution.

It is a relatively easy exercise to solve the more general problem P1 using an oracle for this special case P2. (That is finding T-odd acyclic orientations using an oracle for deciding whether a given graph admits an odd-acyclic orientation).

Although it is unclear whether there is a polynomial algorithm for P2, I am going to give here a simple randomized polynomial time algorithm. In fact I am reiterating the arguments given in my thesis, but in order to make it more concrete, I also decided to write a short sage program to demonstrate its working.

The basic idea is that a graph admits an odd acyclic orientation if and only if its cocycle matroid has a so called “odd ear-decomposition”. The understanding of this notion is not essential here. What we care about is that there is a simple algebraic characterization of binary matroids admitting odd ear decompositions and therefore for odd acyclic orientations when applied to the cocycle matroid of graphs.

The characterization is the following: let us assume that is binary matrix with minimum number of rows the column-space of which defines our matroid.  Let us associate some polynomials over GF(2) with the columns of such that for each row the values associated with the nonzero entries sums to zero.  Let us now form the matrix in which each column of is multiplied by associated polynomial.

1. The column matroid of allows an odd ear decomposition
2. Matrix  is non-singular

Our theorem (with Balazs Szegedy) states that statement 1. implies 2. for any choice of polynomials as long as the above conditions (which is equivalent to the condition that the diagonal of entries of should be all zeros) holds. Moreover, if the polynomials are chosen “generic” enough (and here we need to look at only linear polynomials) then the reverse implication is also true. That is, for the right choice of polynomials, the above two statements are equivalent.

This provides us with the following simple way to decide the existence of an odd-acyclic orientation of graph G:

1. Chose a spanning tree T of G.
2. Associate independent indeterminates with each edge e of T
3. Each other edge of G forms a unique cycle in T. Set for all edges in G, but not in T.
4. Let be a matrix of the cocycle matroid of G. Let be the matrix where each column labeled by is multiplied by the (linear) polynomial
5. G admits an odd acyclic orientation if and only if is non-singular.

In fact, one can prove that the corank of equals to the minimum number of edges to be deleted to get a graph admitting an odd acyclic orientation.

Why is not this a polynomial time procedure? Unfortunately there is no known way to perform step 5 in deterministic polynomial time. Here is where we can resort to a randomized polynomial algorithm: if we go to a suitably large extension field of GF(2): some GF(), and substitute the indeterminates by random field elements, then the rank of the resulting matrix will “almost always” be the same as that of the original one. That is, the probability of a false negative can be made arbitrarily small by chosing larger fields. (Cf. Schwartz-Zippel lemma)

Now let us come to the meat of this posting and give a simple sage script the implements the above algorithm. In order to keep the implementation simple, I just decided to use a field which should be large enough for demonstration purposes: GF(65536). Of course a proper implementation should be parametrized by the desired probability and chose the field and/or number of iterations accordingly.

The script can also be downloaded from here, but let us go through the commented version:

We are to define a function that computes the minimum number of edges needed to be deleted in order to get a graph admitting an odd acyclic orientation.

def MinEdgesToOddAcyclic(G):

Start with computing a minimum spanning tree:

 T = Graph()
 for e in G.min_spanning_tree():
   T.add_edge(e[0],e[1])

Weight the edges of T by random elements of GF(65536). Note that we store the weight for both orientation of the edge. This is a just an implementation trick to simplify the code.

  k.<a>=GF(65536,'a')
  tmap = dict()
  for e in T.edges():
    w = k.random_element()
    tmap[e] = w
    tmap[(e[1],e[0],None)] = w

Create an empty matrix of the correct size (n equals to the corank of G). We also create a unique column index for each edge of G. Note that we use the same trick to store the same index for the backward and forward version of each edge. Our matrix “M” will be matrix of the informal description.

  n = G.num_edges()-T.num_edges()
  M = MatrixSpace(k,n,G.num_edges())()
  edge_index = dict()
  count = 0
  for e in G.edges():
    edge_index[e]=count
    edge_index[(e[1],e[0],None)]=count
    count = count + 1

Process the fundamental cycle of (x,y) which is supposed to be an edge of G not in T. The corresponding row index in the matrix is i.

  def addCycle(i,x,y):
    last = -1
    sum = k.zero()
    for n in T.shortest_path(x,y):
      if last>=0:
        w = tmap[(last,n,None)]
        sum = sum + w
        M[i,edge_index[(last,n,None)]]=w
      last = n
    M[i,edge_index[(x,y,None)]]=sum

Enter the rows corresponding to all fundamental cycles to the matrix:

  cnt = 0
  for e in G.edges():
    if not( (e[0],e[1],None) in tmap ):
      addCycle(cnt,e[0],e[1])
      cnt = cnt + 1

Finally, compute the corank of :

return n-(M*M.transpose()).rank()

This is the minimum number of edges needed to be deleted from G to get a Graph admitting an odd acyclic orientation. The full source code can be downloaded here.

An example to use the above code: the following code prints all connected graphs on 6 nodes that need at least two edges deleted in order to admit an odd acyclic orientation:

for g in graphs(6):
  if g.is_connected():
    r = MinEdgesToOddAcyclic(g)
    if r > 1:
      g.show()
      print r