Borndörfer, Ralf ;
Casel, Katrin ;
Issac, Davis ;
Niklanovits, Aikaterini ;
Schwartz, Stephan ;
Zeif, Ziena
Connected kPartition of kConnected Graphs and cClawFree Graphs
Abstract
A connected partition is a partition of the vertices of a graph into sets that induce connected subgraphs. Such partitions naturally occur in many application areas such as road networks, and image processing. In these settings, it is often desirable to partition into a fixed number of parts of roughly of the same size or weight. The resulting computational problem is called Balanced Connected Partition (BCP). The two classical objectives for BCP are to maximize the weight of the smallest, or minimize the weight of the largest component. We study BCP on cclawfree graphs, the class of graphs that do not have K_{1,c} as an induced subgraph, and present efficient (c1)approximation algorithms for both objectives. In particular, for 3clawfree graphs, also simply known as clawfree graphs, we obtain a 2approximation. Due to the clawfreeness of line graphs, this also implies a 2approximation for the edgepartition version of BCP in general graphs.
A harder connected partition problem arises from demanding a connected partition into k parts that have (possibly) heterogeneous target weights w₁,…,w_k. In the 1970s Győri and Lovász showed that if G is kconnected and the target weights sum to the total size of G, such a partition exists. However, to this day no polynomial algorithm to compute such partitions exists for k > 4. Towards finding such a partition T₁,…, T_k in kconnected graphs for general k, we show how to efficiently compute connected partitions that at least approximately meet the target weights, subject to the mild assumption that each w_i is greater than the weight of the heaviest vertex. In particular, we give a 3approximation for both the lower and the upper bounded version i.e. we guarantee that each T_i has weight at least (w_i)/3 or that each T_i has weight most 3w_i, respectively. Also, we present a bothside bounded version that produces a connected partition where each T_i has size at least (w_i)/3 and at most max({r,3}) w_i, where r ≥ 1 is the ratio between the largest and smallest value in w₁, … , w_k. In particular for the balanced version, i.e. w₁ = w₂ = , … , = w_k, this gives a partition with 1/3w_i ≤ w(T_i) ≤ 3w_i.
BibTeX  Entry
@InProceedings{borndorfer_et_al:LIPIcs.APPROX/RANDOM.2021.27,
author = {Bornd\"{o}rfer, Ralf and Casel, Katrin and Issac, Davis and Niklanovits, Aikaterini and Schwartz, Stephan and Zeif, Ziena},
title = {{Connected kPartition of kConnected Graphs and cClawFree Graphs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
pages = {27:127:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772075},
ISSN = {18688969},
year = {2021},
volume = {207},
editor = {Wootters, Mary and Sanit\`{a}, Laura},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14720},
URN = {urn:nbn:de:0030drops147200},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.27},
annote = {Keywords: connected partition, Gy\H{o}riLov\'{a}sz, balanced partition, approximation algorithms}
}
15.09.2021
Keywords: 

connected partition, GyőriLovász, balanced partition, approximation algorithms 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Issue date: 

2021 
Date of publication: 

15.09.2021 