4
$\begingroup$

I know that IS (is there independent set of size at least $k$?) on planar cubic graphs is NP-Complete, and IS on triangle-free graphs is also NP-Complete. But how about IS on triangle-free planar cubic graphs? Is it still an NP-Complete problem, or there are some polynomial time solutions?

Any ideas or referrences are appreciated, thank you in advance!

$\endgroup$
6
$\begingroup$

Independent Set is $\mathsf{NP}$-hard even for $3$-connected cubic planar triangle-free graphs, as shown in this nice short note.

$\endgroup$
  • $\begingroup$ Thank you for discovering this paper! Can you edit your answer to provide a full citation to the paper? As it stands, if the link stops working, this answer will become useless. At a minimum, I suggest including title, author, and where it was published. Please take some time to improve your post in this regard. We have collected some advice here. Thank you! $\endgroup$ – D.W. Mar 28 '16 at 0:07
4
$\begingroup$

This paper shows that independent set is NP-complete for triangle-free planar graphs whose maximum degree is at most three (Theorem 2 with $\mathcal{F} = \{\triangle\}$). This is almost what you want (you want the graph to be 3-regular), and presumably with some work you could modify the proof to get exactly what you want.

$\endgroup$
1
$\begingroup$

Unfortunately Uehara's proof is wrong. If we consider planar subcubic graphs from Johnson's "Rectilinear Steiner Tree" paper then they could be disconnected and all this stuff with gadgets does not work. Also it does not lead to cubic ($3$-regular) planar graph: when replacing some vertex of degree 2 from the cycle around vertex of degree 1 with the gadget we again have some gadget vertex of degree 2 so the reduction process is infinite.

There is a Mohar's paper Face Covers and the Genus Problem for Apex Graphs that does contain correct proof of NP-hardness of MIS over 2-connected 3-regular planar graphs which involves Kratovchil superresult of NP-hardness of planar 3-connected 3-SAT. I suppose NP-hardness under your setting could be obtained by applying mentioned Mohar's result with Uehara's technique.

$\endgroup$

Your Answer

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

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