License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.27
URN: urn:nbn:de:0030-drops-147200
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14720/
Borndörfer, Ralf ;
Casel, Katrin ;
Issac, Davis ;
Niklanovits, Aikaterini ;
Schwartz, Stephan ;
Zeif, Ziena
Connected k-Partition of k-Connected Graphs and c-Claw-Free 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 c-claw-free graphs, the class of graphs that do not have K_{1,c} as an induced subgraph, and present efficient (c-1)-approximation algorithms for both objectives. In particular, for 3-claw-free graphs, also simply known as claw-free graphs, we obtain a 2-approximation. Due to the claw-freeness of line graphs, this also implies a 2-approximation for the edge-partition 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 k-connected 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 k-connected 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 3-approximation 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 both-side 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 k-Partition of k-Connected Graphs and c-Claw-Free Graphs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
pages = {27:1--27:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-207-5},
ISSN = {1868-8969},
year = {2021},
volume = {207},
editor = {Wootters, Mary and Sanit\`{a}, Laura},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14720},
URN = {urn:nbn:de:0030-drops-147200},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.27},
annote = {Keywords: connected partition, Gy\H{o}ri-Lov\'{a}sz, balanced partition, approximation algorithms}
}
|
Keywords: |
|
connected partition, Győri-Lovász, balanced partition, approximation algorithms |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
15.09.2021 |
