12
$\begingroup$

While answering this question on cstheory, I (informally) proved on the fly the following theorem:

Theorem: For any fixed $l \geq 3$ the Hamiltonian cycle probem remains NP-complete even if restricted to planar bipartite undirected graphs of maximum degree 3 that don't contain cycles of length $\leq l$.

It seems very unlikely that it has not already appeared somewhere.
But it allows to settle many Hamiltonian cycle/path problems on graphclasses.org that are marked as "Unknown to ISGCI" (see for example this one); indeed a direct corollary is that Hamiltonian cycle and path problems are still NP-complete if restricted to $(H_1,...,H_k)\text{-free}$ graphs, where each of the $H_i$ contains at least one cycle.

Can you give me a reference of the paper/book where it appeared?

(then I'll contact people at graphclasses.org)

Improve this question
$\endgroup$
4
  • $\begingroup$ At least these discussions helped for new results in graphclasses.org so please inform graphclasses about unknown to them result - The Contact link gives a form, email address is optional. $\endgroup$
    – joro
    Commented Jun 18, 2014 at 8:02
  • $\begingroup$ @joro: I already contacted them, yesterday (I also gave them my email). I'll wait a few days and see if they update the status of those problems. $\endgroup$
    – Marzio De Biasi
    Commented Jun 18, 2014 at 8:42
  • $\begingroup$ I heard they don't update the database very often and reply with "thanks" after updating the DB and they are quite responsive. $\endgroup$
    – joro
    Commented Jun 18, 2014 at 9:04
  • $\begingroup$ @joro: I think they updated the database (they are very collaborative and polite) $\endgroup$
    – Marzio De Biasi
    Commented Jun 23, 2014 at 7:27

2 Answers 2

Reset to default
13
$\begingroup$

The result is stated in the paper Two New Classes of Hamiltonian Graphs by Arkin, Mitchell and Polinshchuk.

Improve this answer
$\endgroup$
0
26
$\begingroup$

This unpublished manuscript by Hougardy, Emden-Weinert and Kreuter in 1997 provided a simple proof for the following result which is much stronger than the result pointed out in Kristoffer Arnsfelt Hansen's answer:

For any given rational number $0\le r <1/2$, the Hamiltonian cycle probem remains NP-complete even if restricted to bipartite planar $n$-vertex graphs of maximum degree 3 and girth $\ge n^r$.

The manuscript contains also similar results for other problems such as Dominating set, Max cut, VFS, etc.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Ok, thanks! I forgot to mention that my proof works for planar undirected bipartite graphs of max-degree 3 ... so the Hourgardy et al. paper is stronger ... but not much stronger :-) :-). I'll probably accept Kristoffer's answer because he posted it first. $\endgroup$
    – Marzio De Biasi
    Commented Jun 17, 2014 at 17:00
  • 14
    $\begingroup$ @MarzioDeBiasi, I think the strongness is about the size of a girth. your proof is about fixed number, accepted answer is for some f(n) which is less than sqrt and this answer is more general than all of them. (IMHO restriction to the graph is not very important here) $\endgroup$
    – Saeed
    Commented Jun 17, 2014 at 21:26
  • 2
    $\begingroup$ The paper contains other NP-hard problems, it will be an answer to the linked question about cyclic graphs. $\endgroup$
    – joro
    Commented Jun 18, 2014 at 9:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.