1
$\begingroup$

Given a CNF SAT formula, we can turn it into a Hamiltonian graph, which is Hamiltonian iff the formula is satisfiable. Now, we can transform the CNF formula into a DNF one. My question is, can the graph be transformed into a "DNF" graph, from which the property of satisfiability or Hamiltonian-ness can be observed obviously?

$\endgroup$

1 Answer 1

0
$\begingroup$

Yes. DNF-SAT is simple to decide because you only need do a linear search for a clause that does not contain a literal and its negation. Converting a CNF formula to DNF can be done by choosing a literal from each CNF clause and combining them to produce a DNF clause, then repeating this process with different literals until all possible DNF clauses have been created.

Similarly, a graph with an obvious way to decide the Hamiltonian path question would be the decomposition of the original graph into a set of graphs containing at least one simple and connected degree-2 graph that contains all the vertices in the original graph. Given a graph G with a set of vertices V and set of edges E, any Hamiltonian path must have |V| - 1 edges. A "DNF" Hamiltonian graph G would be the set of graphs produced by removing all the combinations of edges that leave only |V| - 1 edges. Somewhere among these graphs will be a simple and connected degree-2 graph that contains all the vertices in the original graph G if the original graph contained a Hamiltonian path. As with DNF-SAT, you can search for this satisfying graph in linear time.

$\endgroup$
2
  • $\begingroup$ You mean generating all subsets of vertices? This is unlike the manipulating procedure that turns CNF into DNF. $\endgroup$
    – Zirui Wang
    Commented Aug 24, 2015 at 15:24
  • $\begingroup$ Generating all subsets of |V| - 1 edges. CNF to DNF can be accomplished with a similarly exhaustive process: choosing a single literal from each CNF clause and combining them to create a DNF clause, then iterating this process with different literals until all possible DNF clauses have been created. $\endgroup$
    – Kyle Jones
    Commented Aug 24, 2015 at 17:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .