A refined complexity analysis of fair districting over graphs [original]

Vol.:(0123456789)

Autonomous Agents and Multi-Agent Systems (2023) 37:13

https://doi.org/10.1007/s10458-022-09594-2

1 3

A refined complexity analysis offair districting overgraphs

NiclasBoehmer1 · TomohiroKoana1· RolfNiedermeier1

Accepted: 9 December 2022 / Published online: 28 December 2022

Abstract

We study the NP-hard

Fair ConneCted distriCting

problem recently proposed by Stoica

etal.[AAMAS 2020]: Partition a vertex-colored graph into kconnected components (sub-

sequently 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 Con

neCted 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 domi-

nating majority in any of the districts. This is to e.g. prevent segregation or political domi-

nation of some political party. 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]-hard, and

para-NP-hard).

Keywords Parameterized Algorithmics· Electoral Districting· Fairness· Social Choice on

Social Networks

A 2-page extended abstract of this work will appear in the proceedings of the 21st International

Conference on Autonomous Agents and Multiagent Systems (AAMAS 2022).

* Niclas Boehmer

[email protected]

Tomohiro Koana

tomohiro.k[email protected]

1 Algorithmics andComputational Complexity, Technische Universität Berlin, Berlin10623, Berlin,

Germany

Autonomous Agents and Multi-Agent Systems (2023) 37:13

1 3

13 Page 2 of 37

1 Introduction

Stoica etal. [48] recently introduced graph-based problems on fair (re)districting, employ-

ing “margin of victory” as the measure of fair representation. In their work, they performed

theoretical and empirical studies; the latter clearly supporting the practical relevance of

these problems. The main contribution of their work is certainly with respect to modeling

and performing promising empirical studies (based on greedy heuristics). In this paper,

we instead focus on the theoretical aspects, significantly extending their findings in this

direction.

Dividing agents into groups is a ubiquitous task. Electoral districting is one of the prime

examples: Voters are partitioned into voting districts, each electing its own representa-

tive.1 Another example emerges in education; in many countries, children are assigned to

schools based on their residency. In such scenarios, the agents (in the settings above, voters

or school children) are often placed on a (social or geographical) network. When assigning

them to districts, it is natural to require that every district should be connected in the net-

work and meet some further criteria.

In districting, there are various objectives. What we study here can be interpreted as

a “benevolent” counterpart of the well-studied gerrymandering scenario in voting theory.

For gerrymandering, every voter is characterized by their projected vote in the upcoming

election. The goal is then to find a partition of the voters into connected districts such that

some designated alternative gains the majority in as many districts as possible. Following

Stoica etal. [48], we consider an opposite objective. That is, we assume that some central

authority wishes to partition the agents, which are of different types, into connected dis-

tricts that are fair, where a district is deemed fair if the margin of victory in the district

is smaller than a given bound. The margin of victory of a district is the minimum number

of agents whose deletion results in a tie between the two most frequent types in the dis-

trict. When it comes to school districts, sociodemographic attributes such as race, gender,

and religion may be modeled. Here, a low margin of victory would be desirable because a

majority of students sharing certain attributes may result in significant funding disparities

between schools, as claimed by EdBuild [19] (see Stoica etal. [48] for a more extensive

discussion). In electoral districting where agents’ types can represent their projected vote

or ethnicity, a low margin of victory may foster competition among politicians, thereby

motivating elected officials to do a great job. To illustrate that districts that are dominated

by a certain ethnicity are a serious problem in particular in developing countries, we quote

the two Noble price winners Banerjee and Duflo [4, pp. 251–252]

There is reason to be concerned that voting [in developing countries] is often based

on ethnic loyalties, which means that the candidate from the largest ethnic group

often wins, whatever his intrinsic merit. [...] [I]f voters choose based on ethnicity

rather than on merit, the quality of candidates representing the majority group will

suffer: These candidates don’t need to make much of an effort because the fact that

they are from the “right” caste or ethnic group is sufficient to ensure that they are

elected.

Banerjee and Duflo [5] even found evidence that in the 1980s and 1990s in North India

elected official that belong to the (clearly) dominating caste group were significantly more

1 One prominent example of electoral districting are the congressional districts in the United States: The

US is divided into 435 congressional districts each electing one member of the House of Representatives.

How these districts are drawn is the topic of an ongoing debate [13, 21, 27, 37].

Autonomous Agents and Multi-Agent Systems (2023) 37:13

1 3

Page 3 of 37 13

likely to be corrupt. This illustrates the practical importance of creating districts with a low

margin of victory (in terms of ethnicity). The importance of this problem is further stressed

by recent finding of Zhao etal. [50], who provided evidence that the 2021 Georgia Con-

gressional Districting Plan was designed in a way to have a high margin of victory in each

district (thereby making elections in each district non-competitive and non-responsive to

change in the preferences of voters).

In our work, we build upon the studies of Stoica etal. [48] to search for tractable special

cases of fair districting over graphs. We focus on the

Fair ConneCted distriCting

(FCd)

problem (a natural special case of Stoica etal.’s

Fair ConneCted regrouping

problem).

The input of FCd consists of a graph

G=(V,E)

in which every vertex is assigned a color

from a setC, and integers k,

𝓁

smin

, and

smax

. The question is whether the vertex set ofG

can be partitioned into k connected districts, each containing between

smin

and

smax

verti-

ces, whose margin of victory is at most

𝓁

. The difference to

Fair ConneCted regrouping

is that FCd does not impose any constraints to which districts an agent can be assigned.2

It is easy to see that FCd generalizes the known NP-hard

perFeCtly BalanCed Con

neCted partition

problem [14, 18], which asks for a partition of a graph into two con-

nected components of the same size (see Proposition 1). This motivates a parameterized

complexity analysis and the study of restrictions of the underlying graph in order to iden-

tify tractable special cases. Specifically, we analyze the computational complexity of FCd

on specific graph classes and the parameterized complexity of FCd with respect to several

problem-specific parameters (such as

|C|

andk) as well as several parameters measuring

structural properties of the underlying graph (such as its treewidth or vertex cover number).

1.1 Related work

1.1.1 Relation tomodel studied byStoica etal. [48]

Stoica etal. [48] introduced

Fair ConneCted regrouping

, which is a generalization of our

FCd problem.

Fair ConneCted regrouping

differs from FCd in that, in

Fair ConneCted

regrouping

, one is additionally given a function that specifies for each vertex to which

district it can belong. They proved that

Fair ConneCted regrouping

is NP-hard even for

only two colors and two districts. Moreover, Stoica etal. [48] considered two special cases

Fair ConneCted regrouping

Fair regrouping

(omitting connectivity constraints) and

Fair regrouping_X

(omitting connectivity constraints and any restriction to which districts

vertices can belong). They proved that

Fair regrouping

is NP-hard for three colors but in

XP with respect to the number of districts. Turning to

Fair regrouping_X

, they showed

that the problem is in XP with respect to the number of colors or districts, but left open the

general complexity. Overall, our problem is a special case of

Fair ConneCted regrouping

incomparable to

Fair regrouping

, and a generalization of

Fair regrouping_X

. Thus, there

are no direct implications of the studies of Stoica etal. for our problem.

2 We mention that Stoica etal. [48] use a slightly different yet in most cases equivalent definition of mar-

gin of victory. See Sect. 1.1.1 for a detailed discussion. Clearly, there are also other fairness measures

for assessing the fairness of districts different from the margin of victory, e.g., the difference between the

occurrences of the most and least frequent color. While these are natural as well, our definition is particu-

larly appealing if each district may be only associated with its most frequent color if its margin of victory is

too high. Notably, margin of victory is also a popular concept in other domains such as group identification

[9], tournament solutions [12], and voting theory [17, 49].

Autonomous Agents and Multi-Agent Systems (2023) 37:13

1 3

13 Page 4 of 37

Moreover, our problem differs from the ones studied by Stoica etal. [48] in a slightly

different definition of margin of victory. While we look at the number of vertices that need

to be deleted to have a tied most frequent color, they examine the number of vertices that

need to change their color such that the most frequent color changes. We chose our defini-

tion in order to be able to distinguish the case of two tied most frequent colors from the

case where one color appears once more than the others (which both have margin of vic-

tory one in the model of Stoica etal. [48]). In all other cases, if m is the margin of victory

in our definition, then the margin of victory in the definition of Stoica etal. [48] is

⌊m

2⌋

However, all our algorithmic results can be extended to the definition of Stoica etal. [48].

We expect that hardness results similar to ours can be obtained for their definition as well.

1.1.2 Further related work

Following up on the work of Stoica etal. [48], Boehmer and Koana [10] analyzed the

Fair regrouping

and the

Fair regrouping_X

problem in more detail. Among others, they

proved that

Fair regrouping_X

without size constraints is polynomial-time solvable while

the NP-hard

Fair regrouping

problem without size constraints is polynomial-time solvable

for two colors and fixed-parameter tractable with respect to the number of districts. In addi-

tion to the margin of victory, they also considered the maximum difference between the

occurrences of two colors in a district as an additional fairness notion. Again, their results

have no implications on the complexity of our FCd problem.

FCd is relevant in district-based elections, where voters are partitioned into districts and

each district elects its own representative. Several papers have studied how to assign voters

to districts so as to “fairly” reflect the political choices of voters [3, 34, 35, 43, 44]. Well-

studied in this context is gerrymandering, which can be regarded as a “malicious” counter-

part to our problem. In gerrymandering, the task is to partition a set of voters into districts

obeying certain conditions such that a designated alternative wins in as many districts as

possible. An intuitive strategy to solve this problem, which is not necessarily optimal [45],

is to maximize the number of districts where the designated alternative wins only by a

small margin (this is somewhat related to our problem.) Initially, gerrymandering has been

predominantly studied from the perspective of social and political science [23, 28, 40].

More recently, different variants of gerrymandering have been considered from an algorith-

mic perspective [20, 38]. Notably, the study of gerrymandering over graphs, which is anal-

ogous to our problem, has recently gained significant interest[6, 15, 26, 29]. In particular,

as done here for FCd, Bentert etal. [6], Gupta etal. [26], and Ito etal. [29] analyzed the

complexity of gerrymandering on paths, cycles, and trees and studied the influence of the

number of candidates/colors and the number of districts. A similar model for graph-based

redistribution scenarios and political districting has been studied under the name “network-

based vertex dissolution”[7].

Partitioning agents of different types into balanced groups is conceptually closely

related to studies of social segregation. In computer science, social segregation is, for

instance, quite extensively studied in the context of Schelling’s segregation model [47]:

While initially the work in this context was mostly concerned with the theoretical analysis

of segregation patterns [8, 11], recently Schelling’s model has been approached from a

game-theoretic perspective [1, 33].

Autonomous Agents and Multi-Agent Systems (2023) 37:13

1 3

Page 5 of 37 13

1.2 Contribution

Motivated by the NP-hardness of FCd (see Proposition 1), we conduct a parameterized

complexity analysis of FCd and study restrictions of the underlying graph in order to iden-

tify tractable special cases. We investigate the influence of problem-specific parameters

(the number

|C|

of colors, the numberk of districts, and the margin of victory

𝓁

) and the

structure of the underlying graph on the computational complexity of FCd.

The motivation for our refined complexity analysis is two-fold. First, analyzing special

graph classes and types of graphs offers a better understanding of the complexity of FCD:

Path, stars, and cycles form the building blocks of more complex graphs and thus under-

standing the problem on these graphs is vital for a further analysis.3 Moreover, real-world

networks will usually have some structure. One specific use case for our algorithms might

be sampling algorithms for “fair” districting plans. These sampling algorithms often work

by pre-aggregating groups of voters, creating a spanning tree on the merged space, and

then continuing by further merging adjacent groups [2, 16, 42]. Here, our analysis of FCD

on trees and tree-like graphs might be useful. Second, considering the analysis of the influ-

ence of the number

|C|

of colors and the numberk of districts, in most applications we

can think of these two parameters are substantially smaller than the number of vertices,

motivating to check whether FCD becomes tractable if one (or both) of these parameters

are small. For instance, in their experiments, Stoica etal. [48] partitioned 50, 000 voters

into10voting districts and 41 834 schoolchildren into 61 school districts with

|C|=7

We show that FCd is NP-hard even if

|C|=k=2

and

𝓁=0

but polynomial-time solv-

able on paths, cycles, stars, and caterpillars (for stars, our algorithm even runs in linear

time). Subsequently, we extend our polynomial-time algorithms for paths and cycles to a

polynomial-time algorithm for all graphs with a constant max leaf number (

mln

), which

are basically graphs that consist of a constant number of paths and cycles (where the two

endpoints of each path and one point from each cycle can be arbitrarily connected).

Remarkably, in our most involved hardness reduction, we show that FCd already

becomes NP-hard and even W[1]-hard with respect to

|C|+k

on trees. However, when the

number of colors or the number of districts is constant, FCd on trees becomes polynomial-

time solvable. In fact, we show that these results hold for some tree-like graphs as well.

Herein, the tree-likeness of a graph is measured by one of three parameters, namely, the

treewidth (

), the feedback edge number (

fen

), and the feedback vertex number (

fvn

More precisely, as our most involved algorithmic results, we establish polynomial-time

solvability of FCd when the number of colors and the treewidth are constant. We achieve

this with a dynamic programming approach on the tree decomposition of the given graph

empowered by some structural observations on FCd. Moreover, we observe that there is a

simple polynomial-time algorithm on graphs with a constant feedback edge number when

there are a constant number of districts. On the other hand, we prove that FCd is NP-hard

for two districts even on graphs with

fvn =1

(and

tw =2

). Lastly, we show that FCd is

polynomial-time solvable on graphs with a constant vertex cover number (

vcn

) and fixed-

parameter tractable with respect to the vertex cover number and the number of colors. A

3 This also motivated a study of these graph classes for gerrymandering over graphs [6, 26, 29]. Moreover,

initially, it is not at all clear that FCd is polynomial-time solvable on these graphs, as, for instance, gerry-

mandering over graphs is NP-hard even on paths [6, Theorem1] That we establish that FCd is polynomial-

time solvable on paths also proves that FCd is sometimes easier than the corresponding gerrymandering

over graphsproblem.

Loading more pages...