3
$\begingroup$

I came across two examples of hypothetical hardness of some graph problems. Hypothetical hardness means that refuting some conjecture would imply the NP-completeness of the respective graph problem. For instance, Barnette's conjecture states that every 3-connected cubic planar bipartite graph is Hamiltonian. Feder and Subi proved that refuting the conjecture would imply the NP-completeness of the Hamiltonian cycle problem on graphs in the class of the conjecture.

Tutte's 5-flow Conjecture states that every bridgeless graph has a nowhere-zero 5-flow. Kochol showed that if the conjecture is false, then the problem to determine whether a cubic graph admits a nowhere-zero 5-flow is NP-complete.

Are there common insights into the above conjectures that explain the hypothetical NP-completeness of the corresponding graph problems?

Also, I am interested in other known examples of hypothetical complexity in the above sense.

P.S. What kind of conjecture would imply the NP-completeness of graph isomorphism problem?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.