Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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)

share|improve this question
    
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. –  joro Jun 18 at 8:02
    
@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. –  Marzio De Biasi Jun 18 at 8:42
    
I heard they don't update the database very often and reply with "thanks" after updating the DB and they are quite responsive. –  joro Jun 18 at 9:04
    
@joro: I think they updated the database (they are very collaborative and polite) –  Marzio De Biasi Jun 23 at 7:27

2 Answers 2

up vote 13 down vote accepted

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

share|improve this answer

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.

share|improve this answer
1  
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. –  Marzio De Biasi Jun 17 at 17:00
    
No problem :-)) –  vb le Jun 17 at 17:13
14  
@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) –  Saeed Jun 17 at 21:26
2  
The paper contains other NP-hard problems, it will be an answer to the linked question about cyclic graphs. –  joro Jun 18 at 9:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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