{'fraction_non_alphanumeric': 0.05372109826589595, 'fraction_numerical': 0.0077312138728323695, 'mean_word_length': 3.680739529902486, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 21, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 40, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Refined Complexity Analysis of Fair Districting over Graphs

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 (subsequently referred to as districts) so that in every district the most frequent color occurs at most a given number of times more often than the second most frequent color. Fair Connected Districting is motivated by various real-world scenarios where agents of different types, which are one-to-one represented by nodes in a network, have to be partitioned into disjoint districts. Herein, one strives for"fair districts"without any type being in a dominating majority in any of the districts. This is to e.g. prevent segregation or political domination of some political party. 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).


Introduction
Stoica et al. [43] recently introduced graph-based problems on fair (re)districting, employing "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 representative. 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 network 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. [43], 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 districts 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 district. When partitioning children into school districts, types may model sociodemographic attributes such as race and gender, and a low margin of victory could be beneficial to prevent the existence of schools where one trait is in a clear majority and which may thus be only associated with this single trait (see Stoica et al. [43] 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 [3, 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 [4] even found evidence that in the 1980s and 1990s in North India elected official that belong to the (clearly) dominating caste group were significantly more likely to be corrupt. This illustrates the practical importance of creating districts with a low margin of victory (in terms of ethnicity).
In our work, we build upon the studies of Stoica et al. [43] 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, ℓ, s min , and s max . The question is whether the vertex set of G can be partitioned into k connected districts, each containing between s min and s max vertices, 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 Connected Partition problem [12,15], which asks for a partition of a graph into two connected 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 identify 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). 2 We mention that Stoica et al. [43] use 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 definition 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 victory one in the model of Stoica et al. [43]). Clearly, there are also other fairness measures, e.g., the difference between the occurrences of the most and least frequent color. While these are natural as well, our definition is particularly 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 [8], tournament solutions [10], and voting theory [14,44].

Related Work
Stoica et al. [43] introduced Fair Connected Regrouping, which is a generalization of our Fair Connected Districting 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. [43] considered special cases of 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 the former problem is NP-hard for three colors but in XP with respect to the number of districts, while the later problem is additionally in XP with respect to the number of colors. In addition, they proposed for each of the variants a greedy heuristic and evaluated them using synthetic and real-world data from UK general elections and US public schools.
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 [2,30,31,38,39]. Well-studied in this context is gerrymandering, which can be regarded as a "malicious" counterpart 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 [40], 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 [19,24,36]. More recently, different variants of gerrymandering have been considered from an algorithmic perspective [16,34]. Notably, the study of gerrymandering over graphs, which is analogous to our problem, has recently gained significant interest [5,13,22,25]. In particular, as done here for FCD, Bentert et al. [5], Gupta et al. [22], and Ito et al. [25] 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" [6].
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 [42]: While initially the work in this context was mostly concerned with the theoretical analysis of segregation patterns [9,7], recently Schelling's model has been approached from a game-theoretic perspective [1,29].

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 identify 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.
We show that FCD is NP-hard even if |C| = k = 2 and ℓ = 0 but polynomial-time solvable on paths, cycles, stars, and caterpillars (for stars, our algorithm even runs in linear time). 3 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 (tw), 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 summary of our parameterized results can be found in Figure 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 tractable, 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. 4 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 ℓ.
Organization The remainder of this paper is structured as follows. In Section 2, we formally introduce FCD and the graph parameters we examine. In Section 3, we present some preliminary results on FCD mostly concerning NP-hardness. In Section 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 Section 5, we shift our attention to trees and graphs that are treelike. Lastly, in Section 6, we analyze the influence of the vertex cover number on the complexity of FCD. [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 ′ .

Preliminaries
Fair Connected Districting. Let C = {c 1 , . . . , 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 → C. For a vertex set V ′ ⊆ V , let χ c (V ′ ) denote the number of vertices of color c in V ′ . Moreover, let χ(V ′ ) ∈ N |C| denote the vector in which the ith entry contains the number of vertices The margin of victory MOV(x) of a vector x is defined as the difference between the largest and second largest entry in x, i.e., MOV(x) := If t = 1, then we set MOV(x) := x 1 . Accordingly, we define the margin of victory MOV(V ′ ) of a vertex set V ′ ⊆ V of colored vertices as MOV(V ′ ) := MOV(χ(V ′ )). For ℓ ∈ N, 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 c i ∈ C is the jth most frequent color in a district V ′ if χ i (V ′ ) is the jth largest entry in χ(V ′ ) (we break ties arbitrarily unless stated otherwise). We now present our central problem: 5 Fair Connected Districting (FCD) Input: A graph G = (V, E), a set C of colors, a function col : V → C assigning each vertex one color from C, a number k ≤ |V | of districts, a maximum margin of victory ℓ, and two integers s max ≥ s min ≥ 1. Question: Does there exist a partition of the vertices into k districts ( 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 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 The width of (T, {B x } x∈VT ) is max x∈VT |B x | − 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, tw, and pw, respectively. For all our parameterized algorithms with respect to one of these parameters, we assume that the corresponding structure is given as part of the input. For instance, in our algorithm parameterized by tw, we assume that we are given a tree decomposition. 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.
Parameterized Complexity Theory A parameterized problem L consists of a problem instance I and a parameter value k ∈ N. Then L lies in XP with respect to k if there exists an algorithm deciding L in |I| 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)|I| O(1) time for a computable function f . The corresponding complexity class is called FPT. There is a hierarchy of complexity classes for parameterized problems: FPT⊆ W[1] ⊆ W [2] ⊆ XP, where it is commonly 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 (I ′ , k ′ ) of L ′ to an instance (I, k) of L such that (I ′ , k ′ ) is a yes-instance for L ′ if and only if (I, k) is a yes-instance for L. Moreover, we require that k is bounded in a function of k ′ and that the transformation takes at most f (k ′ )|I| 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.

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 [15]: Perfectly Balanced Connected Partition Input: A graph G = (V, E). Question: Is there a partition (V 1 , V 2 ) of the vertex set V such that G[V 1 ] and G[V 2 ] are connected and |V 1 | = |V 2 |?
Consider the following polynomial-time many-one reduction: Given an instance G = (V, E) of 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, s min = 1, and s max = ∞. 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, s min = 1, s max = ∞, and (i) |C| = 1, k = 2 or (ii) ℓ = 0, |C| = 2, k = 2.
Proof. To prove (ii), we present a polynomial-time Turing reduction from Perfectly Balanced Connected Partition to FCD. To this end, we assume that we have access to an oracle for FCD. Construction. Given an instance (G = (V, E)) of Perfectly Balanced Connected Partition with n := |V |, for each pair of vertices (v, v ′ ) ∈ V 2 , we construct an instance of FCD: We set C = {c 1 , c 2 }, k = 2, and ℓ = 0. We color all vertices of the given graph G in color c 1 . Moreover, we modify G by introducing n new vertices of color c 2 . We connect half of these vertices to v and the other half to v ′ . Subsequently, we query our oracle for FCD on the resulting instance and return yes if the oracle returns yes; otherwise, we continue with the next pair of vertices. After the oracle rejected all instances, we return no.
We now prove the correctness of the reduction by showing that there exists a pair of vertices (v, v ′ ) ∈ V 2 for which the constructed FCD instance is a yes-instance if and only if the given Perfectly Balanced Connected Partition instance is a yes-instance.
Let (V 1 , V 2 ) be a solution to the FCD instance constructed for some pair of vertices (v, v ′ ) ∈ V 2 . As ℓ = 0 and we require that both V 1 and V 2 need to be non-empty, it needs to hold that both districts contain vertices of both colors. Moreover, as both G[V 1 ] and G[V 2 ] are connected, all vertices of color c 2 adjacent to v need to be in the same district as v (and similarly for v ′ ). Thus, v and v ′ need to be in different districts, each consisting of n 2 vertices of color c 2 and n 2 vertices of color c 1 . Thereby, after removing all vertices of color c 2 , (V 1 , V 2 ) is a solution to the given Perfectly Balanced Connected Partition instance.
To prove the reverse direction, let (V 1 , V 2 ) be a solution to the given Perfectly Balanced Connected Partition instance. Let v ∈ V 1 be some vertex from V 1 and v ′ ∈ V 2 be some vertex from V 2 . Then, the FCD instance constructed for (v, v ′ ) is a yes-instance, as it is possible to add the n 2 vertices of color c 2 attached to v to V 1 and the n 2 vertices of color c 2 attached to v ′ to V 2 to arrive at a solution to the FCD instance constructed for pair ( Note that our results strengthen a result of Stoica et al. [43], 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 G 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 ′ is the class of graphs obtained by taking disjoint unions of graphs from G.
Proof. Let G ′ ∈ G ′ and let G 1 , . . . , G p ∈ G be the connected components of G ′ . Clearly, every district is contained in the vertex set of G i for some i ∈ [p]. We solve the problem using a simple subset-sum like dynamic programming algorithm. To this end, we introduce a In the end, we return T [p, k]. This algorithm runs in O(p · k 2 ) = O(n 3 ) time (aside from the computation of H).

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 Section 4.1, we develop polynomialtime algorithms on paths, cycles, stars and caterpillars. Subsequently, in Section 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.

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 programming approach.
Proposition 3. FCD on paths can be solved in O(k · n 2 ) time.
The reasoning behind this is that if we partition 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 · n 2 ).
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 · n 3 ): 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 problem, in which some set X of leaves must belong to the same district as the center vertex, 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, ℓ, s min , s max ) 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 s min and s max 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 solution consists of the center district and several districts consisting of a single vertex from Y . Hence, we may assume that s min = 1. (For s min ≥ 2, we can immediately conclude that there is no solution unless k = 1, X ∪ Y is ℓ-fair, and |X ∪ Y | ∈ [s min , s max ].) We may also assume that |X| ≤ s max . We now describe a linear-time algorithm that decides whether a given FCD instance admits a solution.
We start with several special cases: For ℓ = 0, a solution exists if and only if MOV(X ∪ Y ) = 0, k = 1, and |X ∪ Y | ≤ s max . If |C| = 1, then all solutions containing k districts are isomorphic, i.e., they contain k −1 districts containing a single vertex and a single district containing the remaining vertices. Thus, the given instance admits a solution if and only if |Y Let c 1 ∈ C be the most frequent color in X ∪ Y and c 2 ∈ 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 characterization of yes-instances assuming that |C| > 1, ℓ > 0, s min = 1, s max ≤ |X|, and We first prove the forward direction, i.e., that the existence of a solution implies that k ∈ [b l + 1, |Y | + 1 − b u ] and k > |X| + |Y | − s max . For any solution, the center district contains at most χ c2 (X ∪ Y ) + ℓ vertices of color c 1 (otherwise it cannot be ℓ-fair). Thus, at least χ c1 (X ∪ Y ) − χ c2 (X ∪ Y ) − ℓ vertices of color c 1 have to be part of a non-center district, which implies that k > b l . Next, we show that k ≤ |Y | + 1 − b u . The center district has at least χ c ⋆ 1 (X) vertices of color c ⋆ 1 . Since the center district is ℓ-fair, it has at least χ c ⋆ 1 (X) − ℓ vertices of color c for some color c ∈ C \ {c ⋆ 1 }. As only χ c (X) of the χ c ⋆ 1 (X) − ℓ vertices come from X, it follows that there are at least χ c ⋆ 1 (X) − ℓ − χ c (X) vertices of color c from Y that are included in the center district. As c ⋆ 2 is the most frequent color in X among all colors occurring at least c c ⋆ 1 (X) − ℓ times, it follows that χ c ⋆ 1 (X) − ℓ − χ c ⋆ 2 (X) minimizes the expression from the previous sentence. Using this, we can conclude that k ≤ |Y | + 1 − b u . Finally, we show that k > |X| + |Y | − s max . Since the center district contains at most s max vertices, at least |X| + |Y | − s max vertices are not part of the center district, which implies that k > |X| + |Y | − s max .
We now prove the backward direction, i.e., that , 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 A solution consisting of b l + 1 districts exists: Put all vertices from X ∪ Y in one district and move b l vertices of color c 1 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 is ℓ-fair, as and χ c2 (S) ≥ χ c (S) for all c ∈ C \ {c 1 }. A solution consisting of |Y | + 1 − b u districts is also guaranteed to exist: Put the vertices of X and b u vertices of color c ⋆ 2 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 ′ is ℓ-fair, as Note that from these two solutions, we can construct a solution consisting of k districts for arbitrary 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 maintaining that the center district is ℓ-fair. Such a vertex always exists: If there is a vertex v of 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 | − s max , then the above constructed solution for this k satisfies the size constraints as it consists of a center district containing |X| + |Y | − (k − 1) ≤ s max vertices where the inequality holds by our observation on k .
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 vertices.

Corollary 2. FCD is linear-time solvable on stars.
Lastly, we extend our polynomial-time algorithm for paths from Proposition 3 to caterpillar 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.
Proof. Let G = (V, E) be the given caterpillar, let (u 1 , . . . , u p ) denote the spine (central path) of G and let U = {u 1 , . . . , u p }. Moreover, for i ∈ [p], let U i consist of u i and all vertices from V \ U adjacent to u i . 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 We can fill table A in O(k · n 3 ) time using Proposition 4 for each A[i, j, t] (for this, it is necessary to slightly restructure as the center vertex and X = {u i , . . . , u j }). Using A, we now apply dynamic programming. To this end, we introduce a The reasoning behind this equality is that in a partitioning of j∈[i] U j into t districts, there needs to be some j ∈ [i − 1] such that there is one district containing vertices {u j+1 , . . . , u i }. However, not all vertices from t∈[j+1,i] U t need to be part of this district. In fact, because of the connectivity constraints, there is some t ′′ such that one district contains vertices {u j+1 , . . . , u i } and all but t ′′ − 1 vertices from t∈[j+1,i] U t and t ′′ − 1 districts consist of a single vertex from t∈[j+1,i] U t (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 vertices from t∈[j] U t (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 Figure 2: An illustration of a graph with four branches: 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 polynomial-time solvable on all graphs with pathwidth one (we later show in Corollary 4 that FCD is NP-hard on pathwidthtwo graphs).

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 Figure 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 [27], Eppstein [18] 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). Proof. Let B 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 = (V 1 , . . . , V k ). Observe that there are naturally at most |X| subsets in V containing at least one vertex from X. Without loss of generality, assume that V i contains at least one vertex from X for i ∈ [k ′ ] for some k ′ ∈ [min(k, |X|)], and let X i = X ∩ V i . Let us now consider the relationship between a district V i for i ∈ [k ′ ] and a branch Since V i induces a connected subgraph in G, the following holds: Using these observations, our algorithm proceeds as follows. We iterate over all possible combinations of the following (note that the number of combinations is n O(|B|) = n O(mln 2 ) ): • An integer k ′ ∈ [min(k, |X|)].
• For every branch B = (v 1 , . . . , v l ) ∈ B, two integers j B , j ′ B ∈ [l] with j B + j ′ B ≤ l. Using these guesses, we can exactly determine the districts intersecting X: For every i ∈ [k ′ ] and every branch B = (v 1 , . . . , v l ) ∈ B, we define V i,B as follows: We check whether the set V i is ℓ-fair and respects the size constraints for every i ∈ [k ′ ]. If there is a V i that is not ℓ-fair or violates the size constraints, then we proceed to the next combination. Otherwise, it remains to determine whether the vertices We leave it open whether FCD parameterized by mln is fixed-parameter tractable or W[1]hard.

FCD on Trees and Tree-like Graphs
After having seen in Section 4 that FCD is polynomial-time solvable on paths, cycles, stars, and caterpillars, we now turn to trees. In Section 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 parameter k. In fact, both XPalgorithms further extend to tree-like graphs: In Section 5.2, we prove that FCD parameterized by the treewidth of the given graph plus |C| is in XP. Subsequently, in Sections 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.

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 parameterized 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 [37] (in this subsection, all indices are taken modulo t):

Grid Tiling
, where each S i,j consists of n pairs and the first entries of all pairs (tiles) from S i,j sum up to the same number X for all i, j ∈ [k] and the second entries of all pairs from S i,j sum up to the same number Y for all i, j ∈ [k]¸. Question: Can one choose one tile (x i,j , y i,j ) ∈ S i,j for each i, j ∈ [t] such that x i,j = x i+1,j and y i,j = y i,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 t 2 tile sets S i,j ∈ S. We construct a star T i,j x,y for each tile such that for each tile set S i,j ∈ S, all but exactly one star T i,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.
Construction. Let (S, t, m, n, X, Y ) be an instance of Grid Tiling. We construct an instance of FCD as follows.
We are now ready to construct the vertex-colored graph G = (V, E). We start by introducing a center vertex v center of color c ⋆ . In a solution, we call the district containing v center the center district. We add Z vertices of color c and Z vertices of color c ′ , all of which are only adjacent to v center .
For each i, j ∈ [t] and (x, y) ∈ S i,j , we construct a star T i,j x,y and connect its center to v center . We color the center of T i,j x,y in c ⋆ . Moreover, T i,j x,y has the following leaves: • Z 2(n−1) − W · y − g(i, j ′ ) vertices of color b i,j ′ for j ′ := j + 1 mod k, and Observe that the constructed star T i,j x,y is 0-fair, as the number of occurrences of c i,j matches the number of occurrences of the otherwise most frequent color. This concludes the construction.
Proof of Correctness. We start with a simple observation on the total number of vertices of some of the colors: , vertices of color d i,j occur in 2n different stars, that is, in all stars corresponding to tiles from S i,j and S i−1,j . As the first entries of all tiles from S i,j and of all tiles from S i−1,j sum up to X, it follows that The same reasoning applies for all colors b i,j proving that χ bi,j (V ) = n n−1 Z − 2ng(i, j). Lastly, for some i, j ∈ [t], vertices of color c i,j appear only in stars corresponding to tiles from S i,j , each of them containing at most Z 2(n−1) + W · m such vertices. Thus, the number of vertices of color c i,j is upper-bounded by n · ( Z 2(n−1) + W · m). As W · m = 1 8(n−1) Z and n > 2, this is smaller than Z from which χ ci,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.
} be a solution for the given Grid Tiling instance. From this we construct a solution of the FCD instance as follows. For each (x i,j , y i,j ) ∈ S, we create a separate district and put into this district all vertices from the star T i,j x,y corresponding to (x i,j , y i,j ). We put all other vertices in the center district. Note that this construction respects the given number k = t 2 + 1 of districts and that all districts are by construction non-empty and connected.
It remains to argue that all created districts are 0-fair. Since every star is 0-fair by construction, 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 c i,j this directly follows from Observation 1. Next we consider color d i,j for some i, j ∈ [t]. All stars with some vertices of color d i,j are part of the center district, except for the one corresponding to (x i,j , y i,j ) and the one corresponding to (x i−1,j , y i−1,j ). Since S is a solution, we have x i−1,j = x i,j . Consequently, exactly Z n−1 − 2f (i, j) vertices of color d i,j are excluded from the center district. Now it follows from Observation 1 that the number of vertices of color d i,j in the center district is at most Z. An analogous argument also holds for b i,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. Subsequently, 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 corresponding 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 observing 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 containing 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 possible number of vertices of a color in the center district in a solution. In the following, let V center 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 χ di,j (V center ) ≥ Z, then the number a of stars T i,j x,y with some vertex of color d i,j that are not part of the center district is at most two. In particular, it holds that χ di,j (V center ) = ( n n−1 Z − 2nf (i, j)) − a( Z 2(n−1) − f (i, j)) + W q for some q ∈ [−2m, 2m].
Proof. Let us consider some i, j ∈ [t]. By Observation 2, for every star T i,j x,y , all the vertices from T i,j x,y are in V center or no vertex from T i,j x,y is in V center . By construction, every star with some vertex of color d i,j contains Z 2(n−1) + W · x − f (i, j) vertices of this color for some x ∈ [−m, m]. So as there are n n−1 Z − 2nf (i, j) vertices of color d i,j (Observation 1), if a ≥ 3, then the number of vertices of color d i,j in the center district is at most Z − Z 2(n−1) + 3mW . By the definition of Z this is smaller than Z. Thus, we obtain a ≤ 2. Since there are in total n n−1 Z − 2nf (i, j) vertices of color d i,j by Observation 2, the lemma holds.
Analogously, we can prove similar bounds for the number of vertices of color b i,j for some i, j ∈ [t] in the center district.
, if χ bi,j (V center ) ≥ Z, then the number a of stars T i,j x,y with some vertex of color b i,j that are not part of the center district is at most two. In particular, it holds that 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. Proof. We claim that for two distinct colors q, q ′ with χ q (V center ), χ q ′ (V center ) > Z, it holds that χ q (V center ) = χ q ′ (V center ). The statement of the lemma directly follows from the claim, as V center needs to be 0-fair.
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 T i,j x,y for some (x, y) ∈ S i,j is not part of V center .
Proof. Lemma 2 and Lemma 4 imply that for each i, j ∈ [t] at least two stars containing vertices of color d i,j are not part of V center . As each star T i,j x,y contains vertices of colors d i,j and d i+1,j and as there exist t 2 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 V center .
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 ′ ) ∈ S i,j are not part of V center . This implies by our previous observation that all other stars containing vertices of color d i+1,j need to belong to V center . However, in this case, Z n−1 − W (x + x ′ ) − 2f (i, j) ≤ W n−1 − 2W vertices of color d i+1,j are not part of V center . By Observation 1, this implies that the number of vertices of color d i+1,j in V center is at least Z + 2W − 2nf (i, j). As W > n(t 2 + t), this number is greater than Z, contradicting Lemma 4.
Putting all peaces 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 V be a solution to the constructed FCD instance and let V center ∈ V be the district containing v center . Lemma 5 implies that for each i, j ∈ [t] exactly one star corresponding to a tile from S i,j is not part of V center . Let x,y is not part of V center } 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 x i,j = x i−1,j or (b) exist i ′ , j ′ ∈ [t] such that y i ′ ,j ′ = y i ′ ,j ′ −1 . Let us start by assuming that (a) is the case. Note that it is possible to assume without loss of generality that x i,j < x i−1,j , as from the fact that there exists some x i,j = x i−1,j it follows that there also exists someĩ ∈ [t] such that xĩ ,j < xĩ −1,j . The only stars containing vertices of color d i,j that are not part of V center are the star corresponding to (x i,j , y i,j ), which contains Z 2(n−1) +W ·x i,j −f (i, j) vertices of this color, and the star corresponding to ( vertices of this color are not part of V center , where the inequality holds by our assumption that x i,j < x i−1,j . Combining this with Observation 1, it follows that the number of vertices of color d i,j in V center 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 construction takes only polynomial time and |C| + k = 3t 2 + 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. 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 v center is a disjoint union of stars. Thus, G ′ admits a path decomposition of width one. Placing v center into every bag yields a path decomposition of G of width two. This results in the following. Notably, this 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 s min = 1 and s max = ∞.
We will complement this result in Corollary 8 where we show that FCD is polynomial-time solvable on trees with diameter at most three.

An XP-algorithm for tw + |C|
Motivated by the hardness result from the previous subsection, we search for an XP-algorithm 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 XPalgorithm for |C| on tree-like graphs-more precisely, we present an XP-algorithm with respect to |C| + tw, where tw is the treewidth of the underlying graph.
Given a graph G = (V, E), a tree decomposition (T = (V T , E T ), {B x } x∈VT ) of G (as defined in the Preliminaries) is nice if each node x ∈ V T has one of the following types 6 : Introduce vertex v node. An internal node of T with one child y ∈ V T such that B x = B y ∪{v}.
Introduce edge {u, v} node. An internal node of T with one child y ∈ V T such that u, v ∈ B x = B y .
Forget v node. An internal node of T with one child y ∈ V T such that B Join node. An internal node of T with two children y ∈ V T and z ∈ V T such that B x = B y = B z .
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 [28]. By applying dynamic programming on top of the nice tree decomposition of the given graph, we establish the following: Proof. Suppose that we are given an instance I = (G, C, col, k, ℓ, s min , s max ) of FCD admitting be a tree decomposition of G. For x ∈ V T , let G x be the graph whose vertices and edges are those introduced in a node from the subtree of T rooted at x. Further, let U x be the set of vertices in G x . Our algorithm employs a dynamic programming method that traverses T from bottom to top. Observe that each district V i ∈ V from the solution is of one of the following three types with respect to each x ∈ V T : i.e., the district V i overlaps with the vertices in the bag of x.
(ii) V i ∩ B x = ∅ and V i ⊆ U x , i.e., the district V i is disjoint from B x but fully contained in vertices from bags from the subtree rooted at x.
i.e., the district V i is disjoint from B x 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 V i ∈ V of type (i), the induced subgraph G x [V i ] can have multiple connected components, in which case G[V i ] includes some vertices or edges not in G x .
For each x ∈ V T , we keep track of the following information: (1) the intersection of B x and every V i ∈ V of type (i), (2) the intersection of B x with the connected components of the subgraph G (3) the number of occurrences of color c for every color c ∈ C in V i ∩ U x for every district V i ∈ V of type (i), and (4) the number of districts of type (ii).
We capture this information in the following variables: For each x ∈ V T , let (1) B be a partition of B x , (2) D be a partition of B x where each subset from D is contained in a subset of B, (3) ζ : B → N |C| be some function, and (4) κ ∈ N be some integer with κ ≤ k.
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 distributed 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 D), 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 B, as we cannot remember all vertices put in the districts so far.
It remains to formally describe the dynamic program we use. For all combinations of the variables B, D, ζ, and κ, we compute A x (B, D, ζ, κ) ∈ {0, 1} such that A x (B, D, ζ, κ) = 1 if and only if there is a partition of the vertices U x into exactly |D| + κ subsets (W 1 , . . . , W |D|+κ ) with the following properties: • Exactly κ subsets from (W 1 , . . . , W |D|+κ ) are disjoint from B x . Moreover, all of them are ℓ-fair and respect the size constraints.
From the subsets in the partitioning (W 1 , . . . , W |D|+κ ), κ are ℓ-fair connected districts of type (ii) with respect to x. The other |D| subsets are partly contained in B x and restricted to B x form the partition D describing the intersection of B x with the connected components of G x [V i ] for districts V i of type (i). Note that some of these |D| subsets may end up in the same district in the solution. Moreover, assuming that B corresponds to the intersections of B x and districts of type (i), it needs to hold that for each set in the intersection B ∈ B, ζ(B) is the distribution of colors in the union of all subsets W i 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 partition B r of B r for the root r of T and a function ζ r such that for all B ∈ B r , ζ r (B) is ℓ-fair and its L 1 -norm is in the range [s min , s max ] and A r (B r , B r , ζ r , k − |B r |) = 1.
We compute A x (B, D, ζ, κ) by traversing the nodes V T of the tree T from bottom to top. Depending on the type of the current node x ∈ V T , we apply one of the following five cases. In the following, let y ∈ V T (and z ∈ V T ) be the child node(s) of x if x has one (two) child node(s) in T .  Introduce edge {u, v} node x. If u and v belong to distinct subsets of B, then we have A x (B, D, ζ, κ) = A y (B, D, ζ, κ). We also have the same recurrence if u and v belong to the same subset of D. This is because in both cases the connected components of districts of type (i) in G x do not change. Otherwise, we have where is over all partitions D ′ of B y from which D can be obtained by removing D u , D v ∈ D ′ with u ∈ D u and v ∈ D v from D ′ and adding D u ∪ D v to D ′ .
Forget v node x. We have two cases. In the first case, the district V i ∈ V to which v belongs does not intersect B x . This implies that V i is now fully contained in G x and becomes a district of type (ii). Then {v} should have been part of B and D for child y. Let us define where is over all functions ζ ′ such that ζ ′ (B) = ζ(B) for all B ∈ B, MOV(ζ ′ ({v})) ≤ ℓ, and s min ≤ c∈C ζ ′ c ({v}) ≤ s max . Note that we also need to decrease κ, as V i is an additional district of type (ii) for the node x. In the other case, the district in which v is contained intersects B x . In this case, it holds that Join node x. Note that two vertices u, w ∈ D for some D ∈ D can reach each other in G x via connections in G y and G z . So we have A x (B, D, ζ, κ) = Dy,Dz,ζy,ζz,κy,κz A y (B, D y , ζ y , κ y ) ∧ A z (B, D z , ζ z , κ z ).
Here, is over all D y , D z , ζ y , ζ z , κ y , κ z such that all the following hold: • D are the connected components of the graph whose vertex set is B x and edge set is {{u, w} | (∃D y ∈ D y : u, w ∈ D y ) ∨ (∃D z ∈ D z : u, w ∈ D z )}.
• κ y + κ z = κ. Since a tree is of treewidth one, we have the following: Corollary 6. FCD on trees can be solved in n O(|C|) time.

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 n O(fen +k) time.
Proof. Suppose that there is a solution (V 1 , . . . , V k ). As for each i ∈ [k], V i is connected (for which at least |V i | − 1 edges are needed), the number of edges whose endpoints both lie in the same district is at least 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 · n O(1) = n O(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 raises the question whether there is an XP-algorithm for tw + k. We answer this question negatively in the next subsection.

NP-hardness for fvn = 1 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 n O(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 s min = 1 and s max = ∞.
The rest of the section is devoted to proving the theorem. We reduce from the NP-hard Not-All-Equal 3-Sat problem [41] 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.
Construction. Given an instance (X = {x 1 , . . . , x n }, Y = {y 1 , . . . , y m }) of Not-All-Equal 3-Sat, we construct an instance of FCD as follows. We add a color c x i for each variable x i ∈ X and a color c y j for each clause y j ∈ Y . In addition, we add three colors c, c ′ , and c ′′ . Moreover, we set k = 2, ℓ = 0, s min = 1, and s max = ∞. Let Z := 2 · n · m + 1.
We start the construction of the vertex colored graph G = (V, E) by introducing two central vertices v ⋆ 1 and v ⋆ 2 of color c. We will construct the instance in a way that these two vertices need to lie in different districts.  Subsequently, for each variable x i ∈ X, we introduce two literal vertices v i and v i of color c and connect both these vertices to the two central vertices. For each literal vertexṽ i ∈ {v i , v i }, we introduce 3Z − i vertices of color c x i and connect them toṽ i (these vertices make sure that the two literal vertices end up in different districts). For each clause y j ∈ Y in which x i occurs positively, we introduce Z + j vertices of color c y j and connect them to v i . For each clause y j ∈ Y in which x i occurs negatively, we introduce Z + j vertices of color c y j and connect them to v i (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 Figure 3 for a visualization of the construction.
We start by showing the forward direction of the correctness of the construction.
Lemma 7. If the given Not-All-Equal 3-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 (V 1 , V 2 ) to the constructed FCD instance as follows. We include v ⋆ 1 and all leaves attached to it in V 1 . Moreover, we include in V 1 the following vertices: v i and all leaves attached to it for all x i ∈ X ′ and v i and all leaves attached to it for all x i ∈ X \ X ′ . We include all other vertices in V 2 .
It is easy to verify that V 1 and V 2 are both connected. We will show that V 1 is 0-fair. By symmetry, an analogous argument will show that V 2 is 0-fair. First, observe that V 1 contains exactly 3Z vertices of color c ′ and 3Z vertices of color c ′′ . We show that χc(V 1 ) ≤ 3Z for every colorc ∈ C. For color c, we have that χ c (V 1 ) ≤ χ c (V ) = n + 2 < 3Z. For each variable x i ∈ X, as the two corresponding literal vertices are part of different districts, we have that For each clause y j ∈ Y , as X ′ is a solution, either one or two literal vertices corresponding to literals in y j and the attached leaves are part of V 1 . Thus, the number of vertices of color c y j in V 1 is either Z + j or 2Z + 2j. As Z > 2m, it follows that χ c y j (V 1 ) < 3Z. Thus, both districts V 1 and V 2 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 x i ∈ X, the two literal vertices v i and v i need to end up in different districts. Thus, the two districts correspond to two inverse truth assignments. Subsequently, 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 vertex 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 ⋆ 1 and v ⋆ 2 always lie in different districts.
Observation 4. The two central vertices v ⋆ 1 and v ⋆ 2 cannot belong to the same district in any solution to the constructed FCD instance.
Proof. Assume that v ⋆ 1 and v ⋆ 2 belong to the same district. By Observation 3, the other district V ′ needs to consist of a single literal vertex v i or v i for some x i ∈ X and all leaves attached to it. The most frequent color appearing in V ′ is c x i which occurs 3Z − i > 2Z times (by the definition of Z). The second most frequent color is either c y j for some j ∈ [m] occurring Z + j < 2Z times or c occurring once (by the definition of Z). Thus, the district cannot be 0-fair.
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 Recalling that 3Z − i vertices of color c x i are attached to each literal vertex corresponding to x i ∈ X and that 6Z − 2i > 3Z, the next observation directly follows from the previous lemma and Observation 3.
Observation 5. Let (V 1 , V 2 ) be a solution of the constructed FCD instance. Then, for each x i ∈ X, exactly one of the two corresponding literal vertices v i and v i is part of V 1 and the other is part of V 2 .
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 3-Sat instance is a yes-instance.
Proof. Let (V 1 , V 2 ) be a solution to the constructed FCD instance. From Observation 5, it follows that for each x i ∈ X, exactly one of v i and v i is part of V 1 . Let ϕ be the truth assignment induced by V 1 , i.e., ϕ sets x i to true if v i ∈ V 1 and x i to false if v i ∈ V 1 . We claim that ϕ is a solution to the given Not-All-Equal 3-Sat instance. Firstly, for the sake of contradiction, assume that there exists a clause y j ∈ C containing only literals that are satisfied by ϕ. However, by Observation 3, this implies that all vertices of color c y j are part of V 1 , contradicting Lemma 8 as there exist 3Z + 3j such vertices. Secondly, for the sake of contradiction, assume that y j contains no literal satisfied by ϕ. However, by Observation 3, this implies that all vertices of color c y j are part of V 2 , contradicting again Lemma 8. Consequently, ϕ is a solution.
Observing that {v ⋆ 1 } is a feedback vertex set of the constructed graph and that the construction 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.
Corollary 7. FCD is NP-hard for tw = 2 and k = 2, even if s min = 1 and s max = ∞.

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 parameterized 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 = (V 1 , . . . , V k ) a solution to an FCD instance on a graph G. There are at most vcn districts in V that contain at least one vertex from S. Moreover, for every 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 V i ∈ V. Consider a minimum spanning be the set of vertices of degree at least two in T . Let As by the definition of J i vertices from J i are only adjacent to vertices from S ∩ V i and as every vertex from J i has degree at least two in T and T ′ , we have 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 connected, 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 [21].
Proof. Suppose there is a solution V = (V 1 , . . . , V k ) to the given FCD instance. Let S be a vertex cover of minimum size and let I = V \ S be the vertices outside of the vertex cover. As in the proof of Theorem 6, our algorithm first tries all possibilities to fix some structure with respect to S. Then, we will construct an instance of the polynomial-time solvable (g, f )-Factor problem, which generalizes Maximum Matching, for each choice of the following: • An integer k ′ ≤ min(k, vcn). If ℓ = 0 or s min ≥ 2, then we consider only one choice for k ′ , namely k ′ = k.
• A partition of S into k ′ non-empty subsets S 1 , . . . , S k ′ . There are at most vcn vcn such partitions.
• For every i ∈ [k ′ ], a set J i ⊆ I of at most |S i |−1 vertices such that G[S i ∪J i ] is connected and . We can assume that |J i | ≤ |S i | − 1 vertices are sufficient to make G[S i ] connected by Lemma 10. The number of choices for J i is at most i∈[k ′ ] n |Si|−1 ≤ n vcn .
• For every i ∈ [k ′ ], a pair (c i , c ′ i ) of colors, which have the largest numbers of occurrences in the sought V i among all colors. There are at most |C| 2 vcn choices for all pairs of colors.
• For every i ∈ [k ′ ], the numbers z ci , z c ′ i of occurrences of color c i and c ′ i , respectively, with z ci − ℓ ≤ z c ′ i ≤ z ci . Since z ci ≤ n and z c ′ i ≤ n, there are at most n 2 vcn choices. Since |C| ≤ n, there are at most n O(vcn) choices. Let I ′ = I\ i∈[k ′ ] J i . Now the question is whether we can partition the vertices V into k districts (V 1 , . . . , V k ) such that, for i ∈ [k ′ , k], V i consists of a single vertex from I ′ , and for 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 → N, 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 ∈ {c i , c ′ i }, we add z c − χ c (S i ∪ J i ) vertices (call them A i ) and connect them via edges to all vertices v ∈ I ′ having color c in G which have at least one neighbor in S i in G.
• For each color c ∈ C \ {c i , c ′ i }, we add z c ′ i − χ c (S i ∪ J i ) vertices (call them B c i ) and connect them via edges to all vertices v ∈ I ′ having color c in G which have at least one neighbor in If s min = 1, then we add a set A ′ of k − k ′ vertices to the right bipartition and connect 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 v i to the left side and let f , then we continue with the next combination). We connect v i to all vertices from B c i . 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 ′ is 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 s min = 1, then every vertex adjacent to some vertex from A ′ forms a district of its own). Moreover, for all i ∈ [k ′ ], we add S i ∪ J i to V i . 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 = z ci and χ c ′ i = z c ′ i and thus that the resulting districts are ℓ-fair. Moreover, the number of neighbors of v i in H ′ is between |B i | − s max + |A i ∪ S i ∪ J i | and |B i | − max(0, s min − |A i ∪ S i ∪ J i |), implying that there are at least s min − |A i ∪ S i ∪ J i | and at most s max − |A i ∪ S i ∪ J i | vertices in B i that adjacent to some vertex from I ′ . Thus, the size of each district is in [s min , s max ].
Recall that FCD is NP-hard and W[1]-hard with respect to |C| + k on trees with diameter 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 tractable 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 according 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 [26,32] to obtain the following: Theorem 6. FCD parameterized by vcn + |C| is fixed-parameter tractable.
Proof. Suppose there is a solution V = (V 1 , . . . , V k ). 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 V that contain at least one vertex of S. By Lemma 10, we have k ′ ≤ vcn. Assume without loss of generality that exactly for every 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 T denote the set of all types (note that |T | = 2 vcn · |C|). For type T ∈ T , let n T be the number of vertices of type T , and for type T with n T > 0 let v T ∈ 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 or s min > 1, then we consider only one choice for k ′ , namely k ′ = k.
• A partition of S into non-empty subsets S 1 , . . . , S k ′ . There are at most vcn vcn such partitions.
• For every i ∈ [k ′ ], a set T i of at most |S i | − 1 types such that G[S i ∪ J i ] is connected for J i = {v T | T ∈ T i }. If |{i | T ∈ T i }| > n T for some T ∈ T , then we reject the current combination. Note that we can assume that |T i | ≤ |S i | − 1 vertices are sufficient to make G[S i ] connected by Lemma 10. As there are at most 2 vcn · |C| types, the number of choices for all T i is at most i∈[k ′ ] (2 vcn · |C|) |Si|−1 ≤ 2 vcn 2 · |C| vcn .
• For every i ∈ [k ′ ], a pair (c i , c ′ i ) of colors, which have the largest numbers of occurrences in V i among all colors. In the sought solution it holds that χ ci (V i ) ≥ χ c ′ i (V i ). There are at most |C| 2 vcn choices for all pairs of colors.
To decide on the distribution of the vertices from I, we now construct an ILP. For the ILP formulation, we introduce an integer variable x i,T for each i ∈ [k ′ ] and T ∈ T . The variable x i,T will indicate the number of vertices of type T that we put in V i . Clearly, there are at most n T vertices for each type T ∈ T that belong to one of V 1 , . . . V k ′ : Then for every i ∈ [k ′ ] and T ∈ T i , at least one vertex of type T is included in V i to satisfy our previous guesses: x i,T ≥ 1.
Further for every i ∈ [k ′ ], only vertices from I that are adjacent to a vertex from S i can be part of V i . Thus, for all types T = (c, X) ∈ T with X ∩ S i = ∅ it holds that: x i,T = 0.
Moreover, there are exactly k − k ′ vertices which are contained in none of V 1 , . . . , V k ′ as they form their own districts: For every i ∈ [k ′ ], the following two constraints will ensure that the district V i is ℓ-fair. n i,c ′ i ≤ n i,ci ≤ n i,c ′ i + ℓ, and n i,c ′ i ≥ n i,c for all c ∈ C \ {c i }. Finally, for every i ∈ [k ′ ], the following imposes the size constraints: For the running time, observe that we construct at most 2 O(vcn 2 ) · |C| vcn ILP instances. Since each ILP instance uses at most vcn ·2 vcn · |C| variables, it can be solved in f (vcn +|C|) · n O(1) time for some computable function f due to a result of Lenstra [26,32].
It remains open whether FCD is fixed-parameter tractable or W[1]-hard with respect to 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 vertices, 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. Proposition 7. Let p be the number of vertices with degree at least two. FCD is solvable in O(p p · k · n) time.
For the sake of simplicity, we assume that the graph does not contain connected components of size two (we can deal with them easily separately). Let X ⊆ V be the set of vertices 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 or s min > 1, then we only consider k ′ = k.
• A partition of X into k ′ non-empty subsets X 1 , . . . , X k ′ . There are at most p p such partitions. For i ∈ [k ′ ], let Y i ⊆ Y be the set of vertices from Y that are adjacent to a vertex from X i . If ℓ = 0 or s min > 1, then k ′ = k and hence we accept if (X 1 ∪ Y 1 , . . . , X k ∪ Y k ) is a solution and otherwise continue with the next combination.
Otherwise, we put all vertices from X i in district V i . Each vertex v ∈ Y i is either part of V i 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 X i ∪Y i can be partitioned or we know that no solution exists (in this case, we continue with the next combination). We now check whether the given k lies between i∈[k ′ ] α i and i∈[k ′ ] β i and return the answer.
As there exist p p partitions of X, the running time of the algorithm is O(p p · k · n).

Conclusion
We initiated a thorough study of the NP-hard Fair Connected Districting (FCD) problem. We considered FCD on specific graph classes and analyzed the parameterized complexity 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 number and the max leaf number, we developed XP-algorithms. As to challenges for future research, we left open whether FCD is fixed-parameter tractable or W[1]-hard with respect to the vertex cover number or max leaf number. The former question is particularly intriguing because it is closely related to an open question of Stoica et al. [43] on the parameterized complexity of Fair Regrouping with respect to the number of districts. The latter is interesting because FCD 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. [43], there may be a function that specifies for each vertex a set of districts to which the vertex can belong. 7 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 gerrymandering by Cohen-Zemach et al. [13] and Ito et al. [25]). Weighted FCD is motivated by the following application scenarios: First, in some settings we might be restricted to put a certain 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. [34] and Eiben et al. [16] in the context of Gerrymandering and, among others, by Lu et al. [35] and Fotakis and Tzamos [20] in the context of facility location problems, instead of placing agents on a social network, the agents may be placed in a metric 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.