English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the NP-hard Fair Connected Districting problem recently proposed byStoica et al. [AAMAS 2020]: Partition a vertex-colored graph into k connectedcomponents (subsequently referred to as districts) so that in every districtthe most frequent color occurs at most a given number of times more often thanthe second most frequent color. Fair Connected Districting is motivated byvarious real-world scenarios where agents of different types, which areone-to-one represented by nodes in a network, have to be partitioned intodisjoint districts. Herein, one strives for "fair districts" without any typebeing in a dominating majority in any of the districts. This is to e.g. preventsegregation or political domination of some political party. We conduct afine-grained analysis of the (parameterized) computational complexity of FairConnected Districting. In particular, we prove that it is polynomial-timesolvable on paths, cycles, stars, and caterpillars, but already becomes NP-hardon trees. Motivated by the latter negative result, we perform a parameterizedcomplexity analysis with respect to various graph parameters, includingtreewidth, and problem-specific parameters, including, the numbers of colorsand districts. We obtain a rich and diverse, close to complete picture of thecorresponding parameterized complexity landscape (that is, a classificationalong the complexity classes FPT, XP, W[1]-hard, and para-NP-hard).

A Refined Complexity Analysis of Fair Districting over Graphs