7
$\begingroup$

Work

Jünger, Michael, Gerhard Reinelt, and William R. Pulleyblank. "On partitioning the edges of graphs into connected subgraphs." Journal of graph theory 9.4 (1985): 539-549.

states that for 4-edge-connected graph one can partition its edges into disjoint subsets of size $r$, such that each subset form a connected subgraph.

I wonder if the same kind of statement could be formulated for partition of vertices. For what kind of graphs one find partition of vertices into disjoint subsets of size $\approx r$, such that each subset form a connected subgraph (for each r)? I'm particularly interested in planar graphs, but would be happy with any class.

I can soften some conditions (it will still meet my needs): for what graph classes existence of partition into less than $\frac{\alpha n}{r}$ connected subgraphs of size less than $r$ is guaranteed (for some $\alpha$)?

Improve this question
$\endgroup$
3
  • $\begingroup$ Compute planer embedding. Run some kind of sweep line algorithm. Once sweep line hits n/r vertices cut the edges connecting to the rest of the graph. This should work for planer graphs. $\endgroup$
    – Pratik Deoghare
    Commented Aug 19, 2014 at 21:40
  • 1
    $\begingroup$ Well, you can't do this partition for any planar graph: for example star-graph is planar, but it is impossible to cut it into pieces of size more then 1. $\endgroup$
    – ivmihajlin
    Commented Aug 20, 2014 at 0:57
  • $\begingroup$ I see. This makes the question very interesting. +1 $\endgroup$
    – Pratik Deoghare
    Commented Aug 20, 2014 at 1:35

2 Answers 2

Reset to default
4
$\begingroup$

Compute a constant degree spanning tree $T$ of your graph, root it, and now greedily find subtrees of roughly size $r$, extract them, and repeat. Naturally, if there is no constant degree spanning tree, then the star example shown above demonstrates that this algorithm can fail.

Improve this answer
$\endgroup$
9
$\begingroup$

For a graph $G=(V,E)$, deciding if $V$ can be partitioned into equal sized subsets (say, for a fixed size $r$) where each subset induces a connected subgraph is $\mathsf{NP}$-hard. It remains $\mathsf{NP}$-hard for planar graphs, and also if the number of subsets is fixed instead of the subset size ($|V|/r$ fixed).

However, the problem is polynomial for cycles, and thus for Hamiltonian graphs. It is also polynomial for trees and for series-parallel graphs when the number of subsets is fixed.

You can find these results in:

Edit (bis): I think that I was wrong about Hamiltonian graphs. They may be partitioned even if their Hamiltonian cycle cannot. Thus the problem can be not polynomial. See the first comment.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Looks like you can do it for Hamiltonian graph. As this graph has a Hamiltonian graph, it has a spanning tree of max degree 2. It is possible to find a spanning tree of max degree 3 in polynomial time and using this tree partition the graph (as stated in other answer). research.microsoft.com/en-us/um/people/mohits/publications/… $\endgroup$
    – ivmihajlin
    Commented Aug 20, 2014 at 21:33

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.