1
$\begingroup$

Hi, i would like to have some clarification on NP-completeness. In particular I'm reading an article where they show:

1) Partitioning the edges of a graph into connected component of 3 edges (3-path or triangles or $K_{1,3}$) is NP-complete.

2) Partitioning the edges of a graph into subgraph isomorphic to 3-path is NP-complete

3) Partitioning the edges of a graph into subgraph isomorphic to K_1,3 is NP-complete.

What I don't understand is why 1) doesn't imply 2) and 3) If I can't tell if partitioning a graph with subgraph isomorphic to a connected component of 3 edges is possible or not, then I can't even tell if partitioning with subgraph isomorphic (for example) to 3-path is possible or not. Thak you for your help

Improve this question
$\endgroup$
6
  • $\begingroup$ If you know that a graph cannot be partitioned into 3-paths, how does it help you to determine whether it can be partitioned into 3-edge components? $\endgroup$
    – Emil Jeřábek
    Commented Jan 18, 2013 at 17:14
  • $\begingroup$ you're right, but if I know that I can't find any partition of 3 edge connected component then I'm sure that I can't find a partition with 3-paths (which are 3 edge connected component) So, 1)----->2) $\endgroup$
    – luca
    Commented Jan 18, 2013 at 17:33
  • 1
    $\begingroup$ But if you can find a 3-edge partition, you have no information on the existence of 3-paths partition. A reduction has to be if and only if, otherwise it is useless. Let me give another example: 1') 3-colourability of graphs is NP-complete. If a graph has no 3-colouring, it has no 2-colouring either, hence by your logic, 2') 2-colourability of graphs is NP-complete. But this is wrong (unless P = NP), as 2-colourability is decidable in polynomial time. $\endgroup$
    – Emil Jeřábek
    Commented Jan 18, 2013 at 17:56
  • $\begingroup$ Anyway, this is not a research-level question, and as such it is not appropriate for this site. $\endgroup$
    – Emil Jeřábek
    Commented Jan 18, 2013 at 18:00
  • $\begingroup$ ok, thank you for your help, and excuse me if I posted the question in the wrong site, I don't know any other. Thank you again. $\endgroup$
    – luca
    Commented Jan 18, 2013 at 18:06

0

Reset to default

Browse other questions tagged .