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

Julien Bensmail ()
Additional contact information
Julien Bensmail: University of Bordeaux, LaBRI

Journal of Combinatorial Optimization, 2015, vol. 30, issue 1, No 14, 174-187

Abstract: Abstract Given a graph $$G$$ G , a sequence $$\tau = (n_1, \ldots , n_p)$$ τ = ( n 1 , ... , n p ) of positive integers summing up to $$|V(G)|$$ | V ( G ) | is said to be realizable in $$G$$ G if there exists a realization of $$\tau $$ τ in $$G$$ G , i.e. a partition $$(V_1, \ldots , V_p)$$ ( V 1 , ... , V p ) of $$V(G)$$ V ( G ) such that each $$V_i$$ V i induces a connected subgraph of $$G$$ G on $$n_i$$ n i vertices. We first give a reduction showing that the problem of deciding whether a sequence with $$c$$ c elements is realizable in a graph is NP-complete for every fixed $$c \ge 2$$ c ≥ 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 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 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$$ G can be extended to obtain whole realizations of $$\tau $$ τ in $$G$$ G , is $$\varPi _2^p$$ Π 2 p -complete.

Keywords: Arbitrarily partitionable graphs; Partition into connected subgraphs; Partition under vertex prescriptions; Complexity; Polynomial hierarchy (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9642-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:30:y:2015:i:1:d:10.1007_s10878-013-9642-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9642-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().