The Complexity of Finding Fair Independent Sets in Cycles

Introduction

In 1986, Du, Hsu, and Hwang conjectured that if a graph on $3n$ vertices is the disjoint union of a Hamilton cycle of length $3n$ and $n$ pairwise vertex-disjoint triangles then its independence number is $n$. The conjecture has become known as the ‘cycle plus triangles’ problem and has been strengthened by Erdös , who conjectured that such a graph is $3$-colorable. Fleischner and Stiebitz confirmed these conjectures in a strong form and proved, using an algebraic approach of Alon and Tarsi , that such a graph is in fact $3$-choosable. Their proof can also be viewed as an application of Alon’s Combinatorial Nullstellensatz technique . Slightly later, an alternative elementary proof of the $3$-coloring result was given by Sachs . However, none of these proofs supplies an efficient algorithm that given a graph on $3n$ vertices whose set of edges is the disjoint union of a Hamilton cycle and $n$ pairwise vertex-disjoint triangles finds a $3$-coloring of the graph or an independent set of size $n$. Questions on the computational aspects of the problem were posed in several works over the years (see, e.g., ).

A natural extension of the problem of Du et al. is the following. Let $G$ be a cycle and let $V_{1},\ldots,V_{m}$ be a partition of its vertex set into $m$ sets. We are interested in an independent set of $G$ that (almost) fairly represents the given partition, that is, an independent set $S$ of $G$ satisfying $|S\cap V_{i}|\geq\frac{1}{2}\cdot|V_{i}|-1$ for all $i\in[m]=\{1,\ldots,m\}$. The existence of such an independent set was proved in a work of Aharoni, Alon, Berger, Chudnovsky, Kotlar, Loebl, and Ziv . For the special case where all the sets $V_{i}$ are of size $3$, the proof technique of Aharoni et al. allowed them to show that there are two disjoint independent sets that fairly represent the partition, providing a new proof of a stronger form of the original conjecture of Du et al. . The results of were then extended in a work of Alishahi and Meunier . A special case of one of their results is the following.

Let $G$ be a cycle on $n$ vertices and let $V_{1},\ldots,V_{m}$ be a partition of its vertex set into $m$ sets. Suppose that $n$ and $m$ have the same parity. Then, there exist two disjoint independent sets $S_{1}$ and $S_{2}$ of $G$ covering all vertices but one from each $V_{i}$ such that for each $j\in\{1,2\}$, it holds that $|S_{j}\cap V_{i}|\geq\frac{1}{2}\cdot|V_{i}|-1$ for all $i\in[m]$.

As shown by Black et al. , analogues of Theorem 1.1 for paths and for partitions into sets of odd sizes can also be proved using the approach of Aharoni et al. .

It is interesting to mention that although the statements of Theorem 1.1 and of its aforementioned variants are purely combinatorial, all of their known proofs are based on tools from topology. The use of topological methods in combinatorics was initiated by Lovász who applied the Borsuk-Ulam theorem from algebraic topology to prove a conjecture of Kneser on the chromatic number of Kneser graphs. For integers $n\geq 2k$, the Kneser graph $K(n,k)$ is the graph whose vertices are all the $k$-subsets of $[n]$ where two sets are adjacent if they are disjoint. It was proved in that the chromatic number of $K(n,k)$ is $n-2k+2$, a result that was strengthened and generalized by several researchers (see, e.g., [39, Chapter 3]). One such strengthening was obtained by Schrijver , who studied the subgraph of $K(n,k)$ induced by the collection of all $k$-subsets of $[n]$ with no two consecutive elements modulo $n$. This graph is denoted by $S(n,k)$ and is commonly referred to as the Schrijver graph. It was proved in , again by a topological argument, that the chromatic number of $S(n,k)$ is equal to that of $K(n,k)$. As for Theorem 1.1, the proof of Alishahi and Meunier employs the Octahedral Tucker lemma that was applied by Matoušek in an alternative proof of Kneser’s conjecture and can be viewed as a combinatorial formulation of the Borsuk-Ulam theorem (see also ). The approach of Aharoni et al. and of Black et al. , however, is based on a direct application of the chromatic number of the Schrijver graph. As before, these proofs are not constructive, in the sense that they do not suggest efficient algorithms for the corresponding search problems. Understanding the computational complexity of these problems is the main motivation for the current work.

In 1994, Papadimitriou has initiated the study of the complexity of total search problems in view of the mathematical argument that lies at the existence proof of their solutions. Let $\mathsf{TFNP}$ be the complexity class, defined in , of the total search problems in $\mathsf{NP}$, that is, the class of search problems in which a solution is guaranteed to exist and can be verified in polynomial running-time. Papadimitriou has introduced in several subclasses of $\mathsf{TFNP}$, each of which consists of the total search problems that can be reduced to a problem that represents some mathematical argument. For example, the class $\mathsf{PPA}$ (Polynomial Parity Argument) corresponds to the simple fact that every graph with maximum degree $2$ that has a vertex of degree $1$ must have another degree $1$ vertex. Hence, $\mathsf{PPA}$ is defined as the class of all problems in $\mathsf{TFNP}$ that can be efficiently reduced to the Leaf problem, in which given a succinct representation of a graph with maximum degree $2$ and given a vertex of degree $1$ in the graph, the goal is to find another such vertex. The class $\mathsf{PPAD}$ (Polynomial Parity Argument in Directed graphs) is defined similarly with respect to directed graphs. Another complexity class defined in is $\mathsf{PPP}$ (Polynomial Pigeonhole Principle) whose underlying mathematical argument is the pigeonhole principle. Additional examples of complexity classes defined in this way are $\mathsf{PLS}$ (Polynomial Local Search) , $\mathsf{CLS}$ (Continuous Local Search) , and $\mathsf{EOPL}$ (End of Potential Line) .

The complexity class $\mathsf{PPAD}$ is known to perfectly capture the complexity of many important search problems. Notable examples of $\mathsf{PPAD}$-complete problems are those associated with Sperner’s lemma , the Nash Equilibrium theorem , the Envy-Free Cake Cutting theorem , and the Hairy Ball theorem . For $\mathsf{PPA}$, the undirected analogue of $\mathsf{PPAD}$, until recently no ‘natural’ complete problems were known, where by ‘natural’ we mean that their definitions do not involve circuits and Turing machines. In the last few years, the situation was changed following a breakthrough result of Filos-Ratsikas and Goldberg , who proved that the Consensus Halving problem with an inverse-polynomial precision parameter is $\mathsf{PPA}$-complete (see also ) and used it to derive the $\mathsf{PPA}$-completeness of the classical Splitting Necklace with two thieves and Discrete Sandwich problems. This was obtained building on the $\mathsf{PPA}$-hardness, proved by Aisenberg, Bonet, and Buss , of the search problem associated with Tucker’s lemma. The variant of the problem that corresponds to the Octahedral Tucker lemma was suggested for study by Pálvölgyi and proved to be $\mathsf{PPA}$-complete by Deng, Feng, and Kulkarni . The $\mathsf{PPA}$-completeness of the Consensus Halving problem was improved to a constant precision parameter in a recent work of Deligkas, Fearnley, Hollender, and Melissourgos . Additional examples of $\mathsf{PPA}$-complete problems can be found, for instance, in the works of Belovs et al. , Schnider , and Deligkas et al. .

The present work initiates the study of the complexity of finding independent sets that fairly represent a given partition of the vertex set of a cycle. It is motivated by the computational aspects of combinatorial existence statements, such as the ‘cycle plus triangles’ conjecture of Du et al. proved by Fleischner and Stiebitz and its extensions by Aharoni et al. , Alishahi and Meunier , and Black et al. . As mentioned before, the challenge of understanding the complexity of the corresponding search problems was explicitly raised by several authors, including Fleischner and Stiebitz , Alon , and Aharoni et al. . In this work we demonstrate that this research avenue may illuminate interesting connections between this family of problems and the complexity class $\mathsf{PPA}$. As an application, we determine the complexity of finding a monochromatic edge in Schrijver graphs colored by fewer colors than the chromatic number.

We start by introducing the Fair Independent Set in Cycle Problem, which we denote by Fair-IS-Cycle and define as follows.

In the Fair-IS-Cycle problem, the input consists of a cycle $G$ and a partition $V_{1},\ldots,V_{m}$ of its vertex set into $m$ sets. The goal is to find an independent set $S$ of $G$ satisfying $|S\cap V_{i}|\geq\frac{1}{2}\cdot|V_{i}|-1$ for all $i\in[m]$.

The existence of a solution to every input of Fair-IS-Cycle is guaranteed by a result of Aharoni et al. [1, Theorem 1.8]. Since such a solution can be verified in polynomial running-time, the total search problem Fair-IS-Cycle lies in the complexity class $\mathsf{TFNP}$. We prove that the class $\mathsf{PPA}$ captures the complexity of the problem.

The Fair-IS-Cycle problem is $\mathsf{PPA}$-complete.

In view of the ‘cycle plus triangles’ problem of Du et al. , it would be interesting to understand the complexity of the Fair-IS-Cycle problem restricted to partitions into sets of size $3$. While Theorem 1.3 immediately implies that this restricted problem lies in $\mathsf{PPA}$, the question of determining its precise complexity remains open.

We proceed by considering the search problem associated with Theorem 1.1. In the Fair Splitting of Cycle Problem, denoted Fair-Split-Cycle, we are given a cycle and a partition of its vertex set and the goal is to find two disjoint independent sets that fairly represent the partition and cover all vertices but one from every part of the partition. We define below an approximate version of this problem, in which the fairness requirement is replaced with the relaxed notion of $\varepsilon$-fairness, where the independent sets should include at least $\frac{1}{2}-\varepsilon$ fraction of the vertices of every part.

In the $\varepsilon\textsc{-}\textsc{Fair-Split-Cycle}$ problem with parameter $\varepsilon\geq 0$, the input consists of a cycle $G$ on $n$ vertices and a partition $V_{1},\ldots,V_{m}$ of its vertex set into $m$ sets, such that $n$ and $m$ have the same parity. The goal is to find two disjoint independent sets $S_{1}$ and $S_{2}$ of $G$ covering all vertices but one from each $V_{i}$ such that for each $j\in\{1,2\}$, it holds that $|S_{j}\cap V_{i}|\geq(\frac{1}{2}-\varepsilon)\cdot|V_{i}|-1$ for all $i\in[m]$. For $\varepsilon=0$, the problem is denoted by Fair-Split-Cycle.

The existence of a solution to every input of $\varepsilon\textsc{-}\textsc{Fair-Split-Cycle}$, already for $\varepsilon=0$, is guaranteed by Theorem 1.1 proved in . For $\varepsilon=0$, it can be seen that Fair-Split-Cycle is at least as hard as Fair-IS-Cycle (see Lemma 2.10). Yet, it turns out that Fair-Split-Cycle lies in $\mathsf{PPA}$ and is thus also $\mathsf{PPA}$-complete.

The Fair-Split-Cycle problem is $\mathsf{PPA}$-complete.

In fact, using the recent work , we also obtain the following $\mathsf{PPA}$-completeness result for the approximate version of the problem (see Remark 2.9).

There exists a constant $\varepsilon>0$ for which the $\varepsilon\textsf{-}\textsc{Fair-Split-Cycle}$ problem is $\mathsf{PPA}$-complete.

We finally consider the complexity of the Schrijver problem. In this problem we are given a succinct representation of a coloring of the Schrijver graph $S(n,k)$ with $n-2k+1$ colors, which is one less than its chromatic number , and the goal is to find a monochromatic edge (see Definition 3.1). The study of the Schrijver problem is motivated by a question raised by Deng et al. regarding the complexity of the analogue Kneser problem for Kneser graphs. Note that the latter is not harder than the Schrijver problem, because $S(n,k)$ is a subgraph of $K(n,k)$ with the same chromatic number. As an application of our Theorem 1.3, we prove the following.

The Schrijver problem is $\mathsf{PPA}$-complete.

It would be interesting to determine the computational complexity of the Kneser problem and to decide whether it is $\mathsf{PPA}$-complete, as suggested in . It would also be interesting to prove unconditional lower bounds on the query complexity of algorithms for the Kneser and Schrijver problems in the black-box input model, where the input is given as an oracle access. We note that the study of the Kneser problem is motivated by its connections to a resource allocation problem called Agreeable Set, that was introduced by Manurangsi and Suksompong and further studied in . From an algorithmic point of view, it was shown in the recent works that there exist randomized algorithms for the Kneser and Schrijver problems with running time $n^{O(1)}\cdot k^{O(k)}$ on graphs $K(n,k)$ and $S(n,k)$ respectively, hence these problems are fixed-parameter tractable with respect to the parameter $k$. It would be nice to further explore algorithms for these problems as well as for the other problems studied in the current work.

2 Overview of Proofs

To obtain our results we present a chain of reductions, as described in Figure 1. Our starting point is the Consensus Halving problem with precision parameter $\varepsilon$, in which given a collection of $m$ probability measures on the interval $$the goal is to partition the interval into two pieces using relatively few cuts, so that each of the measures has the same mass on the two pieces up to an error of$\varepsilon$(see Definition 2.1). It is known that every instance of this problem has a solution with at most$m$cuts even for$\varepsilon=0$(see also ) and that the problem of finding such a solution is$\mathsf{PPA}$-hard for some constant$\varepsilon>0$ .

In Section 2, we reduce the Consensus Halving problem to an intermediate variant of the $\varepsilon\textsf{-}\textsc{Fair-Split-Cycle}$ problem, which we call $\varepsilon\textsf{-}\textsc{Fair-Split-Path}^{\prime}$ (see Definition 2.4). Then, we use this reduction to obtain our hardness results for the Fair-IS-Cycle and Fair-Split-Cycle problems. The reduction borrows a discretization argument that was used in to reduce the Consensus Halving problem to the Splitting Necklace problem with two thieves. This argument enables us to transform a Consensus Halving instance into a path and a partition of its vertex set, for which the goal is to partition the path using relatively few cuts into two parts, each of which contains roughly half of the vertices of every set in the partition. In order to relate this problem to independent sets that fairly represent the partition, we need an additional simple trick. Between every two consecutive vertices of the path we add a new vertex and put all the new vertices in a new set added to the partition of the vertex set. We then argue, roughly speaking, that two disjoint independent sets in the obtained path, which fairly represent the partition and cover almost all of the vertices, can be used to obtain a solution to the original instance. The high-level idea is that those few vertices that are uncovered by the two independent sets can be viewed as cuts, and every path between two such vertices alternates between the two given independent sets. By construction, it means that only one of the two independent sets contains in such a path original vertices (that is, vertices that were not added in the last phase of the reduction), hence every such path can be naturally assigned to one of the two pieces required by the Consensus Halving problem. Combining our reduction with the known hardness results of Consensus Halving, we derive the $\mathsf{PPA}$-hardness of Fair-IS-Cycle and of $\varepsilon\textsf{-}\textsc{Fair-Split-Cycle}$ for a constant $\varepsilon>0$, as needed for Theorems 1.3, 1.5, and 1.6.

In Section 3, we introduce and study the Schrijver problem. We reduce the Fair-IS-Cycle problem to the Schrijver problem, implying that the latter is $\mathsf{PPA}$-hard. The reduction follows an argument of Aharoni et al. who used the chromatic number of the Schrijver graph to prove the existence of the independent set required in Fair-IS-Cycle. Finally, employing arguments of Meunier and Alishahi and Meunier , we reduce the Schrijver and Fair-Split-Cycle problems to the search problem associated with the Octahedral Tucker lemma (see Definition 3.3). Since it is known, already from , that this problem lies in $\mathsf{PPA}$, we get that Fair-IS-Cycle, Fair-Split-Cycle, and Schrijver are all members of $\mathsf{PPA}$, completing the proofs of Theorems 1.3, 1.5, 1.6, and 1.7.

We remark that one could consider analogues of the Fair-IS-Cycle and Fair-Split-Cycle problems for paths rather than for cycles and obtain similar results. We have chosen to focus here on the cycle setting, motivated by the computational aspects of the ‘cycle plus triangles’ problem .

Fair Independent Sets in Cycles

In this section we prove our hardness results for the Fair-IS-Cycle and Fair-Split-Cycle problems. We first recall the definition of the Consensus Halving problem and state its hardness result from . Then, we present an efficient reduction from this problem to an intermediate problem, which is used to obtain the hardness results of Theorems 1.3, 1.5, and 1.6.

Consider the following variant of the Consensus Halving problem, denoted Con-Halving.

There exists a constant $\varepsilon>0$ such that for every constant $c\geq 0$, the $\varepsilon\textsf{-}\textsc{Con-Halving}(m,m+c)$ problem, restricted to inputs with piecewise constant density functions with at most $3$ blocks, is $\mathsf{PPA}$-hard.

We note that, as explained in , the constant $c$ given in Theorem 2.2 can be replaced by $m^{1-\alpha}$ for any constant $\alpha>0$. This stronger hardness, however, is not required to obtain our results. We also note that our results do not rely on the fact that the hardness given in Theorem 2.2 holds for instances with density functions with at most $3$ blocks, as proved in , rather than polynomially many blocks.

2 The Main Reduction

To obtain our hardness results for the Fair-IS-Cycle and Fair-Split-Cycle problems, we consider the following intermediate problem.

In the $\varepsilon\textsc{-}\textsc{Fair-Split-Path}^{\prime}$ problem with parameter $\varepsilon\geq 0$, the input consists of a path $G$ and a partition $V_{1},\ldots,V_{m}$ of its vertex set into $m$ sets such that $|V_{i}|$ is odd for all $i\in[m]$. The goal is to find two disjoint independent sets $S_{1}$ and $S_{2}$ of $G$ covering all but at most $m$ of the vertices of $G$ such that

for all $i\in[m]$. When $\varepsilon=0$, the problem is denoted by $\textsc{Fair-Split-Path}^{\prime}$.

Note that the $\varepsilon\textsc{-}\textsc{Fair-Split-Path}^{\prime}$ problem differs from the $\varepsilon\textsc{-}\textsc{Fair-Split-Cycle}$ problem (see Definition 1.4) in the following respects: (a) The input graph is a path rather than a cycle, (b) an $\varepsilon$-fairness property is required only for the independent set $S_{1}$ rather than for both $S_{1}$ and $S_{2}$, (c) there is no requirement regarding the sets $V_{i}$ to which the vertices that are uncovered by $S_{1}$ and $S_{2}$ belong, and (d) the sets $V_{i}$ are required to be of odd sizes. Yet, every instance of the $\varepsilon\textsc{-}\textsc{Fair-Split-Path}^{\prime}$ problem has a solution already for $\varepsilon=0$, as follows from Theorem 1.1 applied to the cycle obtained by connecting the endpoints of the given path by an edge.

Let $p$ be a polynomial and suppose that $\varepsilon=\varepsilon(m)$ is bounded from below by some inverse-polynomial in $m$. Then, for any constant $\alpha\in[0,1)$, the $\varepsilon\textsf{-}\textsc{Con-Halving}(m,m+1)$ problem, restricted to inputs with piecewise constant density functions with at most $p(m)$ blocks, is polynomial-time reducible to the $\frac{\alpha\cdot\varepsilon}{2}\textsc{-}\textsc{Fair-Split-Path}^{\prime}$ problem.

Consider an instance of $\varepsilon\textsc{-}\textsc{Con-Halving}(m,m+1)$ consisting of $m$ probability measures $\mu_{1},\ldots,\mu_{m}$ on the interval $I=$, given by their piecewise constant density functions $g_{1},\ldots,g_{m}$, each of which has at most $p(m)$ blocks. Fix any constant $\alpha\in[0,1)$. The reduction constructs an instance of $\frac{\alpha\cdot\varepsilon}{2}\textsc{-}\textsc{Fair-Split-Path}^{\prime}$, namely, a path $G$ and a partition $V_{1},\ldots,V_{m+1}$ of its vertex set into $m+1$ sets of odd sizes.

We start with a high-level description of the reduction. First, borrowing a discretization argument of , the reduction associates with every density function $g_{i}$ a collection $V_{i}$ of vertices located in the (at most $p(m)$) intervals on which $g_{i}$ is nonzero. To do so, we partition every block of $g_{i}$ into sub-intervals such that the measure of $\mu_{i}$ on each of them is $\delta$, where $\delta>0$ is some small parameter (assuming, for now, that the measure of $\mu_{i}$ on every block is an integer multiple of $\delta$). At the middle of every such sub-interval we locate a vertex and put it in $V_{i}$. Then, we construct a path $G$ that alternates between the vertices of $V_{1}\cup\cdots\cup V_{m}$ ordered according to their locations in $I$ and additional vertices which we put in another set $V_{m+1}$. We also take care of the requirement that each $|V_{i}|$ is odd.

The intuitive idea behind this reduction is the following. Suppose that we are given a solution to the constructed instance, i.e., two disjoint independent sets $S_{1}$ and $S_{2}$ of the path $G$ covering all but $m+1$ of the vertices such that $S_{1}$ contains roughly half of the vertices of $V_{i}$ for each $i\in[m+1]$. Observe that by removing from $G$ the $m+1$ vertices that do not belong to $S_{1}\cup S_{2}$, we essentially get a partition of the vertices of $S_{1}\cup S_{2}$ into $m+2$ paths. Since $S_{1}$ and $S_{2}$ are independent sets in $G$, it follows that each such path alternates between $S_{1}$ and $S_{2}$. However, recalling that $G$ alternates between $V_{1}\cup\cdots\cup V_{m}$ and $V_{m+1}$, it follows that ignoring the vertices of $V_{m+1}$, each such path contains either only vertices of $S_{1}$ or only vertices of $S_{2}$. Now, one can view the $m+1$ locations of the vertices that do not belong to $S_{1}\cup S_{2}$ as cuts in the interval $I$ which partition it into $m+2$ sub-intervals, each of which includes vertices from either $S_{1}$ or $S_{2}$ (again, ignoring the vertices of $V_{m+1}$). Let $I^{+}$ and $I^{-}$ be the pieces of $I$ obtained from the sub-intervals that correspond to $S_{1}$ and $S_{2}$ respectively. Since the number of vertices from $V_{i}$ in every path is approximately proportional to the measure of $\mu_{i}$ in the corresponding sub-interval, it can be shown that the probability measure of $\mu_{i}$ on $I^{+}$ is approximately $\frac{1}{2}$. This yields that the probability measure $\mu_{i}$ is approximately equal on the pieces $I^{+}$ and $I^{-}$, as needed for the $\textsc{Con-Halving}(m,m+1)$ problem.

We turn to the formal description of the reduction. For an illustration, see Figure 2. Define $\delta=\frac{(1-\alpha)\cdot\varepsilon}{2\cdot(2p(m)+m+3)}$. The reduction acts as follows.

We are given a partition of the interval $I$ into intervals such that on at most $p(m)$ of them the function $g_{i}$ is equal to a nonzero value and is zero everywhere else. For every such interval, let $\gamma$ denote the volume of $g_{i}$ on it, and divide it into $\lceil\gamma/\delta\rceil$ sub-intervals of volume $\delta$ each, possibly besides the last one whose volume might be smaller. We refer to a sub-interval of volume smaller than $\delta$ as an imperfect sub-interval. The number of imperfect sub-intervals associated with $g_{i}$ is clearly at most $p(m)$. At the middle point of every sub-interval of $g_{i}$, locate a vertex and put it in the set $V_{i}$.

If the number of vertices in $V_{i}$ is even, then add another vertex to $V_{i}$ and locate it arbitrarily in $I$.

Consider the path on the vertices of $V_{1}\cup\cdots\cup V_{m}$ ordered according to their locations in the interval $I$, breaking ties arbitrarily.

Add a new vertex before every vertex in this path, locate it at the middle of the sub-interval between its two adjacent vertices (where the first new vertex is located at ), and put these new vertices in the set $V_{m+1}$. If the number of vertices in $V_{m+1}$ is even then add one more vertex to the end of the path, locate it at $1$, and put it in $V_{m+1}$ as well. Denote by $G$ the obtained path, and note that $G$ alternates between $V_{1}\cup\cdots\cup V_{m}$ and $V_{m+1}$.

The output of the reduction is the path $G$ and the partition $V_{1},\ldots,V_{m+1}$ of its vertex set $V$ into $m+1$ sets. By construction, $|V_{i}|$ is odd for every $i\in[m+1]$.

It is easy to verify that the reduction can be implemented in polynomial running-time. Indeed, every density function $g_{i}$ is piecewise constant with at most $p(m)$ blocks, hence for every $i\in[m]$ the number of vertices that the reduction defines for $V_{i}$ is at most $1/\delta+p(m)+1$, and the latter is polynomial in the input size because of the definition of $\delta$ and the fact that $\varepsilon$ is at least inverse-polynomial in $m$. The additional set $V_{m+1}$ doubles the number of vertices, possibly with one extra vertex, preserving the construction polynomial in the input size.

We turn to prove the correctness of the reduction, that is, that a solution to the constructed instance of $\frac{\alpha\cdot\varepsilon}{2}\textsc{-}\textsc{Fair-Split-Path}^{\prime}$ can be used to efficiently compute a solution to the original instance of $\varepsilon\textsf{-}\textsc{Con-Halving}(m,m+1)$. Suppose we are given a solution to $\frac{\alpha\cdot\varepsilon}{2}\textsc{-}\textsc{Fair-Split-Path}^{\prime}$ for the path $G$ and the partition $V_{1},\ldots,V_{m+1}$ of its vertex set $V$. Such a solution consists of two disjoint independent sets $S_{1}$ and $S_{2}$ of $G$ covering all but at most $m+1$ of the vertices of $G$ such that

for all $i\in[m+1]$. Let $S_{3}=V\setminus(S_{1}\cup S_{2})$. It can be assumed that $|S_{3}|=m+1$ (otherwise, remove some arbitrary vertices from $S_{2}$). Denote the vertices of $S_{3}$ by $u_{1},\ldots,u_{m+1}$ ordered according to their order in $G$. Let $P_{1},\ldots,P_{m+2}$ be the $m+2$ paths obtained from $G$ by removing the vertices of $S_{3}$ (where some of the paths might be empty). Since $S_{1}$ and $S_{2}$ are independent sets, every path $P_{j}$ alternates between $S_{1}$ and $S_{2}$. By our construction, this implies that in every path $P_{j}$ either the vertices of $S_{1}$ are from $V\setminus V_{m+1}$ and those of $S_{2}$ are from $V_{m+1}$, or the vertices of $S_{2}$ are from $V\setminus V_{m+1}$ and those of $S_{1}$ are from $V_{m+1}$. We define $b_{j}=1$ in the former case and $b_{j}=2$ in the latter. Thus, for every $i\in[m]$, the number of vertices of $V_{i}$ that appear in the paths $P_{j}$ with $b_{j}=1$ is precisely $|S_{1}\cap V_{i}|$.

Now, let $\beta_{1},\ldots,\beta_{m+1}\in I$ be the locations of the vertices $u_{1},\ldots,u_{m+1}$ in the interval $I$ as defined by the reduction. We interpret these locations as $m+1$ cuts of the interval $I$. Set $\beta_{0}=0$ and $\beta_{m+2}=1$, and for every $j\in[m+2]$, let $I_{j}$ denote the interval $[\beta_{j-1},\beta_{j}]$. Consider the partition of $I$ into two pieces $I^{+}$ and $I^{-}$, where $I^{+}$ includes all the parts $I_{j}$ with $b_{j}=1$ and $I^{-}$ includes all the parts $I_{j}$ with $b_{j}=2$. We claim that this partition, which is obtained using $m+1$ cuts in $I$, forms a valid solution to the original instance of $\varepsilon\textsf{-}\textsc{Con-Halving}(m,m+1)$. To this end, we show that for every $i\in[m]$ it holds that $|\mu_{i}(I^{+})-\frac{1}{2}|\leq\frac{\varepsilon}{2}$, which is equivalent to $|\mu_{i}(I^{+})-\mu_{i}(I^{-})|\leq\varepsilon$.

Fix some $i\in[m]$. We turn to estimate the quantity $\mu_{i}(I^{+})$, i.e., the total measure of $\mu_{i}$ on the intervals $I_{j}$ with $b_{j}=1$. By our construction, every vertex of $V_{i}$ corresponds to a sub-interval whose measure by $\mu_{i}$ is $\delta$ (except for at most $p(m)+1$ of them). Since the intervals of $I^{+}$ correspond to the paths $P_{j}$ whose vertices in $V\setminus V_{m+1}$ are precisely the vertices of $S_{1}\setminus V_{m+1}$, one would expect $\mu_{i}(I^{+})$ to measure the number of vertices in $S_{1}\cap V_{i}$, with a contribution of $\delta$ per every such vertex. This suggests an estimation of $|S_{1}\cap V_{i}|\cdot\delta$ for $\mu_{i}(I^{+})$. This estimation, however, is not accurate for the following reasons:

The set $V_{i}$ might include vertices that correspond to imperfect sub-intervals whose measure by $\mu_{i}$ is smaller than $\delta$. Since there are at most $p(m)$ such vertices in $V_{i}$, they can cause an error of at most $p(m)\cdot\delta$ in the above estimation.

To make sure that $|V_{i}|$ is odd, the reduction might add one extra vertex to $V_{i}$. This might cause an error of at most $\delta$ in the above estimation.

The precise locations $\beta_{j}$ of the cuts of $I$ might fall inside sub-intervals that correspond to vertices of $V_{i}$. Since the sub-intervals that correspond to vertices of $V_{i}$ are disjoint, every such cut can cause an error of at most $\delta$ in the above estimation, and since there are $m+1$ cuts the error here is bounded by $(m+1)\cdot\delta$.

We conclude that $\mu_{i}(I^{+})$ differs from the aforementioned estimation $|S_{1}\cap V_{i}|\cdot\delta$ by not more than $(p(m)+m+2)\cdot\delta$. Combining (1) and (2), it can be verified that

where the last equality holds by the definition of $\delta$. This completes the proof.

There exists a constant $\varepsilon>0$ for which the $\varepsilon\textsf{-}\textsc{Fair-Split-Path}^{\prime}$ problem is $\mathsf{PPA}$-hard.

By Theorem 2.2, the $\varepsilon\textsf{-}\textsc{Con-Halving}(m,m+1)$ problem is $\mathsf{PPA}$-hard for input density functions that are piecewise constant with at most $3$ blocks, where $\varepsilon>0$ is some constant. By Theorem 2.5, for any $\alpha\in[0,1)$, this problem is polynomial-time reducible to the $\frac{\alpha\cdot\varepsilon}{2}\textsf{-}\textsc{Fair-Split-Path}^{\prime}$ problem, implying the assertion of the theorem.

3 Hardness of Fair-IS-Cycle and Fair-Split-Cycle

Equipped with Theorem 2.6, we are ready to derive the hardness of the Fair-IS-Cycle and Fair-Split-Cycle problems (see Definitions 1.2 and 1.4).

The Fair-IS-Cycle problem is $\mathsf{PPA}$-hard.

By Theorem 2.6, the $\varepsilon\textsf{-}\textsc{Fair-Split-Path}^{\prime}$ problem is $\mathsf{PPA}$-hard for some $\varepsilon>0$. It thus follows that $\textsc{Fair-Split-Path}^{\prime}$, with $\varepsilon=0$, is $\mathsf{PPA}$-hard as well. Hence, to prove the theorem, it suffices to show that $\textsc{Fair-Split-Path}^{\prime}$ is polynomial-time reducible to Fair-IS-Cycle.

Consider an instance of $\textsc{Fair-Split-Path}^{\prime}$, that is, a path $G$ on $n$ vertices and a partition $V_{1},\ldots,V_{m}$ of its vertex set into $m$ sets such that $|V_{i}|$ is odd for all $i\in[m]$. The reduction simply returns the cycle $G^{\prime}$, obtained from the path $G$ by connecting its endpoints by an edge, and the same partition $V_{1},\ldots,V_{m}$ of its vertex set. For correctness, suppose that we are given a solution to this instance of Fair-IS-Cycle, i.e., an independent set $S_{1}$ of $G^{\prime}$ satisfying $|S_{1}\cap V_{i}|\geq\frac{1}{2}\cdot|V_{i}|-1$ for all $i\in[m]$. Since each $|V_{i}|$ is odd, it can be assumed that $|S_{1}\cap V_{i}|=\frac{1}{2}\cdot(|V_{i}|-1)$ for all $i\in[m]$ (by removing some vertices from $S_{1}$ if needed), implying that

For every vertex of $S_{1}$ consider the vertex that follows it in the cycle $G^{\prime}$ (say, oriented clockwise), and let $S_{2}$ be the set of vertices that follow those of $S_{1}$. Since $S_{1}$ is an independent set in $G^{\prime}$, we get that $S_{2}$ is another independent set in $G^{\prime}$ which is disjoint from $S_{1}$ and has the same size. We obtain that

hence $S_{1}$ and $S_{2}$ are two disjoint independent sets of $G^{\prime}$ covering all but $m$ of its vertices. In particular, $S_{1}$ and $S_{2}$ are independent sets in the path $G$, and as such, they form a valid solution to the $\textsc{Fair-Split-Path}^{\prime}$ instance. This solution can clearly be constructed in polynomial running-time given $S_{1}$, completing the proof.

There exists a constant $\varepsilon>0$ for which the $\varepsilon\textsf{-}\textsc{Fair-Split-Cycle}$ problem is $\mathsf{PPA}$-hard.

By Theorem 2.6, the $\varepsilon\textsf{-}\textsc{Fair-Split-Path}^{\prime}$ problem is $\mathsf{PPA}$-hard for some constant $\varepsilon>0$. It thus suffices to show that for every $\varepsilon\geq 0$, the $\varepsilon\textsf{-}\textsc{Fair-Split-Path}^{\prime}$ problem is polynomial-time reducible to the $\varepsilon\textsf{-}\textsc{Fair-Split-Cycle}$ problem.

Consider again the reduction that given a path $G$ and a partition $V_{1},\ldots,V_{m}$ of its vertex set into sets of odd sizes returns the cycle $G^{\prime}$, obtained from the path $G$ by connecting its endpoints by an edge, and the same partition $V_{1},\ldots,V_{m}$. Since the sets of the partition have odd sizes, it follows that the number of vertices and the number of sets in the partition have the same parity, hence the reduction provides an appropriate instance of the $\varepsilon\textsf{-}\textsc{Fair-Split-Cycle}$ problem.

For correctness, consider a solution to the constructed instance, i.e., two disjoint independent sets $S_{1}$ and $S_{2}$ of $G^{\prime}$ covering all vertices but one from each part $V_{i}$ such that for each $j\in\{1,2\}$, it holds that $|S_{j}\cap V_{i}|\geq(\frac{1}{2}-\varepsilon)\cdot|V_{i}|-1$ for all $i\in[m]$. We claim that $S_{1}$ and $S_{2}$ form a valid solution to the original $\varepsilon\textsf{-}\textsc{Fair-Split-Path}^{\prime}$ instance. Indeed, an independent set in $G^{\prime}$ is also an independent set in $G$. In addition, the set $S_{1}$ satisfies |S_{1}\cap V_{i}|\in\big{[}(\tfrac{1}{2}-\varepsilon)\cdot|V_{i}|-1,(\tfrac{1}{2}+\varepsilon)\cdot|V_{i}|\big{]} for all $i\in[m]$, where the upper bound holds because

The $\mathsf{PPA}$-hardness of the $\varepsilon\textsf{-}\textsc{Con-Halving}(m,m+1)$ problem, given by Theorem 2.2, was proved in for any constant $\varepsilon<0.2$. It thus follows from the proofs of Theorems 2.6 and 2.8 that $\varepsilon\textsf{-}\textsc{Fair-Split-Cycle}$ is $\mathsf{PPA}$-hard for any constant $\varepsilon<0.1$.

Theorem 2.8 implies that the Fair-Split-Cycle problem, with $\varepsilon=0$, is $\mathsf{PPA}$-hard. The following simple lemma shows that this hardness result can also be derived from the hardness of the Fair-IS-Cycle problem, given in Theorem 2.7.

The Fair-IS-Cycle problem is polynomial-time reducible to the Fair-Split-Cycle problem.

Consider an instance of Fair-IS-Cycle, that is, a cycle $G$ on $n$ vertices and a partition $V_{1},\ldots,V_{m}$ of its vertex set into $m$ sets. If $n$ and $m$ have the same parity then the reduction returns the input as is. Otherwise, there exists some $j\in[m]$ for which the size of $V_{j}$ is even. In this case, the reduction adds to the cycle $G$ a new vertex located between two arbitrary consecutive vertices and puts it in $V_{j}$. Now, the number of vertices and the number of sets in the partition have the same parity, so the reduction can output the obtained cycle and partition.

We turn to prove the correctness of the reduction. If the given instance of Fair-IS-Cycle satisfies that $n$ and $m$ have the same parity, then its solution as an instance of Fair-Split-Cycle includes two disjoint independent sets that fairly represent the partition, and each of them forms a solution as an instance of Fair-IS-Cycle as well. So suppose that $n$ and $m$ have a different parity, and let $j\in[m]$ denote the index for which the reduction adds a vertex to $V_{j}$. Let $u$ denote the added vertex, and define $V^{\prime}_{i}=V_{i}$ for $i\in[m]\setminus\{j\}$ and $V^{\prime}_{j}=V_{j}\cup\{u\}$. Now, a solution to the constructed instance of Fair-Split-Cycle includes two disjoint independent sets that fairly represent the partition. Clearly, at least one of the sets does not include both neighbors of $u$. Letting $S^{\prime}$ denote such a set, it follows that the set $S=S^{\prime}\setminus\{u\}$ is independent in the original given cycle. For every $i\in[m]\setminus\{j\}$, it holds that $|S\cap V_{i}|=|S^{\prime}\cap V^{\prime}_{i}|\geq\frac{1}{2}\cdot|V^{\prime}_{i}|-1=\frac{1}{2}\cdot|V_{i}|-1$. It further holds that

Since $|V_{j}|$ is even, it follows that $|V^{\prime}_{j}|$ is odd, hence $|S\cap V_{j}|\geq\frac{1}{2}\cdot|V^{\prime}_{j}|-\frac{3}{2}=\frac{1}{2}\cdot|V_{j}|-1$. This implies that $S$ is a solution to the original instance of Fair-IS-Cycle, and we are done.

The Schrijver Problem

In this section we introduce and study the Schrijver problem, a natural analogue of the Kneser problem defined by Deng et al. .

In the Schrijver problem, the input consists of a Boolean circuit that represents a coloring

As mentioned earlier, it was proved by Schrijver that the chromatic number of $S(n,k)$ is precisely $n-2k+2$. Therefore, every input to the Schrijver problem has a solution.

The following theorem is used to obtain the hardness result for the Schrijver problem. The proof applies an argument of (see also ).

The Fair-IS-Cycle problem is polynomial-time reducible to the Schrijver problem.

2 Membership in 𝖯𝖯𝖠𝖯𝖯𝖠\mathsf{PPA}

We now show that the Schrijver and Fair-Split-Cycle problems lie in $\mathsf{PPA}$ by reductions to the search problem associated with the Octahedral Tucker lemma. The reductions follow the proofs of the corresponding mathematical statements by Meunier and by Alishahi and Meunier , and we describe them here essentially for completeness.

We start with some notation (following [16, Section 2]). The partial order $\preceq$ on the set $\{+,-,0\}$ is defined by $0\preceq+$ and by $0\preceq-$, where $+$ and $-$ are incomparable. The definition is extended to vectors, so that for two vectors $x,y$ in $\{+,-,0\}^{n}$, we have $x\preceq y$ if for all $i\in[n]$ it holds that $x_{i}\preceq y_{i}$ (equivalently, $x_{i}=y_{i}$ whenever $x_{i}\neq 0$). The Octahedral Tucker lemma, given implicitly in and explicitly in , says that for a function $\lambda:\{+,-,0\}^{n}\setminus\{0\}\rightarrow\{\pm 1,\ldots,\pm(n-1)\}$ satisfying $\lambda(-x)=-\lambda(x)$ for all $x$, there exist vectors $x,y$ such that $x\preceq y$ and $\lambda(x)=-\lambda(y)$. Note that this corresponds to the general Tucker’s lemma applied to (the boundary of) the barycentric subdivision of the $n$-cube whose vertex set can be identified with $\{+,-,0\}^{n}$ (see ). The lemma guarantees the existence of a solution to every input of the following search problem, denoted Octahedral-Tucker.

In the Octahedral-Tucker problem, the input consists of a Boolean circuit that represents a function $\lambda:\{+,-,0\}^{n}\setminus\{0\}\rightarrow\{\pm 1,\pm 2,\ldots,\pm(n-1)\}$ satisfying $\lambda(-x)=-\lambda(x)$ for all $x$. The goal is to find vectors $x,y$ such that $x\preceq y$ and $\lambda(x)=-\lambda(y)$.

The Octahedral-Tucker problem is known to be $\mathsf{PPA}$-complete , where its membership in $\mathsf{PPA}$ essentially follows already from (see also [19, Appendix A] and [2, Section 3]).

The Octahedral-Tucker problem lies in $\mathsf{PPA}$.

For a given vector $x\in\{+,-,0\}^{n}$, we let $A(x)$ denote the vector in $\{+,-,0\}^{n}$ defined as follows. Let $I=\{i\in[n]\mid x_{i}=0\}$. We first define $A(x)_{i}=0$ for every $i\in I$. Next, consider the restriction $x_{\overline{I}}$ of $x$ to the entries whose indices are in $\overline{I}=[n]\setminus I$, and notice that $x_{\overline{I}}$ can be viewed as a sequence of maximal blocks of $+$’s and of $-$’s. The restriction $A(x)_{\overline{I}}$ of $A(x)$ to the entries of $\overline{I}$ is defined as the vector obtained from $x_{\overline{I}}$ by replacing all the symbols to zeros but the first symbol of each block. For example, for the vector $x=(+,+,0,+,-,-,0,-,+,0)$ we have $x_{\overline{I}}=(+,+,+,-,-,-,+)$, hence $A(x)=(+,0,0,0,-,0,0,0,+,0)$.

We reduce the Schrijver problem to Octahedral-Tucker, applying an argument of .

The Schrijver problem is polynomial-time reducible to the Octahedral-Tucker problem.

We finally reduce the Fair-Split-Cycle problem (see Definition 1.4) to Octahedral-Tucker, applying an argument of .

The Fair-Split-Cycle problem is polynomial-time reducible to the Octahedral-Tucker problem.

Consider an instance of the Fair-Split-Cycle problem, that is, a cycle $G$ on the vertex set $[n]$ and a partition $V_{1},\ldots,V_{m}$ of $[n]$ into $m$ sets, such that $n$ and $m$ have the same parity. It can be assumed that $n>m$. We construct an instance of the Octahedral-Tucker problem given by the function $\lambda:\{+,-,0\}^{n}\setminus\{0\}\rightarrow\{\pm 1,\pm 2,\ldots,\pm(n-1)\}$ defined as follows. For a given vector $x\in\{+,-,0\}^{n}\setminus\{0\}$, set

$J(x)\neq\emptyset$. In this case, let $i$ be the largest element of $J(x)$. If $|x^{+}\cap V_{i}|=|x^{-}\cap V_{i}|=\tfrac{|V_{i}|}{2}$ then we define $\lambda(x)=+(i+n-m-1)$ in the case where the smallest element of $(x^{+}\cup x^{-})\cap V_{i}$ is in $x^{+}$ and $\lambda(x)=-(i+n-m-1)$ otherwise. If $\max(|x^{+}\cap V_{i}|,|x^{-}\cap V_{i}|)>\tfrac{|V_{i}|}{2}$ then we define $\lambda(x)=+(i+n-m-1)$ in the case where $|x^{+}\cap V_{i}|>\tfrac{|V_{i}|}{2}$ and $\lambda(x)=-(i+n-m-1)$ otherwise.

3 Putting It All Together

We finally show that the presented reductions complete the proofs of our results (see Figure 1). Indeed, the Fair-IS-Cycle problem is $\mathsf{PPA}$-hard by Theorem 2.7, and is polynomial-time reducible to the Schrijver problem by Theorem 3.2. By Theorem 3.5, the latter is efficiently reducible to the Octahedral-Tucker problem, which by Proposition 3.4 lies in $\mathsf{PPA}$. It thus follows that the Fair-IS-Cycle and Schrijver problems are $\mathsf{PPA}$-complete, as required for Theorems 1.3 and 1.7. In addition, by Theorem 2.8, there exists a constant $\varepsilon>0$ for which the $\varepsilon\textsf{-}\textsc{Fair-Split-Cycle}$ problem is $\mathsf{PPA}$-hard. The $\varepsilon\textsf{-}\textsc{Fair-Split-Cycle}$ problem lies in $\mathsf{PPA}$, even for $\varepsilon=0$, as follows by combining Theorem 3.6 with Proposition 3.4. This confirms Theorems 1.5 and 1.6.

Acknowledgements

We are grateful to Aris Filos-Ratsikas and Alexander Golovnev for helpful discussions and to the anonymous referees for their useful suggestions and comments.

References