Can CNF Hamiltonian graphs be turned to "DNF" graphs?

Question

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?

Answer 1

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.