On the complexity of partitioning a graph into a few connected subgraphs

摘要

Given a graph , a sequence of positive integers summing up to is said to be realizable in if there exists a realization of in , i.e. a partition of such that each induces a connected subgraph of on vertices. We first give a reduction showing that the problem of deciding whether a sequence with elements is realizable in a graph is NP-complete for every fixed . Thanks to slight modifications of this reduction, we then prove additional hardness results on decision problems derived from the previous one. In particular, we show that the previous problem remains NP-complete when a constant number of vertex-membership constraints must be satisfied. We then prove the tightness of an easiness result proved independently by Gyori and Lovasz regarding a similar problem. We finally show that another graph partition problem, asking whether several partial realizations of in can be extended to obtain whole realizations of in , is -complete.