Combining DAGs into an acyclic tournament - MathOverflow

Combining DAGs into an acyclic tournament

2010-06-23T16:21:02Z

I have a vertex set $V$ and a collection of disjoint arc sets $E_1, \ldots, E_t$ such that $$G_i = (V, E_i),\quad\forall i = 1, \ldots t,$$ are directed acyclic graphs (DAGs) and $$G = (V, E_1 \cup \ldots \cup E_t)$$ is a tournament. We note that the individual DAGs may be disconnected and that $G$ may not be acyclic. However, suppose there exists a bipartition of the arc set indices $\alpha \cup \beta$ such that $$G' = (V, E_\alpha\cup E_\beta^T)$$ is an acyclic tournament where $$E_\alpha = E_{\alpha_1} \cup \ldots \cup E_{\alpha_p}$$ and $$E_\beta = E_{\beta_1} \cup \ldots \cup E_{\beta_q}$$ and $E^T$ is the transpose of $E$ (all the arcs are reversed).

Does anybody know of any results relating to the above? In particular, does anybody know of a method of determining a bipartition $\alpha \cup \beta$, given that at least one exists, other that enumerating all possible bipartitions and checking if the resulting $G'$ is acyclic?

Answer by Swapnil Bhatia for Combining DAGs into an acyclic tournament

2010-06-24T06:14:08Z

Since your question is somewhat open ended, here's an observation, although it doesn't go anywhere yet.

A 2SAT instance is a decision problem in which given a set of variables $V$ and a formula comprising a conjunction of clauses over them, each clause being distinct and containing exactly two distinct literals, one wishes to know whether there is a truth assignment to the variables that makes the formula true.

Each 2SAT instance induces a digraph on $V \cup \overline{V}$: an arc from $u$ to $v$ exists if there is a clause $\overline{u} \lor v$.

Conjecture: If this digraph is a DAG, then the 2SAT instance must be satisfiable. If the 2SAT instance is satisfiable then the digraph must have exactly one variable in each of its strongly connected components.

Moreover, such ``2SAT digraphs'' are transposable: reversing their arcs gives a digraph isomorphic to the original.

Your question could be interpreted as being about a collection of 2SAT instances where one is allowed to negate the literals in all the clauses of any instance.

Answer by Nathann Cohen for Combining DAGs into an acyclic tournament

2010-08-19T08:46:55Z

I would use Integer Linear Programming. It may possibly be faster than enumerating all the possibilities, but anyway writing such a program takes at most 10 minutes, so it is definitely worth a try.

Comment 1 - Of course, it tells you nothing about the computing time, it "may" be useful in practice, that's all

Comment 2 - I advise you to try it using sagemath, as I wrote the LP interface myself and know it does not take more than twenty (uncommented) lines :-)

Nathann

Answer by Tracy Hall for Combining DAGs into an acyclic tournament

2010-08-19T23:03:32Z

The problem you pose, of finding a bipartition if one exists, is of polynomially equivalent difficulty to the decision problem of determining whether a bipartition exists. The decision problem in turn is NP-complete, by reduction from 3-SAT (and the fact that a solution is easily checked.)

Given an instance of 3-SAT with $n$ clauses, we construct a family of DAGs on $4n$ vertices. All edges in the complement of $n$ disjoint $4$-cycles will be singleton DAGs. One "universal" DAG consists of a single edge in each $4$-cycle, and establishes a potential (forbidden) orientation on each $4$-cycle. Then for every variable in the 3-SAT instance we define a DAG consisting of an edge in each of the $4$-cycles corresponding to the clauses in which that variable appears, with the direction depending on whether the variable appears negated in the clause, in such a way that the forbidden orientation imposed by the universal DAG is achieved in a given $4$-cycle if and only if no literal in the corresponding clause is true, where a variable is considered true when its DAG lies on the same side of the bipartition as the universal DAG and is considered false otherwise. Then an acyclic bipartition of the DAGs exists if and only if the instance of 3-SAT has a satisfying assignment.