2026-07-22T13:49:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14607 2024-03-06T10:54:26Z ddc:004 open_access

Balanced Crown Decomposition for Connectivity Constraints Casel, Katrin Friedrich, Tobias Issac, Davis Niklanovits, Aikaterini Zeif, Ziena crown decomposition connected partition balanced partition approximation algorithms We introduce the balanced crown decomposition that captures the structure imposed on graphs by their connected induced subgraphs of a given size. Such subgraphs are a popular modeling tool in various application areas, where the non-local nature of the connectivity condition usually results in very challenging algorithmic tasks. The balanced crown decomposition is a combination of a crown decomposition and a balanced partition which makes it applicable to graph editing as well as graph packing and partitioning problems. We illustrate this by deriving improved approximation algorithms and kernelization for a variety of such problems. In particular, through this structure, we obtain the first constant-factor approximation for the Balanced Connected Partition (BCP) problem, where the task is to partition a vertex-weighted graph into k connected components of approximately equal weight. We derive a 3-approximation for the two most commonly used objectives of maximizing the weight of the lightest component or minimizing the weight of the heaviest component. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Katrin Casel and Tobias Friedrich and Davis Issac and Aikaterini Niklanovits and Ziena Zeif 2021 Is Part Of LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2021.26 urn:nbn:de:0030-drops-146076 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.26 eng https://creativecommons.org/licenses/by/4.0/legalcode