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?


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.