2026-09-18T20:59:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25982 2026-09-05T19:31:57Z ddc:004 open_access

Packing Compact Subgraphs with Applications to Districting Chen, Ho-Lin Chou, Po-Yu Dharangutte, Prathamesh Gao, Jie Huang, Shang-En Yu, Fang-Yi Approximation algorithms algorithmic fairness Packing disjoint subgraphs in a given graph is a fundamental problem with many applications. Motivated by political districting, we focus on connected subgraphs that are compact (e.g., having constant radius from a single center vertex) and that satisfy additional composition requirements, such as a minimum population/weight threshold or balanced weight types (e.g., political affiliations). We aim to maximize coverage by disjoint districts that meet these requirements. In this work, we present new results that substantially improve the previously known bounds on balanced star districts for planar and minor-free graphs [Prathamesh Dharangutte et al., 2025]. In particular, we improve the approximation factor from O(log n) to O(1) for packing balanced star districts using the exact same algorithm, but with a refined analysis. We also extend the results beyond planar graphs to minor-free graphs and an even broader family of graphs of bounded expansion. Additionally, we obtain an O(1) approximation for packing radius-k districts (with a constant k) in planar and apex-minor-free graphs. In order to get a (1+ε) approximation on the max coverage, we show that this can be achieved if we allow a slight relaxation of the balancedness parameters (by a factor that can be made arbitrarily close to 1), for bounded radius-k districts on planar and apex-minor-free graphs. We show that all of these results can also be obtained if we enforce a minimum weight threshold for each district as the composition requirement, rather than balancedness. We present various results on hardness and hardness of approximation for this variant, by graph and district types. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ho-Lin Chen and Po-Yu Chou and Prathamesh Dharangutte and Jie Gao and Shang-En Huang and Fang-Yi Yu 2026 Is Part Of LIPIcs, Volume 368, 7th Symposium on Foundations of Responsible Computing (FORC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FORC.2026.10 urn:nbn:de:0030-drops-259820 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2026.10 eng https://creativecommons.org/licenses/by/4.0/legalcode