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.

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

1 3

13 Page 6 of 37

summary of our parameterized results can be found in Fig.1. Notably, all our hardness

results also hold without sizeconstraints.

In our studies, we identify several sharp complexity dichotomies. For instance, FCd is

polynomial-time solvable on trees with diameter at most three but NP-hard and W[1]-hard

with respect to

|C|+k

on trees with diameter four. Similarly, FCd is NP-hard and W[1]-

hard with respect to

|C|+k

on graphs with pathwidth at least two but polynomial-time

solvable on pathwidth-one graphs.

To summarize, we show that FCd without size constraints is NP-hard even in very

restricted settings, e.g., on trees or if

|C|=k=2

and

𝓁=0

. To make the problem tracta-

ble, one possibility is to significantly restrict the input graph, e.g., to consist of a constant

number of paths and cycles, or to combine structural parameters of the given graph with

the number

|C|

of colors or the number k of districts. For small

|C|

and k, the tractability

of FCd extends to certain tree-like graphs and graphs with a small vertex cover number.

In contrast to the parameters

|C|

andk, which have a strong influence on the complexity

of FCd, the bound

𝓁

on the margin of victory has only little impact as all hardness results

already hold for

𝓁=0

and all our algorithmic results hold for arbitrary

𝓁

1.2.1 Organization

The remainder of this paper is structured as follows. In Sect.2, we formally introduce FCd

and the graph parameters we examine. In Sect.3, we present some preliminary results on

FCd mostly concerning NP-hardness. In Sect.4, we then consider FCd on very special

graph classes such as paths and cycles as well as on graphs that can be partitioned into

a bounded number of those. In Sect.5, we shift our attention to trees and graphs that are

tree-like. Lastly, in Sect.6, we analyze the influence of the vertex cover number on the

complexity of FCd. We defer the proofs of two technical results (marked with

★

) to the

appendix.

Fig. 1 Overview of our parameterized complexity results. Each box represents one parameterization of

FCd. An arc from parameterp to another parameter

p′

indicates that p is upper-bounded by some function

of

p′

. For parameters in the red area (dotted), we prove that FCd is NP-hard even if the parameter is a con-

stant. For parameters in the orange area (dashed), we prove W[1]-hardness and present an XP-algorithm.

For parameters in the yellow area (solid thick), we have an XP-algorithm but W[1]-hardness is unknown.

The green area (solid) indicates fixed-parameter tractability (Color figure online)

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

1 3

Page 7 of 37 13

2 Preliminaries

For

a,b∈ℕ

, let [a,b] denote

{a,a+1, …,b−1, b}

and let [b] denote [1,b]. Throughout

the paper, all graphs

G=(V,E)

are undirected and have no self-loops or multi-edges. By

convention, we will use

n∶= |V|

. Given a graph

G=(V,E)

and a vertex set

V′⊆V

, let

G[V�]

be the graph G induced by the vertices from

V′

2.1 Fair connected districting

Let

C={c1,…,c|C|}

be the set of colors. We assume that each vertex

v∈V

of the given

graph has a color

c∈C

determined by a given coloring function

col ∶V

→

. For a

vertex set

V′⊆V

, let

𝜒c(V�)

denote the number of vertices of color c in

V′

. Moreover,

let

𝜒(V�)∈

ℕ

denote the vector in which the

ith

entry contains the number of vertices

of color

V′

, i.e,

𝜒i(V�)=

𝜒

ci(V�)

. For a vector

x=(x1,…,xt)∈

ℕ

, let

i∗

denote an

index with the largest entry in

, i.e.,

i∗

x∈ arg max i∈[t]xi

. The margin of victory

MOV(

)

of a vector

is defined as the difference between the largest and second largest entry in

, i.e.,

MOV(

) ∶= x

i∗

−max

i∈[t]⧵{i∗

}

. If

t=1

, then we set

MOV(

) ∶= x1

. Accordingly,

we define the margin of victory

MOV(V�)

of a vertex set

V′⊆V

of colored vertices as

MOV(V�) ∶= MOV(𝜒(V�))

. For

𝓁∈ℕ

, we call a vertex set

V′

𝓁

-fair if

MOV(V�)≤𝓁

. We

use the term district to refer to a vertex set

V′⊆V

. We say that a color

ci∈C

is the

jth

most frequent color in a district

V′

𝜒i(

�)

is the

jth

largest entry in

𝜒(V�)

(we break ties

arbitrarily unless statedotherwise). We now present our central problem4:

Fair Connected Districting (FCD)

Input: AgraphG=(V,E), aset Cof colors,afunction col:V→

Cassigningeachvertexone colorfrom C,anumber k≤|V|

of districts, amaximum margin of victory,and twointegers

smax≥smin≥1.

Question:Does there exist apartition of theverticesintokdistricts

(V1,...,V

k)suchthat, forall i∈[k], Viis -fair, |Vi

|∈

[smin,s

max], andG[Vi]isconnected?

2.2 Graph parameters

We define several graph parameters for an undirected graph

G=(V,E)

. The diameter

ofG is the maximum shortest distance between any pair of vertices. The max leaf number

mln (G)

(for a connected graphG) is the maximum number of leaves over all spanning

trees of G. A vertex set

V′⊆V

is a vertex cover ofG if

G[V⧵V�]

has no edge. A vertex

4 Note that we chose to require that all districts are non-empty to be consistent with the closely related lit-

erature on gerrymandering over graphs [15, 29]. Moreover, our variant can easily be used to decide whether

there exists a partitioning into at most k non-empty districts by simply iterating over all

i∈[k]

. For the

reverse direction, this is not easily possible. For instance, consider a clique with two blue vertices and one

green and one red vertex and

𝓁=0

. Then, a partitioning into two non-empty

𝓁

-fair districts is possible but

not into any other number of non-empty districts.

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

1 3

13 Page 8 of 37

set

V′⊆V

is a feedback vertex set if

G[V⧵V�]

is a forest. Analogously, an edge set

E′⊆E

is a feedback edge set if

(V,E⧵E�)

is a forest. The vertex cover number

vcn (G)

, feedback

vertex number

fvn (G)

, and feedback edge number

fen (G)

is the size of a smallest vertex

cover, feedback vertex set, and feedback edge set, respectively. A tree decomposition of a

graph

G=(V,E)

is a pair

(

T,{B

}

x∈VT)

, where

T=(VT,ET)

is a rooted tree and

Bx⊆V

for

each

x∈VT

such that

(i)

⋃x∈VT

Bx=V

(ii) for each edge

{u,v}∈E

, there is an

x∈VT

with

u,v∈Bx

, and

(iii) for each

v∈V

, the set of nodes

x∈VT

with

v∈Bx

induces a connected subtree in

The width of

(T,{Bx}x∈VT)

maxx∈VT|Bx|−1

. The treewidth

tw (G)

of G is the minimum

width of all tree decompositions of G. The pathwidth

pw (G)

of G is defined analogously

with the additional constraint that T is a path.

If G is clear from context, then we simply omit it and write

mln

vcn

fvn

fen

, and

, respectively. For all our parameterized algorithms with respect to one of these param-

eters, we assume that the corresponding structure is given as part of the input. For instance,

in our algorithm parameterized by

, we assume that we are given a tree decompositionof

width tw. However, note that in all cases, the worst-case running time of our algorithms

would not change if we compute the structure using known parameterized algorithms.

2.3 Parameterized complexity theory

A parameterized problemL consists of a problem instance

and a parameter value

k∈ℕ

Then L lies in XP with respect to k if there exists an algorithm decidingL in

|f(k)

time

for some computable function f. Furthermore, Lis called fixed-parameter tractable with

respect to k if there exists an algorithm decidingL in

f(k)|

|O(1)

time for a computable

functionf. The corresponding complexity class is calledFPT. There is a hierarchy of com-

plexity classes for parameterized problems: FPT

⊆

W[1]

⊆

W[2]

⊆

XP, where it is com-

monly believed that all inclusions are strict. Thus, ifL is shown to be W[1]-hard, then the

common belief is that it is not fixed-parameter tractable. For instance, computing a clique

of size at leastk in a graph is known to be W[1]-hard with respect to the parameter k. One

can show that L is W[t]-hard,

t≥1

, by a parameterized reduction from a known W[t]-hard

parameterized problem

L′

. A parameterized reduction from

L′

to L is a function that maps

an instance

(

�

,k�)

L′

to an instance

(I,k)

of L such that

(

�

,k�)

is a yes-instance for

L′

and only if

(I,k)

is a yes-instance for L. Moreover, we require that k is bounded in a func-

tion of

k′

and that the transformation takes at most

f(k�)|

|O(1)

time for some computable

function f. Finally, we say that a parameterized problem is para-NP-hard if it is NP-hard

even for constant parameter values.

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

1 3

Page 9 of 37 13

3 Basic results onFCD

In this section, we make some basic observations on the computational complexity of

FCd. First, we prove that FCd is para-NP-hard with respect to the combination

|C|+k+𝓁

of all three problem-specific parameters. This strong general hardness result motivates the

study of various restricted graph classes in subsequent sections.

The NP-hardness of FCd easily follows from the fact that it generalizes the

perFeCtly

BalanCed ConneCted partition

problem, which is NP-hard on bipartite graphs [18]:

PerfectlyBalanced ConnectedPartition

Input: AgraphG=(V,E).

Question:Is thereapartition(

V1,V

2)ofthe vertex setVsuch that G[V1]

andG[V2]are connected and

Consider the following polynomial-time many-one reduction: Given an instance

G=(V,E)

perFeCtly BalanCed ConneCted partition

, construct an equivalent instance

of FCd by coloring all vertices in G in the same color, setting

k=2

𝓁=|V|∕2

smin =1

and

smax =∞

. Moreover, it is also possible to prove the NP-hardness for the case with

𝓁=0

at the cost of introducing a second color:

Proposition 1 FCD is NP-hard even if G is bipartite,

smin =1

smax =∞

, and (i)

|C|=1

k=2

or (ii)

𝓁=0

|C|=2

,

k=2

Proof To prove the second part, we present a polynomial-time reduction from

perFeCtly

BalanCed ConneCted partition

to FCd. Notably

perFeCtly BalanCed ConneCted parti

tion

is also NP-hard if we are given two vertices

v1,v2∈V

and the question is whether

there is a partition

(V1,V2)

with

v1∈V1

and

v2∈V2

(in the hardness proof by Dyer and

Frieze [18, Theorem2.2], the vertex

always belongs to one partition and

to the other).

Construction. Given an instance

(G=(V,E),v1,v2)

perFeCtly BalanCed ConneCted

partition

with

n∶= |V|

, we construct an instance of FCd: We set

C={c1,c2}

k=2

, and

𝓁=0

. We color all vertices of the given graph G in color

. Moreover, we modify G by

introducing n new vertices of color

. We connect half of these vertices to

and the other

half to

Proof of Correctness. Let

(V1,V2)

be a solution to the FCd instance. As

𝓁=0

and we

require that both

and

need to be non-empty, it needs to hold that both districts contain

vertices of both colors. Moreover, as both

G[V1]

and

G[V2]

are connected, all vertices of

color

adjacent to v need to be in the same district as

(and similarly for

). Thus,

and

need to be in different districts, each consisting of

vertices of color

and

verti-

ces of color

. Thereby, after removing all vertices of color

(V1,V2)

is a solution to the

given

perFeCtly BalanCed ConneCted partition

instance.

To prove the reverse direction, let

(V1,V2)

be a solution to the given

perFeCtly Bal

anCed ConneCted partition

instance with

v1∈V1

and

v2∈V2

. Then, the FCd instance is

a yes-instance, as it is possible to add the

vertices of color

attached to

and the

vertices of color

attached to

to arrive at a solution to the FCd instance.

◻

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

1 3

13 Page 10 of 37

Note that our results strengthen a result of Stoica etal. [48], who proved that FCd is

NP-hard for

|C|=2

and

k=2

if we can additionally specify for each vertex the districts to

which it can be assigned.

As our second basic result, using a simple dynamic programming approach, we show

that an instance of FCd on a disconnected graph is polynomial-time solvable if FCd can

be solved in polynomial time on its connected components. This will play a crucial role,

e.g., in developing an XP-algorithm for the max leaf number (Theorem1).

Proposition 2 Let

be a class of graphs such that

FCD

is polynomial-time solvable on any

graph

G∈G

. Then, FCD is polynomial-time solvable on any graph from

G′

, where

G≃

the class of graphs obtained by taking disjoint unions of graphs from

Proof Let

G�∈G�

and let

G1,…,Gp∈G

be the connected components of

G′

. Clearly,

every district is contained in the vertex set of

for some

i∈[p]

. We solve the problem

using a simple subset-sum like dynamic programming algorithm. To this end, we introduce

a table T[i,j] for

i∈[p]

and

j∈[k]

. An entryT[i,j] is true if one can partition the vertices

G1,…,Gi

into j connected

𝓁

-fair districts respecting the size constraints. We also use a

table H where H[i,j] for

i∈[p]

and

j∈[k]

is true if the vertex set of

can be partitioned

into j connected

𝓁

-fair districts respecting the size constraints. Note that H can be com-

puted in polynomial time by our initial assumption on G.

To initialize T, we set T[1,j] to H[1,j] for all

j∈[k]

. Subsequently, for increasing

i>1

we update T as follows:

In the end, we return T[p,k]. This algorithm runs in

O(p

⋅

k2)=

(n3)

time (aside from the

computation of H).

◻

4 FCD onpaths, cycles, andbeyond

This section studies the computational complexity of FCd on simple graphs and graphs

that can be partitioned into “few” paths and cycles. Specifically, in Sect.4.1, we develop

polynomial-time algorithms on paths, cycles, stars and caterpillars. Subsequently, in

Sect.4.2, we show that FCd is in XP when parameterized by the max leaf number, which

generalizes polynomial-time solvability on paths and cycles.

4.1 Polynomial‑time algorithms forFCD onsimple graph classes

We start by proving that FCd is cubic-time solvable on paths using a simple dynamic pro-

gramming approach.

Proposition 3 FCD on paths can be solved in

O(k

⋅

n2)

time.

[i,j]=

⋁

j�,j�� ∈[j]

�

��

T[i−1, j�]∧H[i,j��]

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

1 3

Page 11 of 37 13

Proof Let

(

,…,v

},{{v

i+1

}∣i∈[n−1]}

)

be the input path. We first cre-

ate a table A[i, j], where A[i, j] for

i≤j∈[n]

is true if and only if

{vi,…,vj}

𝓁

-fair

and

|{vi,…,vj}|=j−i+1∈[smin,smax]

. We then create a tableT with entries T[i,t] for

i∈[n]

and

t∈[k]

. The meaning of an entry T[i,t] is that it is true if there is a partition of

the vertices

{v1,…,vi}

into t paths (connected districts) that are all

𝓁

-fair and respect the

size constraints. Note that the input is a yes-instance if and only if T[n,k] is true.

We initialize tableT by setting T[i,1] for

i∈[n]

to A[1,i]. Subsequently, for

t>1

, we

update the table using:

The reasoning behind this is that if we partition

{v1,…,vi}

into t districts, then there needs

to be some

j∈[i−1]

such that

{vj+1,vj+2,…,vi}

is one district in the solution. Thus, if

T[i,t] is true, then there needs to be some

j∈[i−1]

such that the vertices from

{v1,…,vj}

can be partitioned into

t−1

𝓁

-fair districts respecting the size constraints and the vertices

{vj+1,vj+2,…,vi}

form an

𝓁

-fair district respecting the size constraints.

The table A can be filled in

O(n2)

time: for a fixed

i∈[n]

, we can com-

pute all

A[i,n−j]

for

j∈[0, n−i]

in linear time by starting for

j=0

with com-

puting

𝜒({vi,…,vn−j})

and, subsequently, for increasing

j>1

compute

𝜒({vi,…,vn−j}) = 𝜒({vi,…,vn−j+1}) − 𝜒({vn−j+1})

(which can be done in constant time).

It can be determined in O(1) time whether

𝜒({vi,…,vn−j})

𝓁

-fair by additionally storing

the number of occurrences of integers (which are at most n) in

𝜒({vi,…,vn−j})

. Addi-

tional bookmarking allows us to find the two largest entries in

𝜒({vi,…,vn−j})

O(1)

time. Moreover, the number of occurrences in

𝜒({vi,…,vn−j})

can be updated in

O(1)

time as we increase j. We set

A[i,n−j]

to true if and only if

𝜒({vi,…,vn−j})

𝓁

-fair and

smin ≤n−i−j+1≤smax

Note that table T consists of

k⋅n

entries. We spend

O(n)

time for every entry, resulting

in an overall running time of

O(k

⋅

n2)

◻

To solve FCd on cycles, we iterate over all vertices of the cycle as the starting point of

the first district and split the cycle at this point to convert it into a path. Subsequently, we

employ the algorithm from above, which results in a running time of

O(k

⋅

n3)

Corollary 1 FCD on cycles is solvable in

O(k

⋅

n3)

time.

Next, we proceed to stars, for which we derive a precise characterization of yes-

instances. In fact, using a relatively involved analysis, we consider a more general prob-

lem, in which some set X containing the center vertex must belong to the same district,

i.e., the vertex which is adjacent to all other vertices from the star. This proves useful in

speeding up the algorithms to be presented in Propositions 5 and 7.

Proposition 4 (

★

) Let

(G=(X∪Y,E),C, col, k,𝓁,smin,smax)

be an FCD instance where

G is a star with center vertex

v∈X

. Then, one can decide in linear time whether there is

a partition of

X∪Y

into kconnected

𝓁

-fair districts respecting

smin

and

smax

such that all

vertices from X are part of the same district.

[i,t]=

⋁

j∈[i−1]

T[j,t−1]∧A[j+1, i]

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

1 3

13 Page 12 of 37

Proposition 4 directly implies that FCd is linear-time solvable on stars, even if the

center vertex has a weight for each color, i.e., the center vertex represents multiple ver-

ticesthat all need to be put into one district.

Corollary 2 FCD is linear-time solvable on stars.

Lastly, we extend our polynomial-time algorithm for paths from Proposition 3 to cat-

erpillar graphs. A caterpillar graph is a tree where every vertex is either on a central

path (spine) or a neighbor of a vertex on the central path.

Proposition 5 FCD on caterpillars can be solved in

O(k

⋅

n3)

time.

Proof Let

G=(V,E)

be the given caterpillar, let

(u1,…,up)

denote the spine (central path)

ofG and let

U={u1,…,up}

. Moreover, for

i∈[p]

, let

consist of

and all vertices from

V⧵U

adjacent to

. Note that each vertex from

V⧵U

is only adjacent to one vertex from

U, as G is in particular a tree. We solve the problem by extending our algorithm for paths

from Proposition 3.

As a first step, we introduce a table A[i,j,t] for

i≤j∈[n]

and

t∈[k]

. An entry A[i,j,t]

is set to true if there is a partition

(V1,…,Vt)

⋃i

�

∈[i,j]

�

into t districts such that:

•

contains

ui′

for every

i�∈[i,j]

, and

•

Vt′

𝓁

-fair,

|Vt

�

|∈[smin,smax]

, and

G[Vt

�

]

is connected for every

t�∈[t]

We can fill table A in

O(k

⋅

n3)

time using Proposition 4 for each A[i,j,t] (for this, it is nec-

essary to slightly restructure

G[⋃i

�

∈[i,j]

Ui�

]

as a star

G′

⋃i

�

∈[i,j]

�

with

as the center

vertex and

X={ui,…,uj}

). Using A, we now apply dynamic programming. To this end,

we introduce a table T[i,t] for

i∈[n]

and

t∈[k]

. Entry T[i,t] is set to true if it is possible

to partition the vertices from

⋃j∈[i]Uj

into t connected districts that are

𝓁

-fair and respect

the size constraints. We initialize the table by setting T[i,1] to true if

⋃j∈[i]

𝓁

-fair.

Subsequently, for

t>1

, we update the table using:

The reasoning behind this equality is that in a partitioning of

⋃j∈[i]Uj

into t districts, there

needs to be some

j∈[i−1]

such that there is one district containing vertices

{uj+1,…,ui}

However, not all vertices from

⋃t∈[j+1,i]Ut

need to be part of this district. In fact, because

of the connectivity constraints, there is some

t′′

such that one district contains vertices

{uj+1,…,ui}

and all but

t�� −1

vertices from

⋃t∈[j+1,i]Ut

and

t�� −1

districts consist of a

single vertex from

⋃t∈[j+1,i]

(such a partitioning respecting fairness and size constraints

exists if and only if

A[j+1, i,t��]

is true). The remaining

t−t��

districts then consists of ver-

tices from

⋃t∈[j]

(such a partitioning respecting fairness and size constraints exists if and

only if

T[j,t�]

is true). Table T has

k⋅n

entries each computable in

O(k⋅n)

time. This leads

to an overall running time of

O(k

⋅

n3)

◻

Note that a graphG has pathwidth one (

pw (G)=1

) if and only if G is a disjoint

union of caterpillars. By Proposition 2 and Proposition 5, it follows that FCd is

[i,t]=

⋁

j∈[i−1]∧t�,t�� ∈[t]∶

�

��

T[j,t�]∧A[j+1, i,t��]

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

1 3

Page 13 of 37 13

polynomial-time solvable on all graphs with pathwidth one (we later show in Corollary

4 that FCd is NP-hard on pathwidth-two graphs).

Corollary 3 FCD on a graphG with

pw (G)=1

is polynomial-time solvable.

4.2 An XP‑algorithm for

mln

Now, we generalize the polynomial-time solvability on paths and cycles to a larger graph

class. More precisely, we develop an XP-algorithm for the max leaf number (

mln

). Recall

that the max leaf number of a connected graph G is the maximum number of leaves over

all spanning trees of G. Notably, any path or cycle has

mln =2

. In order to develop a

polynomial-time algorithm for constant

mln

, we use the notion of branches. (See Fig.2 for

an illustration.)

Definition 1 A branch in a graph is either a maximal path in which all inner vertices have

degree two or a cycle in which all but one vertex have degree two.

Using a classical theorem of Kleitman and West[31], Eppstein[22] showed that any

graph has at most

O(mln 2)

branches. For notational brevity, we assume that every branch

B that is a cycle has exactly one endpoint, namely, the vertex in B with degree at least three

in G (if there is no such vertex in B, then we fix an arbitrary vertex as its endpoint).

Theorem1 FCD can be solved in

O(mln

time.

Proof Let

be the set of all branches of the given graph G and let X be the set of all

endpoints of all branches. Suppose that there is a solution

V=(V1,…,Vk)

. Observe that

there are naturally at most

|X|

subsets in

containing at least one vertex from X. Without

loss of generality, assume that

contains at least one vertex from X for

i∈[k�]

for some

k�∈[min(k,|X|)]

, and let

Xi=X∩Vi

. Let us now consider the relationship between a dis-

trict

for

i∈[k�]

and a branch

B=(v1,…,vl)∈B

(where for all

i∈[l−1]

and

vi+1

are

adjacent in G and if B is a cycle, then

v1=vl

). Since

induces a connected subgraph in G,

the following holds:

• If

v1,vl∉Xi

, then

and B are disjoint: Since

is connected and contains at least one

vertex from

X⧵{v1,vl}

contains no “inner” vertices from B.

• If

v1∈Xi

and

vl∉Xi

, then there is an integer

j∈[l−1]

such that

Vi∩{v1,…,vl}={v1,…,vj}

(for

v1∉Xi

and

vl∈Xi

, the situation is symmetric).

• If

v1,vl∈Xi

for some

i∈[k]

, then there are two integers

j,j�∈[l]

such that

Vi∩{v1,…,vl}={v1,…,vj}∪{vl−j

�

+1,…,vl}

. Note that

contains all vertices of B

when

j+j�=l

Fig. 2 An illustration of a

graph with four branches:

(v1,v2,v3),(v3,v5),(v3,v4,v6,v5),(v5,v7,v8)

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

1 3

13 Page 14 of 37

For all other districts

i∈[k�+1, k]

, it holds that there is a branch

(v1,…,vl)∈B

with

Vi⊆{v2,…,vl−1}

Using these observations, our algorithm proceeds as follows. We iterate over all possible

combinations of the following (note that the number of combinations is

)

O(mln

• An integer

k�∈[min(k,|X|)]

• A partition

X=(X1,…,Xk

�

)

of X into

k′

subsets.

• For every branch

B=(v1,…,vl)∈B

, two integers

jB,j�

B∈[l]

with

jB+j�

≤

Using these guesses, we can exactly determine the districts intersecting X: For every

i∈[k�]

and every branch

B=(v1,…,vl)∈B

, we define

Vi,B

as follows:

• If

v1,vl∉Xi

, then

Vi,B∶= �

• If

v1∈Xi

and

vl∉Xi

, then

Vi,B∶= {v1,…,vjB}

. Symmetrically, if

v1∉Xi

and

vl∈Xi

then

i,B

∶= {v

l−j�

,…,v

}

• If

v1,vl∈Xi

, then

i,B

={v

,…,v

B}∪{v

l−j�

,…,v

}

For

i∈[k�]

, let

Vi∶= ⋃B∈BVi,B

. We check whether the set

𝓁

-fair and respects the size

constraints for every

i∈[k�]

. If there is a

that is not

𝓁

-fair or violates the size constraints,

then we proceed to the next combination. Otherwise, it remains to determine whether the

vertices

⧵

⋃i∈[k

�

]

can be partitioned into

k−k�

𝓁

-fair districts that respect the size con-

straints. Since

G[V⧵⋃i∈[k

�

]Vi]

is a disjoint union of paths as all endpoints of branches are

contained in

⋃i∈[k

�

]

this can be done in polynomial time by Propositions 2 and 3.

◻

We leave it open whether FCd parameterized by

mln

is fixed-parameter tractable or

W[1]-hard.

5 FCD ontrees andtree‑like graphs

After having seen in Sect. 4 that FCd is polynomial-time solvable on paths, cycles, stars,

and caterpillars, we now turn to trees. In Sect. 5.1, we prove that these polynomial-time

results do not extend to trees. In particular, we prove that FCd on trees is NP-hard and

W[1]-hard parameterized by

|C|+k

. We complement these hardness results with an XP-

algorithm for FCd on trees parameterized by

|C|

and another XP-algorithm for parame-

terk. In fact, both XP-algorithms further extend to tree-like graphs: In Sect. 5.2, we prove

that FCd parameterized by the treewidth of the given graph plus

|C|

is in XP. Subsequently,

in Sects. 5.3 and 5.4, we consider the feedback edge number (

fen

) and the feedback vertex

number (

fvn

), which are both alternative measures for the tree-likeness of a graph (the

treewidth of a graph can be upper bounded in a function of

fen

and in a function of

fvn

Thus, the XP algorithm for

tw +|C|

extends to the parameter combinations

fvn +|C|

and

fen +|C|

, which is why we focus on the parameter combinations

fvn +k

and

fen +k

here. We prove that FCd parameterized by

fen +k

is in XP and we show that there is

(presumably) no such result for the treewidth and the feedback vertex number (

fvn

) by

showing that FCd is NP-hard even if

fvn =1

tw =2

, and

k=2

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

1 3

Page 15 of 37 13

5.1 W[1]‑hardness ontrees

In this subsection, we show that in contrast to paths, cycles, stars, and caterpillars, FCd on

trees is NP-hard even without size constraints. Simultaneously, we show that FCd param-

eterized by the number k of districts and the number

|C|

of colors is W[1]-hard on trees. To

this end, we present a parameterized reduction from the following version of

grid tiling

which is NP-hard and W[1]-hard with respect to t [41] (in this subsection, all indices are

taken modulot):

Grid Tiling

Input: AcollectionSof t2(tile)setsSi,j⊆[m]×[m], i, j∈[t], where

each Si,jconsists of npairsand thefirstentries of allpairs

(tiles) from Si,jsumuptothe same number Xforall i, j∈[k]

andthe second entriesofall pairsfrom Si,jsumuptothe same

number Yforall i, j∈[k]¸.

Question:Canone choose onetile(

xi,j,yi,j)∈Si,jforeachi, j∈[t]such

that xi,j=xi+1,j andyi,j=yi,j+1?

Without loss of generality, we assume that

n>2

The general idea of the reduction is as follows. Each solution to the constructed FCd

instance has a center district. The center district contains some large numberZ of vertices

of two “dummy” colors c and

c′

. The instance is constructed such that in every solution,

vertices of any fixed color can appear at most Z times in the center district. By definition,

each tile (x,y) belongs to one of

tile sets

Si,j∈S

. We construct a star

Ti,j

x,y

for each tile

such that for each tile set

Si,j∈S

, all but exactly one star

Ti,j

x,y

need to be contained in the

center district. Thus, the center district (respectively its complement) basically encodes a

selection of one tile from each tile set. Moreover, we construct the FCd instance in such

a way that for two stars from two “adjacent” tile sets the respective first or second entries

of the tiles need to match; otherwise the number of vertices of some color in the central

district will exceed Z.

5.1.1 Construction

Let

(S,t,m,n,X,Y)

be an instance of

GRID TILING

. We construct an instance of FCd as

follows.

First of all, we set

𝓁=0

smin =1

smax =∞

, and

k=t2+1

. For each

i,j∈[t]

, we intro-

duce three distinct colors

bi,j

di,j

, and

ci,j

. Moreover, we introduce three distinct colors

c′

, and

c⋆

. Now, we fix some constants which we use later. Let

W∶= 5n(t2+t)+1

Z∶= 2(n−1)⋅5mW

f(i,j) ∶= i⋅t+j

, and

g(i,j) ∶= t2+t+i

⋅

t+j

. Note that this

implies that

W≥2.5 ⋅n⋅g(i,j)

and

W≥2.5 ⋅n⋅f(i,j)

for all

i,j∈[t]

We are now ready to construct the vertex-colored graph

G=(V,E)

. We start by intro-

ducing a center vertex

vcenter

of color

c⋆

. In a solution, we call the district containing

vcenter

the center district. We add Z vertices of color c and Z vertices of color

c′

, all of which are

only adjacent to

vcenter

For each

i,j∈[t]

and

(x,y)∈Si,j

, we construct a star

Ti,j

x,y

and connect its center to

vcenter

We color the center of

Ti,j

x,y

c⋆

. Moreover,

Ti,j

x,y

has the following leaves:

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

1 3

13 Page 16 of 37

•

2(n−1)

+W⋅x−f(i,j

)

vertices of color

di,j

•

2(n−1)

−W⋅x−f(i�,j

)

vertices of color

′

for

i�∶= i+1mod k

•

2(n−1)

+W⋅y−g(i,j

)

vertices of color

bi,j

•

2(n−1)

−W⋅y−g(i,j�

)

vertices of color

bi,j′

for

j�∶= j+1mod k

, and

•

max

(

2(n−1)

+W⋅x−f(i,j),

2(n−1)

+W⋅y−g(i,j

))

vertices of color

ci,j

Observe that the constructed star

Ti,j

x,y

is 0-fair, as the number of occurrences of

ci,j

matches

the number of occurrences of the otherwise most frequent color. This concludes the

construction.

5.1.2 Proof ofcorrectness

We start with a simple observation on the total number of vertices of some of the colors:

Observation 1 For each

i,j∈[t]

, it holds that

𝜒

i,j

(V)=

n−1

Z−2nf (i,j

)

and

𝜒

i,j

(V)=

n−1

Z−2ng(i,j

)

. For all

i,j∈[k]

, it holds that

𝜒

i,j(V)≤Z

Proof For each

i,j∈[t]

, vertices of color

di,j

occur in 2n different stars, that is, in all stars

corresponding to tiles from

Si,j

and

Si−1,j

. As the first entries of all tiles from

Si,j

and of all

tiles from

Si−1,j

sum up to X, it follows that

The same reasoning applies for all colors

bi,j

proving that

𝜒

i,j(

)= n

n−1

−

2ng

(

i,j

)

. Lastly,

for some

i,j∈[t]

, vertices of color

ci,j

appear only in stars corresponding to tiles from

Si,j

each of them containing at most

2(n−1)

+W⋅

such vertices. Thus, the number of vertices

of color

ci,j

is upper-bounded by

⋅(

2(n−1)

+W⋅m

)

. As

⋅m=

8(n−1)

Z and

n>2

, this is

smaller than Z from which

𝜒

i,j(V)≤Z

follows.

◻

Using Observation 1, we now prove the forward direction of the correctness of the

construction.

Lemma 1 If the given

GriD TilinG

instance is a yes-instance, then the constructed FCD

instance is a yes-instance.

Proof Let

S= {(xi,j

,yi,j)∈Si,j∣i,j∈[t]}

be a solution for the given

grid tiling

instance.

From this we construct a solution of the FCd instance as follows. For each

(xi,j

,yi,j)∈S

we create a separate district and put into this district all vertices from the star

Ti,j

x,y

corre-

sponding to

(xi,j

,yi,j)

. We put all other vertices in the center district. Note that this construc-

tion respects the given number

k=t2+1

of districts and that all districts are by construc-

tion non-empty and connected.

𝜒

di,j(V)=

∑

(x,y)∈Si,j

2(n−1)+Wx −f(i,j)+

∑

(x,y)∈Si−1,j

2(n−1)−Wx −f(i,j

)

=(n

2(n−1)Z+WX −nf (i,j))+(n

2(n−1)Z−WX −nf (i,j))

n−1

Z−2nf (i,j).

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

1 3

Page 17 of 37 13

It remains to argue that all created districts are 0-fair. Since every star is 0-fair by con-

struction, all non-center districts are 0-fair. For the center district, note that it contains Z

vertices of color c and Z vertices of color

c′

. Thus, it is sufficient to argue that there is no

color such that the number of its occurrences in the center district exceedsZ. For color

ci,j

this directly follows from Observation 1. Next we consider color

di,j

for some

i,j∈[t]

. All

stars with some vertices of color

di,j

are part of the center district, except for the one cor-

responding to

(xi,j

,yi,j)

and the one corresponding to

(xi−1,j,yi−1,j)

. Since S is a solution,

we have

xi−1,j=xi,j

. Consequently, exactly

n−1

−2f(i,j

)

vertices of color

di,j

are excluded

from the center district. Now it follows from Observation 1 that the number of vertices of

color

di,j

in the center district is at mostZ. An analogous argument also holds for

bi,j

for

i,j∈[t]

, which concludes the proof.

◻

It remains to prove the correctness of the backward direction. To do this, we first

observe that for every star, all of its vertices have to belong to the same district. Subse-

quently, we prove that the center district can contain at most Z vertices of each color. We

then show that in order to respect this bound, for each tile set, exactly one star correspond-

ing to a tile from this set must be excluded from the center district. Again exploiting the

fact that every color has at most Z occurrences in the center district, we show that those

excluded tiles form indeed a solution to the given

grid tiling

instance. We start by observ-

ing that the vertices from one star need to be part of the same district.

Observation 2 For each tile

(x,y)∈S

, all vertices from the corresponding star need to be

part of the same district in a solution to the constructed FCd instance.

Proof As we set

𝓁=0

in the constructed FCd instance, there cannot exist a district con-

taining just a single vertex. Thus, all vertices from a star need to belong to the same district

as the center of the star.

◻

Using this observation, we make some more involved arguments dealing with the pos-

sible number of vertices of a color in the center district in a solution. In the following, let

Vcenter

denote the center district in a solution to the constructed FCd instance. We make

this observation in order to ensure that no two different colors appear the same number of

times and in particular more than Z times in the center district.

Lemma 2 For each

i,j∈[t]

, if

𝜒

i,j(V

center

)

≥

, then the number α of stars

Ti,j

x,y

with some

vertex of color

di,j

that are not part of the center district is at most two. In particular, it

holds that

𝜒

di,j(Vcenter)=(

n−1

Z−2nf (i,j)) − 𝛼(

2(n−1)

−f(i,j)) +

for some

q∈ [−2m,2m]

Proof Let us consider some

i,j∈[t]

. By Observation 2, for every star

Ti,j

x,y

, all the vertices

from

Ti,j

x,y

are in

Vcenter

or no vertex from

Ti,j

x,y

is in

Vcenter

By construction, every star with some vertex of color

di,j

contains

2(n−1)

+W⋅x−f(i,j

)

vertices of this color for some

x∈ [−m,m]

. So as there are

n−1

Z−2nf (i,j

)

vertices of color

di,j

(Observation 1), if

𝛼≥3

, then the number of vertices of color

di,j

in the center district is

at most

−

2(n−1)

+3mW . By the definition of Z this is smaller than Z.

Thus, we obtain

𝛼≤2

. Since there are in total

n−1

Z−2nf (i,j

)

vertices of color

di,j

Observation 2, the lemma holds.

◻

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

1 3

13 Page 18 of 37

Analogously, we can prove similar bounds for the number of vertices of color

bi,j

for

some

i,j∈[t]

in the center district.

Lemma 3 For each

i,j∈[t]

, if

𝜒

i,j(V

center

)

≥

, then the number α of stars

Ti,j

x,y

with some

vertex of color

bi,j

that are not part of the center district is at most two. In particular, it

holds that

𝜒

bi,j(Vcenter)=(

n−1

Z−2ng(i,j)) − 𝛼(

2(n−1)

−g(i,j)) +

for some

v∈ [−2m,2m]

Using these two lemmas, we can now prove that there are at most Z vertices of the same

color in the center district in a solution to the constructed FCd instance.

Lemma 4 For every color q,

𝜒q(Vcenter)≤Z

Proof We claim that for two distinct colors

q,q′

with

𝜒q(Vcenter),𝜒q

�

(Vcenter)>Z

, it holds

that

𝜒q(Vcenter)≠𝜒q

�

(Vcenter)

. The statement of the lemma directly follows from the claim,

Vcenter

needs to be 0-fair.

Assume for a contradiction that

𝜒q(Vcenter)=𝜒q

�

(Vcenter)>Z

for some colors

q≠q′

Since there are at most Z vertices of color

′

⋆

i,j

for

i,j∈[t]

, q and

q′

are among the

colors

bi,j

and

di,j

for

i,j∈[t]

. By Lemmas 2 and 3 and as it holds that

𝜒q(Vcenter)=𝜒q

�

(Vcenter)

, from this it follows that

nh(i,j)+a

2(n−1)

−h(i,j)

)

+Wv =2nh�(i�,j�)+a�

2(n−1)

−h�(i�,j�)

)

+Wv

�

, for some

a,a�∈{0, 1, 2}

v,v�∈ [−2m,2m]

h(i,j)∈{f(i,j),g(i,j)}

, and

h�(i�

,j�)∈{f(i�

,j�),g(i�

,j�)}

. Rewriting yields that

(5m(a−a�)+v−v�)W=(2n−a�)h�(i�,j�)−(2n−a)h(i,j)

. Since W is sufficiently large,

the absolute value of the right-hand side does not exceed W. Thus, we have

5m(a−a�)+v−v�=0

and

(2n−a)h(i,j)=(2n−a�)h�(i�,j�)

. The first equation implies

a=a�

since

v−v�∈ [−4m,4m]

. Cancelling out

2n−a>0

in the second equation, we

obtain

h(i,j)=h�(i�

,j�)

. Now we have

q=q�

, as



≠



i�



j�)

for all



i�



j�∈[t]



j)=f(



i�



j�)

only if



i�

and



j�

, and



j)=g(



i�



j�)

only if



i�

and



j�

. We

have reached a contradiction.

◻

Using Lemma 4, we can prove that each solution to the constructed FCd instance

induces a selection of one tile from each tile set in the given

grid tiling

instance:

Lemma 5 For each

i,j∈[t]

, exactly one star

Ti,j

x,y

for some

(x,y)∈Si,j

is not part of

Vcenter

Proof Lemma 2 and Lemma 4 imply that for each

i,j∈[t]

at least two stars containing ver-

tices of color

di,j

are not part of

Vcenter

. As each star

Ti,j

x,y

contains vertices of colors

di,j

and

di+1,j

and as there exist

non-center districts in the end, this means that for each

i,j∈[t]

exactly two stars containing vertices of this color are not part of

Vcenter

For the sake of contradiction, let us assume that there exists

i,j∈[t]

such that two stars

corresponding to tiles

(x,y),(x�

,y�)∈Si,j

are not part of

Vcenter

. This implies by our previous

observation that all other stars containing vertices of color

di+1,j

need to belong to

Vcenter

However, in this case,

n−1

−W(x+x�)−2f(i,j)≤

n−1

−2W vertices of color

di+1,j

are not

part of

Vcenter

. By Observation 1, this implies that the number of vertices of color

di+1,j

Vcenter

is at least

Z+2W−2nf (i,j)

. As

W>n(t2+t)

, this number is greater thanZ, contra-

dicting Lemma 4.

◻

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

1 3

Page 19 of 37 13

Putting all pieces together, we are now ready to prove the correctness of the backward

direction of the construction.

Lemma 6 If the constructed FCD instance is a yes-instance, then the given

GriD TilinG

instance is a yes-instance.

Proof Let

be a solution to the constructed FCd instance and let

Vcenter ∈V

be the district

containing

vcenter

. Lemma 5 implies that for each

i,j∈[t]

exactly one star corresponding to

a tile from

Si,j

is not part of

Vcenter

. Let

be a set of all tiles corresponding to excluded stars (one for each

i,j∈[t]

). We claim that S

is a valid solution to the given

grid tiling

instance.

For the sake of contradiction, assume that this is not the case. That is, there either (a)

exist

i,j∈[t]

such that

xi,j≠xi−1,j

or (b) exist

i�

,j�∈[t]

such that

�

�≠y

�

�−1

. Let us start

by assuming that (a) is the case. Note that it is possible to assume without loss of generality

that

xi,j<xi−1,j

, as from the fact that there exists some

xi,j≠xi−1,j

it follows that there also

exists some



i∈[t]

such that

x

i,j

<x

i−1,

. The only stars containing vertices of color

di,j

that

are not part of

Vcenter

are the star corresponding to

(xi,j

,yi,j)

, which contains

2(n−1)

+W⋅xi,j−f(i,j

)

vertices of this color, and the star corresponding to

(xi−1,j,yi−1,j)

which contains

2(n−1)

−W⋅xi−1,j−f(i,j

)

vertices of this color. This implies that at most

n−1

+W⋅(xi,j−xi−1,j)−2f(i,j)≤

n−1

−W−2f(i,j

)

vertices of this color are not part of

Vcenter

, where the inequality holds by our assumption that

xi,j<xi−1,j

. Combining this with

Observation 1, it follows that the number of vertices of color

di,j

Vcenter

is at least

Z+W−2(n−1)f(i,j)

. By the definition of W, this is strictly greater than Z. Applying

Lemma 4, we reach a contradiction.

The same argument can also be applied if (b) holds, which proves that S is a solution to

the given

grid tiling

instance.

◻

From Lemma 1 and Lemma 6 the correctness of the reduction follows. As our construc-

tion takes only polynomial time and

|C|+k=3t2+4

is bounded in a function of t, the NP-

hardness and the W[1]-hardness with respect to

|C|+k

of FCd on treesfollows.

Theorem 2 FCD on trees is NP-hard and W[1]-hard with respect to

|C|+k

, even if

smin =1

and

smax =∞

Recall that by Corollary 3, FCd can be solved in polynomial time on all graphs with

pathwidth one (disjoint unions of caterpillars). Observe that the tree constructed in the

reduction above has pathwidth two: Graph

G′

obtained from G by deleting

vcenter

is a dis-

joint union of stars. Thus,

G′

admits a path decomposition of width one. Placing

vcenter

into

every bag yields a path decomposition of G of width two. This results in the following.

Corollary 4 FCD on graphsG with

pw (G)=2

is NP-hard and W[1]-hard with respect

to

|C|+k

, even if

smin =1

and

smax =∞

To be more precise, we even get NP-hardness and W[1]-hardness with respect to

|C|

on a pathwidth one graph to which we add a single vertex and adjacent edges. Notably, this

∶= {(x

i,j

)∈S

i,j

∣i,j∈[t]∧T

i,j

x,y

is not part of Vcenter

}

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

1 3

13 Page 20 of 37

result is tight in the sense that we have proved polynomial-time solvability on pathwidth-

one graphs in Corollary 3.

As the tree constructed in the previous reduction has diameter four (it consists of a

center vertex and centers of stars attached to it), we conclude that FCd is computationally

intractable even on trees with a small constant diameter:

Corollary 5 FCD is NP-hard and W[1]-hard with respect to

|C|+k

on trees with diameter

four, even if

smin =1

and

smax =∞

We will complement this result in Corollary 8 where we show that FCd is polynomial-

time solvable on trees with diameter at most three.

5.2 An XP‑algorithm for

𝐭𝐰

|𝐂|

Motivated by the hardness result from the previous subsection, we search for an XP-algo-

rithm for the parameters

|C|

and k for FCd on trees. We start by considering the parameter

|C|

here and the parameter k in the next two subsections. Specifically, we show that there

exists an XP-algorithm for

|C|

on tree-like graphs—more precisely, we present an XP-algo-

rithm with respect to

|C|+tw

, where

is the treewidth of the underlying graph.

Given a graph

G=(V,E)

, a tree decomposition

(T=(VT,ET),{Bx}x∈VT)

of G (as

defined in the Preliminaries) is nice if each node

x∈VT

has one of the following types5:

Leaf node. A leaf of T with

Bx={v}

for

v∈V

Introduce vertex v node. An internal node of T with one child

y∈VT

such that

Bx=By∪{v}

Introduce edge

{u,v}

node. An internal node of T with one child

y∈VT

such that

u,v∈Bx=By

Forget v node. An internal node of T with one child

y∈VT

such that

Bx=By⧵{v}

for

v∈By

Join node. An internal node of T with two children

y∈VT

and

z∈VT

such that

Bx=By=Bz

We will implicitly assume that every introduce edge

{u,v}

node is labeled by

{u,v}

and

that for each edge there is exactly one such node. Given a tree decomposition, a nice tree

decomposition of equal width can be computed in linear time [32]. By applying dynamic

programming on top of the nice tree decomposition of the given graph, we establish the

following:

Theorem3 (

★

) FCD can be solved in

O(nO(tw ⋅|C|))

time.

Since a tree is of treewidth one, we have the following:

Corollary 6 FCD on trees can be solved in

nO(|C|)

time.

5 Note that in the following we refer to the elements of V as vertices and the elements of

as nodes. We

refer to the set

for a node

x∈VT

as a bag.

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

1 3

Page 21 of 37 13

5.3 An XP‑algorithm for

fen +k

Having constructed a polynomial-time algorithm for constant

|C|

on trees and on graphs

with a constant treewidth, we now consider the number k of districts as our parameter for

FCd on trees. We show that there is a simple XP-algorithm with respect to k for FCd on

trees, which naturally extends to an XP-algorithm with respect to

fen +k

, where

fen

is the

number of edges that need to be deleted to make the given graph atree:

Proposition 6 FCD can be solved in

nO(fen +k)

time.

Proof Suppose that there is a solution

(V1,…,Vk)

. As for each

i∈[k]

is connected (for

which at least

|Vi|−1

edges are needed), the number of edges whose endpoints both lie

in the same district is at least

∑k

i=1

(

�

i�

−1)=n−

. Since the input graph

G=(V,E)

has at most

n+fen −1

edges (by the definition of

fen

), it follows that there are at most

(n+fen −1)−(n−k)= fen +k−1

edges whose endpoints belong to different districts.

Accordingly, in our algorithm for each edge set

E′⊆E

of size at most

fen +k−1

, we

verify whether

(V,E⧵E�)

has k connected components each of which being

𝓁

-fair and

respecting the size constraints. We return yes if this is the case for some subset of edges

and no otherwise. Overall, it takes

(n+fen −1)fen +k−1

⋅

nO(1)=nO(fen +k)

time to do so.

◻

As the treewidth of a graph is upper-bounded in a function of its feedback edge number,

we can conclude from Theorem3 that FCd parameterized by

fen +|C|

is in XP. However,

Proposition 6 leaves it open whether there is an XP-algorithm for

tw +k

. We answer this

question negatively in the next subsection.

5.4 NP‑hardness for

𝐟𝐯𝐧 =𝟏

and

k=2

Having already considered the parameters treewidth and feedback edge number, we now

consider a third way to measure the distance from a tree, the number of vertices to delete to

make it a tree (feedback vertex number

fvn

). As

tw +1≤fvn

, from Theorem3 it follows

that there is an XP-algorithm for

fvn +|C|

. We now prove that FCd is NP-hard even for

fvn =1

and

k=2

, in contrast to the result from the previous subsection, where we gave an

nO(fen +k)

-time algorithm. Notably, this NP-hardness result also excludes the existence of an

XP-algorithm for

tw +k

unless P

NP:

Theorem4 FCD is NP-hard for

fvn =1

and

k=2

, even if

smin =1

and

smax =∞

The rest of the section is devoted to proving the theorem. We reduce from the NP-hard

not-all-equal 3-sat

problem [46] where the input is a set X of n boolean variables and

a setY of mclauses overX such that each clause

y∈Y

contains three different literals,

and the question is whether there exists a truth assignment to the variables inX such that

for each clause

y∈Y

at least one literal is set to true and at least one literal is set to false.

Notably, given an assignment fulfilling these constraints, the assignment that assigns all

variables in X the opposite truth value also fulfills the constraints.

The general idea of the construction is that we introduce one vertex for each literal and

that the two districts in the solution correspond to two opposite truth assignments of the

variables from X that are both solutions of the

not-all-equal 3-sat

instance.

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

1 3

13 Page 22 of 37

5.4.1 Construction

Given an instance

(X={x1,…,xn},Y={y1,…,ym})

not-all-equal 3-sat

, we con-

struct an instance of FCd as follows. We add a color

for each variable

xi∈X

and a

color

for each clause

yj∈Y

. In addition, we add three colors c,

c′

, and

c′′

. Moreover, we

set

k=2

𝓁=0

smin =1

, and

smax =∞

. Let

Z∶= 2⋅n⋅m+1

We start the construction of the vertex colored graph

G=(V,E)

by introducing two

central vertices

v⋆

and

v⋆

of colorc. We will construct the instance in a way that these two

vertices need to lie in different districts. For each central vertex

v⋆

i∈{1, 2}

, we introduce

3Zvertices of color

c′

and 3Zvertices of color

c′′

and connect them to

v⋆

Subsequently, for each variable

xi∈X

, we introduce two literal vertices

and

color c and connect both these vertices to the two central vertices. For each literal vertex

vi∈{vi,vi}

, we introduce

3Z−i

vertices of color

and connect them to

vi

(these vertices

make sure that the two literal vertices end up in different districts). For each clause

yj∈Y

in which

occurs positively, we introduce

Z+j

vertices of color

and connect them to

For each clause

yj∈Y

in which

occurs negatively, we introduce

Z+j

vertices of color

and connect them to

(these vertices ensure that there is no clause in which all three literal

vertices corresponding to literals from the clause lie in the same district). See Fig.3 for a

visualization of the construction.

We start by showing the forward direction of the correctness of the construction.

Fig. 3 Example of the hardness reduction from Theorem 4 for the

not-all-equal 3-sat

instance

X={x1,x2,x3}

x1,x2,x3

}

,y2

x1,x2,x3

}

,y3

x1,x2,x3}}

. The district marked in

red corresponds to the solution setting

to true and

and

to false

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

1 3

Page 23 of 37 13

Lemma 7 If the given

noT

All

EquAl

SAT

instance is a yes-instance, then the constructed

FCD instance is a yes-instance.

Proof Let

X′⊆X

be the set of variables set to true in a solution to the given

not-all-

equal 3-sat

instance. From this, we construct a solution

(V1,V2)

to the constructed FCd

instance as follows. We include

v⋆

and all leaves attached to it in

. Moreover, we include

the following vertices:

and all leaves attached to it for all

xi∈

�

and

and all

leaves attached to it for all

xi∈X⧵X�

. We include all other vertices in

It is easy to verify that

and

are both connected. We will show that

is 0-fair. By

symmetry, an analogous argument will show that

is 0-fair. First, observe that

contains

exactly 3Z vertices of color

c′

and 3Z vertices of color

c′′

. We show that

𝜒c(V1)≤3Z

for

every color

c∈C

. For colorc, we have that

𝜒c(V1)

≤

𝜒c(V)=n+2<3Z

. For each varia-

ble

xi∈X

, as the two corresponding literal vertices are part of different districts, we have

that

𝜒

)=3Z−i<3Z

. For each clause

yj∈Y

, as

X′

is a solution, either one or two

literal vertices corresponding to literals in

and the attached leaves are part of

. Thus,

the number of vertices of color

is either

Z+j

2Z+2j

. As

Z>2m

, it follows that

𝜒

)<3Z

. Thus, both districts

and

are 0-fair.

◻

It remains to prove the correctness of the backward direction of the reduction. For this,

note that the FCd instance is constructed such that the two central vertices need to end up

in different districts and for each

xi∈X

, the two literal vertices

and

need to end up in

different districts. Thus, the two districts correspond to two inverse truth assignments. Sub-

sequently, we will prove that there is no clause in which all corresponding vertices are in

the same district. This will show that the two truth assignments induced by the two districts

are a solution to the given

not-all-equal 3-sat

instance.

We start by observing that all leaves need to lie in the same district as the vertex they

are attached to.

Observation 3 In a solution to the constructed FCd instance, all leaves attached to a ver-

tex

v∈V

need to lie in the same district as v.

Proof If a leaf is not in the same district as its neighbor, then the leaf needs to form its own

district. However, this is not possible, as we require each district to be 0-fair.

◻

Next, we show that indeed the two central vertices

v⋆

and

v⋆

always lie in different

districts.

Observation 4 The two central vertices

v⋆

and

v⋆

cannot belong to the same district in any

solution to the constructed FCd instance.

Proof Assume that

v⋆

and

v⋆

belong to the same district. By Observation 3, the other dis-

trict

V′

needs to consist of a single literal vertex

for some

xi∈X

and all leaves

attached to it. The most frequent color appearing in

V′

which occurs

3Z−i>2Z

times

(by the definition of Z). The second most frequent color is either

for some

j∈[m]

occur-

ring

Z+j<2Z

times or c occurring once (by the definition of Z). Thus, the district cannot

be 0-fair.

◻

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

1 3

13 Page 24 of 37

To prove that, for each variable, the two corresponding literal vertices need to be part of

different districts and that not all literal vertices corresponding to literals from a clause can

lie in the same district, we prove that neither district can contain more than 3Z vertices of

the same color.

Lemma 8 For any solution to the constructed FCD instance, no district contains more than

3Z vertices of the same color.

Proof Assume that there exists a solution with a district

V′

containing more than

3Z vertices of the same color. Since

V′

is 0-fair, there are two colors q and

q′

with

𝜒q(

�)=

𝜒

�

(

�)

. We have

𝜒c(

�)

≤𝜒

(

2<3Z and

𝜒c

�

(

�)=

𝜒

��

(

�)=

by Observation 4. Thus, we have

�

∈{c

∣xi∈X}∪{c

∣yj∈Y

}

For

xi∈X

, there are two literal vertices each of which have

3Z−i

leaves of color

attached to it. For

yj∈Y

, there are three literal vertices each of which have

Z+j

leaves of

color

attached to it. It follows from Observation 3 that

𝜒

(

�)∈{

0, 3Z

−

i,6Z

−

}

for

each

xi∈X

and that

𝜒

(V�)∈{0, Z+j,2Z+2j,3Z+3j}

for each

yj∈Y

. Since

i≤n

j≤m

Z=2⋅n⋅m+1

, and

𝜒q(V�)=𝜒q

�

(V�)

for

�

∈{c

∣xi∈X}∪{c

∣yj∈Y

}

, it

needs to hold that

𝜒q(

�)=

𝜒

�

(

�)=0

, which contradicts

𝜒q(

�)=

𝜒

�

(

�)

>3Z .

◻

Recalling that

3Z−i

vertices of color

are attached to each literal vertex correspond-

ing to

xi∈X

and that

6Z−2i>3Z

, the next observation directly follows from the previ-

ous lemma and Observation 3.

Observation 5 Let

(V1,V2)

be a solution of the constructed FCd instance. Then, for each

xi∈X

, exactly one of the two corresponding literal vertices

and

is part of

and the

other is part of

We are now ready to prove the backward direction of the correctness of our construction.

Lemma 9 If the constructed FCD instance is a yes-instance, then the given

noT

All

EquAl

SAT

instance is a yes-instance.

Proof Let

(V1,V2)

be a solution to the constructed FCd instance. From Observation 5, it

follows that for each

xi∈X

, exactly one of

and

is part of

. Let

𝜑

be the truth assign-

ment induced by

, i.e.,

𝜑

sets

to true if

vi∈V1

and

to false if

vi∈V1

. We claim that

𝜑

is a solution to the given

not-all-equal 3-sat

instance. Firstly, for the sake of contra-

diction, assume that there exists a clause

yj∈C

containing only literals that are satisfied

by

𝜑

. However, by Observation 3, this implies that all vertices of color

are part of

contradicting Lemma 8 as there exist

3Z+3j

such vertices. Secondly, for the sake of con-

tradiction, assume that

contains no literal satisfied by

𝜑

. However, by Observation 3, this

implies that all vertices of color

are part of

, contradicting again Lemma 8. Conse-

quently,

𝜑

is a solution.

◻

Observing that

{

⋆

is a feedback vertex set of the constructed graph and that the con-

struction can be computed in polynomial time, Theorem4 follows directly from Lemma 7

and Lemma 9

From our reduction, we can further conclude that FCd is also para-NP-hard with respect

to the treewidth plus the number k of districts.

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

1 3

Page 25 of 37 13

Corollary 7 FCD is NP-hard for

tw =2

and

k=2

, even if

smin =1

and

smax =∞

6 FCD ongraphs ofbounded vertex cover number

Motivated by our hardness results for graphs with constant treewidth, we now turn to the

size

vcn

of a minimum vertex cover, a parameter never smaller than the treewidth. In this

section, we present two parameterized algorithms, namely, an XP-algorithm for

vcn

and an

FPT-algorithm for

vcn +|C|

. Unfortunately, we were unable to settle whether FCd param-

eterized by

vcn

is W[1]-hard or fixed-parameter tractable. In contrast, we develop an FPT-

algorithm for the number of vertices with degree at least two (a parameter which is never

smaller than

vcn

Both algorithms for

vcn

rely on the followinglemma.

Lemma 10 Let S be a vertex cover of minimum size and

V=(V1,…,Vk)

a solution to an

FCD instance on a graphG. There are at most

vcn

districts in

that contain at least one

vertex from S. Moreover, for every

Vi∈V

with

S∩Vi

≠

�

, there is a set

Ji⊆Vi⧵S

of at

most

|S∩Vi|−1

vertices such that

G[(S∩Vi)∪Ji]

is connected.

Proof As each vertex is only contained in one district, the first part of the lemma follows

from the definition of

vcn

. To prove the second part, fix some

Vi∈V

. Consider a mini-

mum spanning tree

T=(Vi,F)

G[Vi]

. Let

Ji⊆Vi⧵S

be the set of vertices of degree

at least two in T. Let

T�∶= ((S∩Vi)∪Ji,F�)

be the result of deleting from T each ver-

tex

v∈Vi⧵(S∪Ji)

along with an edge incident to it. Observe that

T′

is connected and

thus

G[(S∩Vi)∪Ji]

is connected, which contains

T′

as a subgraph. We show that

|Ji|≤|S∩Vi|−1

. As by the definition of

vertices from

are only adjacent to verti-

ces from

S∩Vi

and as every vertex from

has degree at least two in T and

T′

, we have

′|

≥2

. We also have

�|=|

∩

i|+|

i|−1

since

T′

is a tree. Thus, we have

|Ji|

≤

|S∩Vi|−1

◻

We first show that FCd parameterized by

vcn

is in XP using the following approach: We

first guess how the vertex cover is partitioned into districts in the sought solution, which

gives partial (not necessarily connected) districts. For every partial district, we then guess

some vertices outside the vertex cover to include such that the partial district becomes con-

nected, the two most frequent colors, and how often they occur in the resulting district.

The remaining problem can be reduced to the polynomial-time solvable (g , f

)-FaCtor

problem[25].

Theorem5 FCD is solvable in

nO(vcn )

time.

Proof Suppose there is a solution

V=(V1,…,Vk)

to the given FCd instance. Let S be a

vertex cover of minimum size and let

I=V⧵S

be the vertices outside the vertex cover.

As in the proof of Theorem6, our algorithm first tries all possibilities to fix some struc-

ture with respect to S. Then, we will construct an instance of the polynomial-time solv-

able (g , f

)-FaCtor

problem, which generalizes

MaXiMuM MatChing

, for each choice of the

following:

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

1 3

13 Page 26 of 37

• An integer

k�≤min(k, vcn )

. If

𝓁=0

smin ≥2

, then we consider only one choice for

k′

, namely

k�=k

• A partition of S into

k′

non-empty subsets

S1,…,Sk�

. There are at most

vcn vcn

such par-

titions.

• For every

i∈[k�]

, a set

Ji⊆I

of at most

|Si|−1

vertices such that

G[Si∪Ji]

is con-

nected and

Ji∩Ji

�

=�

for

i≠i�∈[k�]

. We can assume that

|Ji|

≤

|Si|−1

vertices are

sufficient to make

G[Si]

connected by Lemma 10. The number of choices for

is at

most

∏i∈[k

�

]

�S

�−1

≤n

vcn

• For every

i∈[k�]

, a pair

(

�

of colors, which have the largest numbers of occur-

rences in the sought

among all colors. There are at most

|C|2 vcn

choices for all pairs

of colors.

• For every

i∈[k�]

, the numbers

i,z

′

of occurrences of color

and

c′

, respectively,

with

−𝓁≤z

c�

≤z

. Since

zci≤n

and

c′

≤n

, there are at most

n2 vcn

choices.

Since

|C|≤n

, there are at most

nO(vcn )

choices. Let

I�=

I⧵

⋃i∈[k

�

]

. Now the question is

whether we can partition the vertices V into k districts

(V1,…,Vk)

such that, for

i∈[k�

,k]

consists of a single vertex from

I′

, and for

i∈[k�]

Si∪Ji⊆Vi

G[Vi]

is connected,

|Vi|∈[smin,smax]

𝜒ci(Vi)=zci

𝜒

c�

)=z

�

and

𝜒

)

≤

𝜒

c�

)

for all

c∈C⧵{ci}

. We

reject the current combination, if for some

i∈[k�]

𝜒ci(Si∪Ji)>zci

𝜒

c�

∪J

)>z

�

𝜒

∪J

)>z

�

for some

c∈C⧵{ci}

, or

|Si∪Ji|>smax

. Otherwise, to decide whether it is

possible to distribute the vertices

I′

to construct a partition respecting the above-described

properties, we reduce to (g , f

)-FaCtor

, where given a graph

H=(U,F)

and two functions

g,f∶V

↦

ℕ

, the question is whether there is a subgraph

H�=(U,F�)

with

F′⊆F

such

that every vertex has at least g(v) and at most f(v) neighbors in

H′

We construct a bipartite graph H and f,g as follows. The left bipartition of H consists of

all vertices

v∈I�

. For every

i∈[k�]

, we add the following vertices to the right bipartition:

• For each color

c∈{ci,c�

, we add

zc−𝜒c(Si∪Ji)

vertices (call them

) and connect

them via edges to all vertices

v∈I�

having color c in G which have at least one neigh-

bor in

in G.

• For each color

c∈

C⧵

{

�

, we add

c�

−𝜒

∪J

)

vertices (call them

) and con-

nect them via edges to all vertices

v∈I�

having color c in G which have at least one

neighbor in

in G. Let

∶= ⋃

c∈C⧵{c

,c�

smin =1

, then we add a set

A′

k−k�

vertices to the right bipartition and con-

nect them via edges to all vertices of

I′

. For every vertex v introduce thus far, let

f(v)=g(v)=1

. Finally, for every

i∈[k�]

, add a vertex

to the left side and let

f(vi)=|Bi|−max(0, smin −|Ai∪Si∪Ji|)

and

g(vi)=|Bi|−smax +|Ai∪Si∪Ji|

(if it does

not hold that

0≤g(vi)≤f(vi)

, then we continue with the next combination). We connect

to all vertices from

If the constructed (g,f)

-FaCtor

instance is a yes-instance, we return yes; otherwise, we

continue with the next combination. To see why the algorithm works correctly, suppose

that there is a subgraph

H�=(U,F�)

of H such that the degree of every vertex v in

H′

in the range [g(v),f(v)]. From

H′

, we can construct a solution of the given FCd instance

by putting each vertex

v∈I�

into the district corresponding to the neighbor of v in

H′

(if

smin =1

, then every vertex adjacent to some vertex from

A′

forms a district of its own).

Moreover, for all

i∈[k�]

, we add

Si∪Ji

. As all vertices from

I′

have one neighbor in

H′

, each vertex from

I′

is assigned to a district. As all vertices from A have one neighbor in

H′

, for

i∈[k�]

, it holds that

𝜒ci

=zci

and

𝜒

c�

�

and thus that the resulting districts are

𝓁

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

1 3

Page 27 of 37 13

-fair. Moreover, the number of neighbors of

H′

is between

|Bi|−smax +|Ai∪Si∪Ji|

and

|Bi|−max(0, smin −|Ai∪Si∪Ji|)

, implying that there are at least

smin −|Ai∪Si∪Ji|

and at most

smax −|Ai∪Si∪Ji|

vertices in

that adjacent to some vertex from

I′

. Thus,

the size of each district is in

[smin,smax]

◻

Recall that FCd is NP-hard and W[1]-hard with respect to

|C|+k

on trees with diam-

eter four (Corollary 5). In contrast to this, since a tree of diameter at most three has a vertex

cover of size at most two, by Theorem5, the following holds.

Corollary 8 FCD is polynomial-time solvable on trees with diameter at most three.

Recall that we have shown in Corollary 5 that FCd is NP-hard on trees with diameter

four.

Using a similar approach as for Theorem5, we show that FCd is fixed-parameter trac-

table with respect to

vcn +|C|

. The overall idea is the following: We guess the partition of

the vertex cover into the districts. We categorize vertices outside the vertex cover accord-

ing to their neighborhood and color. We formulate the resulting problem as an ILP whose

number of variables only depends on

vcn +|C|

. Subsequently we employ Lenstra’s FPT-

algorithm for ILPs [30, 36] to obtain the following:

Theorem6 FCD parameterized by

vcn +|C|

is fixed-parameter tractable.

Proof Suppose there is a solution

V=(V1,…,Vk)

. Let S be a vertex cover of minimum

size. Then the vertices

I=V⧵S

that are not part of the vertex cover form an independent

set. Let

k′

be the number of districts in

that contain at least one vertex of S. By Lemma

10, we have

k′≤vcn

. Assume without loss of generality that exactly for every

i∈[k�]

≠

∅

where

Si=S∩Vi

. Then, for every

i∈{k�+1, …,k}

, we have

Vi={v}

where v is

some vertex from I.

We say that a vertex

v∈I

has type (c,X) for

c∈C

and

X⊆S

if the color of v in G is

c and its neighborhood is X. Let

denote the set of all types (note that

|T|=2vcn

⋅|C|

For type

T∈T

, let

be the number of vertices of type T, and for typeT with

nT>0

let

vT∈I

be an arbitrary vertex of type T. Our algorithm will construct an ILP instance for

each choice of the following:

• An integer

k′≤vcn

. If

𝓁=0

smin >1

, then we consider only one choice for

k′

namely

k�=k

• A partition of S into non-empty subsets

S1,…,Sk�

. There are at most

vcn vcn

such parti-

tions.

• For every

i∈[k�]

, a set

of at most

|Si|−1

types such that

G[Si∪Ji]

is connected for

Ji={vT∣T∈Ti}

. If

|{i∣T∈Ti}|>nT

for some

T∈T

, then we reject the current

combination. Note that we can assume that

≤

i|−1

vertices are sufficient to make

G[Si]

connected by Lemma 10. As there are at most

2vcn

⋅|C|

types, the number of

choices for all

is at most

∏i∈[k

�

]

(2vcn

⋅

�

)

�

−1≤2vcn

⋅

�

�vcn

• For every

i∈[k�]

, a pair

(ci,c�

of colors, which have the largest numbers of occur-

rences in

among all colors. In the sought solution it holds that

𝜒

i(V

)≥𝜒

c�

)

There are at most

|C|2 vcn

choices for all pairs of colors.

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

1 3

13 Page 28 of 37

To decide on the distribution of the vertices from I, we now construct an ILP. For the ILP

formulation, we introduce an integer variable

xi,T

for each

i∈[k�]

and

T∈T

. The variable

xi,T

will indicate the number of vertices of type T that we put in

. Clearly, there are at

most

vertices for each type

T∈T

that belong to one of

V1,…Vk�

Then for every

i∈[k�]

and

T∈Ti

, at least one vertex of type T is included in

to satisfy

our previous guesses:

Further for every

i∈[k�]

, only vertices from I that are adjacent to a vertex from

can be

part of

. Thus, for all types

T=(c,X)∈T

with

X∩Si=�

it holds that:

Moreover, there are exactly

k−k�

vertices which are contained in none of

V1,…,Vk�

they form their own districts:

For

i∈[k�]

and

c∈C

, let

ni,c

be the number of vertices of color c in

For every

i∈[k�]

, the following two constraints will ensure that the district

𝓁

-fair.

Finally, for every

i∈[k�]

, the following imposes the size constraints:

For the running time, observe that we construct at most

O(vcn

)⋅

|C|vcn

ILP instances.

Since each ILP instance uses at most

vcn ⋅2vcn

⋅|C|

variables, it can be solved in

f(vcn +|C|)

⋅

nO(1)

time for some computable function f due to a result of Lenstra [30,

36].

◻

It remains open whether FCd is fixed-parameter tractable or W[1]-hard with respect

vcn

. However, we can prove fixed-parameter tractability with respect to the number of

vertices with degree at least two. Neglecting connected components consisting of two ver-

tices, the set of vertices with degree at least two is always also a vertex cover; therefore,

this parameter upper-bounds the vertex cover number in connected graphs on at least three

vertices. The idea of the algorithm is to guess the partitioning of the degree-two vertices

into the districts. Then, for each of these districts, there exists a set of degree-one vertices

where each of these vertices either belongs to the district or needs to form its own. Lastly,

we can distribute the degree-one vertices using Proposition 4.

∑

i∈[k

�

]

xi,T≤nT

xi,T

≥

xi,T=0.

∑

∈T

(

nT−

∑

i∈[k�]

xi,T

)

=k−k�

i,c=𝜒c(Si)+

∑

T∈Twith T=(c,X)for some X⊆S

xi,T

i,c�

≤

i,c

≤

i,c�

+𝓁, and n

i,c�

≥

i,c

for all c∈C⧵{c

min ≤

∑

c∈C

ni,c≤smax

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

1 3

Page 29 of 37 13

Proposition 7 Let

be the number of vertices with degree at least two. FCD is solvable in

O(pp⋅k⋅n)

time.

For the sake of simplicity, we assume that the graph does not contain connected com-

ponents of size two (we can deal with them easily separately). Let

X⊆V

be the set of ver-

tices with degree at least two and

Y=V⧵X

be the set of degree-one vertices. We iterate

over all combinations of the following:

• An integer

k′≤k

. If

𝓁=0

smin >1

, then we only consider

k�=k

• A partition of X into

k′

non-empty subsets

X1,…,Xk�

. There are at most

such parti-

tions.

For

i∈[k�]

, let

Yi⊆Y

be the set of vertices from Y that are adjacent to a vertex from

𝓁=0

smin >1

, then

k�=k

and hence we accept if (

X1∪Y1,…,Xk∪Yk

) is a solution

and otherwise continue with the next combination.

Otherwise, we put all vertices from

in district

. Each vertex

v∈Yi

is either part of

or forms its own district. Thereby, for each

i∈[k�]

, we know by applying Proposition 4 an

interval

[𝛼i,𝛽i]

for the number of

𝓁

-fair districts respecting the size constraints in which the

vertices

Xi∪Yi

can be partitioned or we know that no solution exists (in this case, we con-

tinue with the next combination). We now check whether the given k lies between

∑i∈[k

�

]𝛼i

and

∑i∈[k

�

]

𝛽

and return the answer.

As there exist

partitions of X, the running time of the algorithm is

O(pp⋅k⋅n)

7 Conclusion

We initiated a thorough study of the NP-hard

Fair ConneCted distriCting

(FCd) prob-

lem. We considered FCd on specific graph classes and analyzed the parameterized com-

plexity of FCd with a focus on the number of districts, the number of colors, and various

graph parameters. We have shown that while FCd can be solved on simple graph classes in

polynomial time (mostly using approaches based on dynamic programming), on trees it is

already NP-hard and W[1]-hard with respect to the combined parameter number of colors

plus number of districts. Nevertheless, for graph parameters such as the vertex cover num-

ber and the max leaf number, we developed XP-algorithms.

As to challenges for future research, we left open whether FCd is fixed-parameter trac-

table or W[1]-hard with respect to the vertex cover number or max leaf number. The former

question is particularly intriguing because it is related to an open question of Stoica etal.

[48] on the parameterized complexity of

Fair regrouping

with respect to the number of

districts (which has been very recently partly solved by Boehmer and Koana [10]): Recall

that the input of

Fair regrouping

is additionally endowed with a function

f∶V

→

2[k]

with the requirement that every vertex

v∈V

should belong to district

for some

i∈f(v)

(and that the connectivity requirement is dropped). Consider the FCd instance on the

bipartite graph with bipartition (V,[k]), where there is an edge between

i∈[k]

and

v∈V

if and only if

i∈f(v)

. The vertex cover number of this graph is at most the number k of

districts. Under certain constraints, FCd on this graph becomes essentially equivalent

Fair regrouping

. Thus an algorithm for the vertex cover number for FCd would also

shine further light on the complexity of

Fair regrouping

with respect to the number of

districts. The latter question concerning the max leaf number is interesting because FCd

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

1 3

13 Page 30 of 37

could turn out to be one of few problems that are in XP yet W[1]-hard with respect to the

max leaf number. It would be also promising to consider additional graph parameters (such

as cliquewidth, treedepth or sparsity related parameters like the maximum degree or the

degeneracy) or to examine further graph classes (such as grids).

From a broader perspective, there are several natural extensions of FCd. For instance,

as already suggested by Stoica etal. [48], there may be a function that specifies for each

vertex a set of districts to which the vertex can belong.6 While all our hardness results still

hold for this more complicated setting, it is open which of our algorithmic results can be

adapted. Moreover, we did not study the generalization of FCd where each vertex has an

integer weight for each color (such a study has been done in the context of gerrymander-

ing by Cohen-Zemach etal. [15] and Ito etal. [29]). Weighted FCd is motivated by the

following application scenarios: First, in some settings we might be restricted to put a cer-

tain group of agents always in the same district (those can be combined into one vertex).

Second, if each vertex represents a voter and the colors represent alternatives, then voters

might want to give points to different alternatives (such as done in the context of positional

scoring rules).

Lastly, one can modify the definition of FCd. For instance, as done, among others, by

Lewenberg etal.[38] and Eiben etal.[20] in the context of

gerryMandering

and, among

others, by Lu etal.[39] and Fotakis and Tzamos[24] in the context of facility location

problems, instead of placing agents on a social network, the agents may be placed in a met-

ric space. The task is then to place k ballot boxes in the space where each agent is assigned

to the closest ballot box. The goal is again to make the resulting districts as fair as possible.

Appendix

Proof ofproposition 4

proposition 4(

★

). Let

(G=(X∪Y,E),C, col, k,𝓁,smin,smax)

be an FCd instance where

G is a star with center vertex

v∈X

. Then, one can decide in linear time whether there is

a partition of

X∪Y

into kconnected

𝓁

-fair districts respecting

smin

and

smax

such that all

vertices from X are part of the same district.

Proof In the following, we call a partition of the vertices in

X∪Y

into kconnected districts

a solution if each district is

𝓁

-fair, respects the size constraints, and all vertices from X

are part of the same district to which we refer as the center district. Note that each solu-

tion consists of the center district and several districts consisting of a single vertex fromY.

Hence, we may assume that

smin =1

. (For

smin

≥

, we can immediately conclude that

there is no solution unless

k=1

X∪Y

𝓁

-fair, and

|X∪Y|∈[smin,smax]

.) We may also

assume that

|X|

≤

smax

. We now describe a linear-time algorithm that decides whether a

given FCd instance admits a solution.

6 However, it seems that in most applications where connectivity plays a crucial rule districts are “isomor-

phic” to each other, i.e., districts do not carry any particular meaning; for instance, when dividing a city into

voting districts or people placed on a social network into teams for a competition. Thus, a priori, it is irrel-

evant for a vertex in which district it is put.

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

1 3

Page 31 of 37 13

We start with several special cases: For

𝓁=0

, a solution exists if and only if

MOV(X∪Y)=0

k=1

, and

|X∪Y|

≤

smax

. If

|C|=1

, then all solutions containing k dis-

tricts are isomorphic, i.e., they contain

k−1

districts containing a single vertex and a sin-

gle district containing the remaining vertices. Thus, the given instance admits a solution if

and only if

|Y|≥k−1

𝓁

≥

|Y∪X|−(k−1)

, and

|Y∪X|−(k−1)≤smax

Let

c1∈C

be the most frequent color in

X∪Y

and

c2∈C

be the second most frequent

color in

X∪Y

. If

𝜒c1(X)>𝜒

c2(X∪Y)+𝓁

, then the given instance has no solution because

the center district cannot be

𝓁

-fair.

Having dealt with several special cases separately, we now present a precise char-

acterization of yes-instances assuming that

|C|>1

𝓁>0

smin =1

|X|

≤

smax

, and

𝜒c1(X)≤𝜒c2(X∪Y)+𝓁

. Let

c⋆

be the most frequent color in X. Further, let

c⋆

≠c

⋆

be the most frequent color in X among colors

c′

such that

𝜒

c�

(X∪Y)

≥

𝜒

c⋆

(X)−𝓁

Note that

c⋆

is always well-defined. If

c⋆

≠c

, then by the definition of

it holds that

𝜒

1(X∪Y)

≥

𝜒

c⋆

(X∪Y)>𝜒

c⋆

(X)−𝓁

. On the contrary, if

c⋆

, then, by our assump-

tion that

𝜒c1(X)≤𝜒c2(X∪Y)+𝓁

, we have

𝜒

2(X∪Y)≥𝜒

c⋆

(X)−𝓁

Let

bl∶= max(0, 𝜒c1(X∪Y)−𝜒c2(X∪Y)−𝓁)

and

∶= max(0, 𝜒

c⋆

(X)−𝓁−𝜒

c⋆

(X))

Then, there is a solution if and only if

k∈[bl+1, |Y|+1−bu]

and

k>|X|+|Y|−smax

We first prove the forward direction, i.e., that the existence of a solution implies that

k∈[bl+1, |Y|+1−bu]

and

k>|X|+|Y|−smax

. For any solution, the center district

contains at most

𝜒c2(X∪Y)+𝓁

vertices of color

(otherwise it cannot be

𝓁

-fair). Thus,

at least

𝜒c1(X∪Y)−𝜒c2(X∪Y)−𝓁

vertices of color

have to be part of a non-center

district, which implies that

k>bl

. Next, we show that

≤

|Y|+1−bu

. The center district

has at least

𝜒

c⋆

(X)

vertices of color

c⋆

. Since the center district is

𝓁

-fair, it has at least

𝜒

c⋆

(X)−𝓁

vertices of color c for some color

∈C⧵{c

⋆

. As only

𝜒c(X)

of the

𝜒

c⋆

(X)−𝓁

vertices come from X, it follows that there are at least

𝜒

c⋆

(X)−𝓁−𝜒

(X)

vertices of

color c from Y that are included in the center district. As

c⋆

is the most frequent color in

X among all colors occurring at least

c⋆

(X)−𝓁

times, it follows that

𝜒

c⋆

(X)−𝓁−𝜒

c⋆

(X)

minimizes the expression from the previous sentence. Using this, we can conclude that

k≤|Y|+1−bu

. Finally, we show that

k>|X|+|Y|−smax

. Since the center district con-

tains at most

smax

vertices, at least

|X|+|Y|−smax

vertices are not part of the center dis-

trict, which implies that

k>|X|+|Y|−smax

We now prove the backward direction, i.e., that

k∈[bl+1, |Y|+1−bu]

and

k>|X|+|Y|−smax

imply the existence of a solution. First, we show that if

k∈[bl,|Y|+1−bu]

, ignoring the size constraints, a solution always exists. We do this

by first constructing two “extreme” solutions where as many or as few vertices as possible

are contained in the center district. Recall that by our assumption

𝜒c1(X)

≤

𝜒c2(X∪Y)+𝓁

So we have

𝜒c1(Y)=𝜒c1(X∪Y)−𝜒c1(X)≥𝜒c1(X∪Y)−𝜒c2(X∪Y)−𝓁

, and hence

𝜒c1(Y)

≥

. A solution consisting of

bl+1

districts exists: Put all vertices from

X∪Y

in one district and move

vertices of color

fromY each in their own district (this is

always possible by our above observation). Let S be the center district in this solution. S

𝓁

-fair, as

𝜒c1(S)≥𝜒c2(S)

𝜒c1(S)=𝜒c1(X∪Y)−bl≤𝜒c2(X∪Y)−𝓁=𝜒c2(S)−𝓁

, and

𝜒c2(S)

≥

𝜒c(S)

for all

c∈C⧵{c1}

. A solution consisting of

|Y|+1−bu

districts is also

guaranteed to exist: Put the vertices of X and

vertices of color

c⋆

from Y into the center

district; put all remaining vertices from Y into their own district. Let

S′

be the center district

in this solution.

S′

𝓁

-fair, as

𝜒

c⋆

(S)−𝓁=𝜒

c⋆

(X)−𝓁≤𝜒

c⋆

(X)+b

=𝜒

c⋆

(S)≤𝜒

c⋆

(S)

Note that from these two solutions, we can construct a solution consisting of k districts for

arbitrary

k∈[bl+1, |Y|+1−bu]

. For this, we start with the first solution and one by one

move vertices from

Y∩(S⧵S�)

from the center district into their own district while main-

taining that the center district is

𝓁

-fair. Such a vertex always exists: If there is a vertex v of

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

1 3

13 Page 32 of 37

the most frequent color of the center district in

Y∩(S⧵S�)

, then we move v from S into its

own district (removing v only increases the margin of victory by one if the center district

is currently 0-fair and we have

𝓁>0

). Otherwise, we remove the remaining vertices from

Y∩(S⧵S�)

in an arbitrary order and put each into its own district (doing so results in an

𝓁

-fair center district, since otherwise

S′

would not be

𝓁

-fair). If

k>|X|+|Y|−smax

, then

the above constructed solution for this k satisfies the size constraints as it consists of a

center district containing

|X|+|Y|−(k−1)≤smax

vertices where the inequality holds by

our observation on k.

◻

Proof oftheorem3

Theorem 3 (

★

). FCd can be solved in

O(nO(tw ⋅|C|))

time.

Proof Suppose that we are given an instance

I=(G,C, col, k,𝓁,smin,smax)

of FCd admit-

ting a solution

V={V1,…,Vk}

. Let

(T=(VT,ET),{Bx}x∈VT)

be a tree decomposition of

For

x∈VT

, let

be the graph whose vertices and edges are those introduced in a node

from the subtree ofT rooted atx. Further, let

be the set of vertices in

. Our algorithm

employs a dynamic programming method that traversesT from bottom totop.

Observe that each district

Vi∈V

from the solution is of one of the following three types

with respect to each

x∈VT

(i)

Vi∩

≠

�

, i.e., the district

overlaps with the vertices in the bag of x.

(ii)

Vi∩Bx=�

and

Vi⊆Ux

, i.e., the district

is disjoint from

but fully contained in

vertices from bags from the subtree rooted at x.

(iii)

Vi∩Bx=�

and

Vi⊆V⧵Ux

, i.e., the district

is disjoint from

and does not contain

any vertex occurring in a bag from the subtree rooted at x.

These three cases are exhaustive, as by definition of the tree decomposition, for each

vertex, all nodes in which bags the vertex appears form a connected subgraph in T. Note

that for each district

Vi∈V

of type (i), the induced subgraph

Gx[Vi]

can have multiple

connected components, in which case

G[Vi]

includes some vertices or edges not in

For each

x∈VT

, we keep track of the following information:

(1) the intersection of

and every

Vi∈V

of type (i),

(2) the intersection of

with the connected components of the subgraph

Gx[Vi]

for all

districts

Vi∈V

of type (i),

(3) the number of occurrences of color c for every color

c∈C

Vi∩Ux

for every district

Vi∈V

of type (i), and

(4) the number of districts of type (ii).

We capture this information in the following variables: For each

x∈VT

, let (1)

a partition of

, (2)

be a partition of

where each subset from

is contained in

a subset of

, (3)

𝜁∶

B→ℕ

|C|

be some function, and (4)

𝜅∈ℕ

be some integer with

𝜅≤k

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

1 3

Page 33 of 37 13

On an intuitive level, moving in the tree from the bottom to the top, we keep track of

the number of “completed” districts (type (ii) districts). Moreover, for each “unfinished”

district (type (i) district), we store its current color distribution (and thereby implicitly its

current size of so far added vertices), and how the vertices from the current bag are distrib-

uted to the unfinished districts. Also, for each unfinished district, we keep track of which of

its vertices from the current bag are already connected over vertices that have been added

to the district and edges that have been introduced in the respective subtree. It is necessary

to keep track of the connectivity of vertices from one district (stored in

), as we need this

information to ensure that we make the district connected by adding further vertices and

edges to it further up in the tree. Moreover, we cannot directly infer it from

, as we cannot

remember all vertices put in the districts so far.

It remains to formally describe the dynamic program we use. For all combina-

tions of the variables

𝜁

, and

𝜅

, we compute

Ax(B,D,𝜁,𝜅)∈{0, 1}

such that

Ax(B,D,𝜁,𝜅)=1

if and only if there is a partition of the vertices

into exactly

|D|+𝜅

subsets

(W1,…,W|D|+𝜅)

with the following properties:

• For every

i∈[|D|+𝜅]

Gx[Wi]

is connected.

• Exactly

𝜅

subsets from

(W1,…,W|D|+𝜅)

are disjoint from

. Moreover, all of them

are

𝓁

-fair and respect the size constraints.

• For every subset

intersecting

, it holds that

Wi∩Bx∈D

• For every

B∈B

, it holds that

𝜁(

)=∑i∈[�

�+𝜅],Wi∩B

≠

�

𝜒

(

)

From the subsets in the partitioning

(W1,…,W|D|+𝜅)

𝜅

are

𝓁

-fair connected districts of

type (ii) with respect to x. The other

|D|

subsets are partly contained in

and restricted

form the partition

describing the intersection of

with the connected compo-

nents of

Gx[Vi]

for districts

of type(i). Note that some of these

|D|

subsets may end up

in the same district in the solution. Moreover, assuming that

corresponds to the inter-

sections of

and districts of type (i), it needs to hold that for each set in the intersec-

tion

B∈B

𝜁(B)

is the distribution of colors in the union of all subsets

intersecting

with B (these are the subsets that will finally end up being one district in the solution).

Observe that a given instance of FCd is a yes-instance if and only if there exists a parti-

tion

for the root r of T and a function

𝜁r

such that for all

B∈Br

𝜁r(B)

𝓁

-fair and

its

-norm is in the range

[smin,smax]

and

Ar(Br,Br,𝜁r,k−|Br|)=1

We compute

Ax(B,D,𝜁,𝜅)

by traversing the nodes

of the tree T from bottom to top.

Depending on the type of the current node

x∈VT

, we apply one of the following five

cases. In the following, let

y∈VT

(and

z∈VT

) be the child node(s) of x if x has one (two)

child node(s) inT.

Leaf node x.

For a leaf node x with

Bx={v}

, we have

Ax({v},{v},𝜁,0)=1

if and only if

𝜁({v}) = 𝜒({v})

Introduce vertex v node x.

Note that v is isolated in

. Thus,

Ax(B,D,𝜁,𝜅)=0

{v}

is not contained in

. Oth-

erwise we have

where

B�=(

⧵{B})∪{B⧵{v}}

for

B∈B

with

v∈B

(

B�=

⧵{B}

B={v}

D�=

⧵{{v}}

, and

𝜁�(B�)=𝜁(B)−𝜒({v})

B�=B⧵{v}

(we assume that

𝜁�(�)

is a zero

vector here) and

𝜁�(B�)=𝜁(B�)

otherwise.

(B,D,𝜁,𝜅)=A

�

,𝜁

�

,𝜅)

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

1 3

13 Page 34 of 37

Introduce edge

{u,v}

node x.

If u and v belong to distinct subsets of

, then we have

Ax(B,D,𝜁,𝜅)=Ay(B,D,𝜁,𝜅)

We also have the same recurrence if u and v belong to the same subset of

. This is

because in both cases the connected components of districts of type (i) in

do not change.

Otherwise, we have

where

⋁

is over all partitions

D′

from which

can be obtained by removing

v∈D�

with

u∈Du

and

v∈Dv

from

D′

and adding

Du∪Dv

D′

Forget v node x.

We have two cases. In the first case, the district

Vi∈V

to which v belongs does not

intersect

. This implies that

is now fully contained in

and becomes a district of type

(ii). Then

{v}

should have been part of

and

for child y. Let us define

where

⋁

is over all functions

𝜁′

such that

𝜁�(B)=𝜁(B)

for all

B∈B

MOV(𝜁�({v})) ≤𝓁

and

smin

≤

∑c∈C

𝜁

�

({v}) ≤s

max

. Note that we also need to decrease

𝜅

, as

is an additional

district of type (ii) for the node x. In the other case, the district in which v is contained

intersects

. In this case, it holds that

where

⋁

is over all partitions

B′

and

D′

such that

B�=(

⧵{B}) ∪ (B∪{v})

and

D�=(

D⧵

{

}) ∪ (

∪{

})

for some

B∈B

and

D∈D

. All in all, we have

(B,D,𝜁,𝜅)=A

(B,D,𝜁,𝜅)∨A

(B,D,𝜁,𝜅

)

Join node x.

Note that two vertices

u,w∈D

for some

D∈D

can reach each other in

via connec-

tions in

and

. So we have

Here,

⋁

is over all

Dy,Dz,𝜁y,𝜁z,𝜅y,𝜅z

such that all the following hold:

•

are the connected components of the graph whose vertex set is

and edge set is

{{u,w} ∣ (∃Dy∈Dy∶u,w∈Dy) ∨ (∃Dz∈Dz∶u,w∈Dz)}

•

𝜁y(B)+𝜁z(B)=𝜁(B)−𝜒(B)

for every

B∈B

•

𝜅y+𝜅z=𝜅

Now we examine the running time. Note that there are

tw O(tw )

partitions of

for every

node x of T. Since

𝜁(B)∈{0, …,n}|C|

for every

B∈Bx

and

x∈VT

, there are at most

nO(tw ⋅|C|)

states for

𝜁

. It is easy to see that the computation of all values takes

nO(tw ⋅|C|)

time.

◻

Ax(B,D,𝜁,𝜅)=Ay(B,D,𝜁,𝜅)∨

⋁

�

Ay(B,D

�

,𝜁,𝜅)

x(B,D,𝜁,𝜅)=

⋁

𝜁

�

(Ay(B∪ {{v}},D∪ {{v}},𝜁

�

,𝜅−1))

x(B,D,𝜁,𝜅)=

⋁

B�

D�

Ay(B

�

,𝜁,𝜅)

(B,D,𝜁,𝜅)

⋁

,𝜁

,𝜅

Ay(B,Dy,𝜁y,𝜅y)∧Az(B,Dz,𝜁z,𝜅z)

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

1 3

Page 35 of 37 13

Acknowledgements NB was supported by the DFG projects MaMu (NI 369/19) and ComSoc-MPMS (NI

369/22). TK was supported by the DFG projects FPTinP (NI 369/18) and DiPa (NI 369/21). This work was

started at the research retreat of the TU Berlin Algorithmics and Computational Complexity research group

held in Zinnowitz (Usedom) in September 2020.

Funding Open Access funding enabled and organized by Projekt DEAL.

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License,

which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long

as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Com-

mons licence, and indicate if changes were made. The images or other third party material in this article

are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the

material. If material is not included in the article’s Creative Commons licence and your intended use is not

permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly

from the copyright holder. To view a copy of this licence, visit http:// creat iveco mmons. org/ licen ses/ by/4. 0/.

References

1. Agarwal, A., Elkind, E., Gan, J., Igarashi, A., Suksompong, W., & Voudouris, A. A. (2021). Schelling

games on graphs. Artificial Intelleligence 301, 103576.

2. Autry, E. A., Carter, D., Herschlag, G. J., Hunter, Z., & Mattingly, J. C. (2021). Metropolized multi-

scale forest recombination for redistricting. Multiscale Modelling Simulation, 19(4), 1885–1914.

3. Bachrach, Y., Lev, O., Lewenberg, Y., & Zick, Y. (2016). Misrepresentation in district voting. In Pro-

ceedings of the 25th international joint conference on artificial intelligence (IJCAI ’16). AAAI Press,

(pp. 81–87).

4. Banerjee, A.V., & Duflo, E. (2011). Poor economics: A radical rethinking of the way to fight global

poverty. Public Affairs.

5. Banerjee, A.V., & Pande, R. (2007). Parochial politics: Ethnic preferences and politician corruption.

6. Bentert, M., Koana, T., & Niedermeier, R. (2021). The complexity of gerrymandering over graphs:

Paths and trees. In: Proceedings of the 47th international workshop on graph-theoretic concepts in

computer science (WG ’21). Springer, (pp. 195–206).

7. van Bevernvan Bevern, R., Bredereck, R., Chen, J., Froese, V., Niedermeier, R., & Woeginger, G. J.

(2015). Network-based vertex dissolution. SIAM Journal Discrete Mathematics 29(2), 888–914.

8. Bhakta, P., Miracle, S., & Randall, D. (2014). Clustering and mixing times for segregation models

𝕫2

. In Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms (SODA ’14).

SIAM, (pp. 327–340).

9. Boehmer, N., Bredereck, R., Knop, D., & Luo, J. (2020). Fine-grained view on bribery for group iden-

tification. In Proceedings of the twenty-ninth international joint conference on artificial intelligence

(IJCAI ’20). (pp. 67–73). ijcai.org

10. Boehmer, N., & Koana, T. (2022). The complexity of finding fair many-to-one matchings. In Proceed-

ings of the 49th international colloquium on automata, languages, and programming (ICALP ’22).

(pp. 27:1–27:18).

11. Brandt, C., Immorlica, N., Kamath, G., & Kleinberg, R. (2012). An analysis of one-dimensional

Schelling segregation. In Proceedings of the 44th symposium on theory of computing conference

(STOC ’12). ACM, (pp. 789–804).

12. Brill, M., Schmidt-Kraepelin, U., & Suksompong, W. (2022). Margin of victory for tournament solu-

tions. Artificial Intelligence, 302, 103600.

13. Campagna, J., & Grofman, B. (1990). Party control and partisan bias in 1980s congressional redistrict-

ing. The Journal of Politics, 52(4), 1242–1257.

14. Chlebíková, J. (1996). Approximating the maximally balanced connected partition problem in graphs.

Information Processing Lettering, 60(5), 223–230.

15. Cohen-Zemach, A., Lewenberg, Y., & Rosenschein, J. S. (2018). Gerrymandering over graphs. In Pro-

ceedings of the 17th international conference on autonomous agents and multiagent systems (AAMAS

’18). IFAAMAS, (pp. 274–282).

16. DeFord, D., Duchin, M., & Solomon, J. (2021). Recombination: a family of Markov chains for redis-

tricting. Harvard Data Science Review.

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

1 3

13 Page 36 of 37

17. Dey, P., & Narahari, Y. (2015). Estimating the margin of victory of an election using sampling. In

Proceedings of the twenty-fourth international joint conference on artificial intelligence (IJCAI ’15).

AAAI Press, (pp. 1120–1126).

18. Dyer, M. E., & Frieze, A. M. (1985). On the complexity of partitioning graphs into connected sub-

graphs. Discrete Applied Mathematics, 10(2), 139–153.

19. EdBuild: Non-white school districts get $23 billion less than white districts, despite serving the same

number of students (2019), edbuild.org/content/23-billion

20. Eiben, E., Fomin, F. V., Panolan, F., & Simonov, K. (2020). Manipulating districts to win elections:

Fine-grained complexity. In Proceedings of the 34th AAAI conference on artificial intelligence (AAAI

’20). AAAI Press, (pp. 1902–1909).

21. Engstrom, E. J. (2006). Stacking the states, stacking the house: the partisan consequences of congres-

sional redistricting in the 19th century. American Political Science Review, 100(3), 419–427.

22. Eppstein, D. (2015). Metric dimension parameterized by max leaf number. Journal of Graph Algo-

rithms Application, 19(1), 313–323.

23. Erikson, R. S. (1972). Malapportionment, gerrymandering, and party fortunes in congressional elec-

tions. American Political Science Review, 66(4), 1234–1245.

24. Fotakis, D., & Tzamos, C. (2014). On the power of deterministic mechanisms for facility location

games. ACM Transaction on Economic and Computation, 2(4), 15:1-15:37.

25. Gabow, H. N. (1983). An efficient reduction technique for degree-constrained subgraph and bidirected

network flow problems. In Proceedings of the 15th annual ACM symposium on theory of computing

(STOC ’83). ACM, (pp. 448–456).

26. Gupta, S., Jain, P., Panolan, F., Roy, S., & Saurabh, S. (2021). Gerrymandering on graphs: computa-

tional complexity and parameterized algorithms. In: Proceedings of the 14th international symposium

on algorithmic game theory (SAGT ’21). Springer, (pp. 140–155).

27. Hirsch, S. (2003). The united states house of unrepresentatives: What went wrong in the latest round of

congressional redistricting. Election Law Journal, 2(2), 179–216.

28. Issacharoff, S. (2002). Gerrymandering and political cartels. Harvard Law Review, 116, 593–648.

29. Ito, T., Kamiyama, N., Kobayashi, Y., & Okamoto, Y. (2021). Algorithms for gerrymandering over

graphs. Theoritical Computer Science, 868, 30–45.

30. Kannan, R. (1987). Minkowski’s convex body theorem and integer programming. Mathematics of

Operation Research, 12(3), 415–440.

31. Kleitman, D. J., & West, D. B. (1991). Spanning trees with many leaves. SIAM Journal on Discrete

Mathematics, 4(1), 99–106.

32. Kloks, T. (1994). Treewidth, computations and approximations lecture notes in computer science (Vol.

842). New York: Springer.

33. Kreisel, L., Boehmer, N., Froese, V., & Niedermeier, R. (2021). Equilibria in schelling games: com-

putational complexity and robustness. In Proceedings of the 21st international conference on autono-

mous agents and multiagent systems (AAMAS ’22). IFAAMAS, (pp. 761–769).

34. Landau, Z., Reid, O., & Yershov, I. (2009). A fair division solution to the problem of redistricting.

Social Choice and Welfare, 32(3), 479–492.

35. Landau, Z., & Su, F. E. (2013). Fair division and redistricting AMS Special Sessions on The Mathe-

matics of Decisions Elections and Games. Rodhe Island: American mathematical society, (pp. 17–36).

36. Lenstra, H. W. (1983). Integer programming with a fixed number of variables. Mathematics of Opera-

tion Research, 8, 538–548.

37. Levin, H. A., & Friedler, S. A. (2019). Automated congressional redistricting. ACM Journal of Experi-

mental Algorithmics, 24(1), 1.10:1-1.10:24.

38. Lewenberg, Y., Lev, O., & Rosenschein, J. S. (2017). Divide and conquer: Using geographic manipula-

tion to win district-based elections. In Proceedings of the 16th conference on autonomous agents and

multiagent systems (AAMAS ’17). ACM, (pp. 624–632).

39. Lu, P., Sun, X., Wang, Y., & Zhu, Z. A. (2010). Asymptotically optimal strategy-proof mechanisms

for two-facility games. In Proceedings of the 11th ACM conference on electronic commerce (EC ’10).

ACM, (pp. 315–324).

40. Lublin, D. (1999). The Paradox of Representation: Racial Gerrymandering and Minority Interests in

Congress. New Jersey: Princeton University Press.

41. Marx, D. (2007). On the optimality of planar and geometric approximation schemes. In Proceedings of

the 48th annual IEEE symposium on foundations of computer science (FOCS 07). (pp. 338–348).

42. McCartan, C., Imai, K. (2020). Sequential monte carlo for sampling balanced and compact redistrict-

ing plans. CoRR http://arxiv.org/2008.06131

43. Mitra, A. (2020). Electoral david versus goliath: how does the spatial concentration of electors affect

district-based elections? http://arxiv.org/2006.11865

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

1 3

Page 37 of 37 13

44. Puppe, C., & Tasnádi, A. (2008). A computational approach to unbiased districting. Mathematical and

Computer Modelling, 48(9–10), 1455–1460.

45. Puppe, C., & Tasndi, A. (2009). Optimal redistricting under geographical constraints: Why "pack and

crack’’ does not work. Economics Letters, 105(1), 93–96.

46. Schaefer, T. J. (1978). The complexity of satisfiability problems. In Proceedings of the 10th annual

ACM symposium on theory of computing (STOC ’78). ACM, (pp. 216–226).

47. Schelling, T. C. (1969). Models of segregation. American Economic Review, 59(2), 488–493.

48. Stoica, A., Chakraborty, A., Dey, P., & Gummadi, K. P. (2020). Minimizing margin of victory for fair

political and educational districting. In Proceedings of the 19th international conference on autono-

mous agents and multiagent systems (AAMAS ’20). IFAAMAS, (pp. 1305–1313).

49. Xia, L. (2012). Computing the margin of victory for various voting rules. In Proceedings of the 13th

ACM conference on electronic commerce (EC ’12). ACM, (pp. 982–999).

50. Zhao, Z., Hettle, C., Gupta, S., Mattingly, J., Randall, D., & Herschlag, G. (2022). Mathematically

quantifying gerrymandering and the non-responsiveness of the 2021 Georgia congressional districting

plan. In Proceedings of the second ACM conference on equity and access in algorithms, mechanisms,

and optimization (EAAMO ’’22). ACM, (pp. 11–15).

Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and

institutional affiliations.