Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
If a bipartition exists it may not be unique, the worst case being when every arc set is a singleton. –  Tracy Hall Aug 19 '10 at 22:22
    
Thank you -- I edited the last two lines to allow for this. –  Martin Harrigan Aug 22 '10 at 10:06
    
So the real-life analogy or the source of the graph which I see here is a set of bus routes or a set of subway routes from which you can pick, and the desire to make an acyclic tournament over the entirety of the bus or subway stops. Is that why you know that at least one bipartition exists? Because for each route set $E_j$, there is the return bus which traverses the directed path in $G_j=(V,E_j^T)$ using the route set $E_k=E_j^T$ ? –  sleepless in beantown Sep 5 '10 at 20:52
add comment

3 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
But in any instance of the problem I know that at least one such bipartition exists. The answer to the decision problem is always YES. I was hoping that this would make finding such a bipartition easier. –  Martin Harrigan Aug 22 '10 at 10:11
    
@Martin Harrigan: The reduction also shows that not every instance of your problem has a solution. Apply the reduction to any unsatisfiable 3-CNF formulas. Of course, it is possible that all the instances you are interested in have a solution. However, a mere promise that a solution exists does not make the problem easier. (more) –  Tsuyoshi Ito Sep 5 '10 at 20:09
    
@Martin Harrigan: (cont’d) Suppose there is a t(n)-time algorithm which finds a solution as long as one exists, where t(n) is a polynomial and n is the input length. Now suppose you have an instance of size n such that you do not know whether a solution exists or not. How can you make a use of the algorithm to find out whether a solution exists or not? (more) –  Tsuyoshi Ito Sep 5 '10 at 20:09
    
@Martin Harrigan: (cont’d) The answer is to run the algorithm on this instance anyway. If the algorithm does not terminate in time t(n), you can conclude that the instance does not have a solution. If it terminates in time t(n), it outputs something, which is always a bit string. You can check whether that output is indeed a (correctly encoded) solution or not. It is easy to see that the output is a solution if and only if the instance has a solution. (more) –  Tsuyoshi Ito Sep 5 '10 at 20:09
    
@Martin Harrigan: (cont’d) To summarize, unless P=NP, we cannot hope for a polynomial-time algorithm which finds a solution to every instance that has a solution. However, this does not rule out a polynomial-time algorithm which works for some instances that have a solution. If the cases you are interested in satisfy some additional conditions which guarantee the existence of a solution, those additional conditions (rather than the mere existence of a solution) might be useful to get a polynomial-time algorithm. –  Tsuyoshi Ito Sep 5 '10 at 20:11
show 1 more comment

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.

share|improve this answer
2  
It is known that 2SAT instances are satisfiable iff every variable belongs to a different strongly connected component of the implication graph (the graph you describe) from its complement. That's weaker than having one variable per scc, though. See Aspvall, Bengt; Plass, Michael F.; Tarjan, Robert E. (1979), "A linear-time algorithm for testing the truth of certain quantified boolean formulas", Information Processing Letters 8 (3): 121–123. However, the question is not really a 2SAT problem because the DAGs could be pairwise compatible but still not have a joint acyclic orientation. –  David Eppstein Jun 24 '10 at 6:23
    
Yes, I think the DAGs need to be three-wise compatible in order to have a joint acyclic orientation. –  Martin Harrigan Jun 24 '10 at 9:07
1  
Actually $k$-wise compatible isn't sufficient for any fixed $k$. The reduction from 3-SAT I posted has an obvious generalization to $k$-SAT, and given an instance of $k$-SAT with distinct variables in each clause but no satisfying assignment, the DAGs in the corresponding system are $k$-wise compatible, but no bipartition gives an acyclic tournament. –  Tracy Hall Aug 19 '10 at 23:14
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.