Authors: Julien Bensmail
Publish Date: 2013/06/23
Volume: 30, Issue: 1, Pages: 174-187
Abstract
Given a graph G a sequence tau = n 1 ldots n p of positive integers summing up to VG is said to be realizable in G if there exists a realization of tau in G ie a partition V 1 ldots V p of VG such that each V i induces a connected subgraph of G on n i vertices We first give a reduction showing that the problem of deciding whether a sequence with c elements is realizable in a graph is NPcomplete for every fixed c ge 2 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 NPcomplete when a constant number of vertexmembership constraints must be satisfied We then prove the tightness of an easiness result proved independently by Györi and Lovász regarding a similar problem We finally show that another graph partition problem asking whether several partial realizations of tau in G can be extended to obtain whole realizations of tau in G is varPi 2pcomplete
Keywords: