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 kernelization and approximation algorithms 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.
翻译:我们引入平衡的皇冠分解, 记录图形因特定大小的相联引导子体而导致的结构。 这种子体分解是各种应用领域流行的模型工具, 互连性的非本地性通常导致非常具有挑战性的算法任务。 平衡的王冠分解是冠分解和平衡的分割的结合, 使这种分解适用于图形编辑以及图形包装和分区问题。 我们通过为各种问题改进内核化和近似算法来说明这一点。 特别是通过这一结构, 我们获得了平衡连连通区( BCP) 问题的第一个常数点近似值, 在那里, 任务就是将一个顶点加权的图形分割成一个大约同等重量的美元相连接的元件。 我们为最常用的两个目标, 即最大限度地增加最轻部分的重量或尽量减少最重部分的重量, 我们得出一个3- 3- 方位的混合值。