Saturday, 28 November 2009

graph theory - Combining DAGs into an acyclic tournament

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.

No comments:

Post a Comment