We study the NP-hard Fair Connected Districting problem: Partition a vertex-colored graph into k connected components (subsequently referred to as districts) so that in every district the most frequent color occurs at most a given number of times more often than the second most frequent color. Fair Connected Districting is motivated by various real-world scenarios where agents of different types, which are one-to-one represented by nodes in a network, have to be partitioned into disjoint districts. Herein, one strives for "fair districts" without any type being in a dominating majority in any of the districts. This is to e.g. prevent segregation or political domination of some political party. Our work builds on a model recently proposed by Stoica et al. [AAMAS 2020]. We conduct a fine-grained analysis of the (parameterized) computational complexity of Fair Connected Districting. In particular, we prove that it is polynomial-time solvable on paths, cycles, stars, and caterpillars, but already becomes NP-hard on trees. Motivated by the latter negative result, we perform a parameterized complexity analysis with respect to various graph parameters, including treewidth, and problem-specific parameters, including the numbers of colors and districts. We obtain a rich and diverse, close to complete picture of the corresponding parameterized complexity landscape (that is, a classification along the complexity classes FPT, XP, W[1]-hardness, and para-NP-hardness).
翻译:我们研究了NP-hard Fair Connected 地区问题: 将一个顶端彩色图形分割成 k连结组件( 后称为区), 这样在每个区, 最常见的颜色会发生的次数最多, 比第二个最经常的颜色多得多。 公平的连通区受到各种真实世界情景的驱动, 不同类型的代理, 由网络节点代表的一对一的计算复杂性, 被分割成互不连接区 。 在这里, 人们努力争取“ 公平区 ”, 而不是任何类型的在任何地区占据主导多数的复杂程度 。 例如, 防止某些政党的隔离或政治支配。 我们的工作建立在由Stoica 等人( AMAS 2020) 推荐的模型上。 我们对不同类型( 参数) 的计算复杂性进行细微分析, 特别是, 我们证明, 在路径、 周期、 恒星 和 结柱形 上, 已经变得 硬性 。