An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange

Extensions of the standard kidney exchange problem have also been studied. In this work, we consider one such extension which we now motivate and introduce. It is known that the fraction of patients to receive a healthy kidney can increase significantly with an increase in the total number of participating pairs [2]. This motivates collaborations between multiple programs, from now on referred to as agents. Such collaborations, however, can be hindered by a mismatch between the individual interests of agents, as these need not align with the collective goal of helping as many patients as possible overall. In particular, a socially optimal solution – in which as many patients as possible are treated overall – is not guaranteed to help as many people from each individual agent as that agent could have achieved on their own. This may stop agents from participating in collaborative programs or, when they do participate, move them to withhold information from the collective.

Several ways of incorporating fairness into multi-agent KEPs have been studied [2, 3, 4, 8, 9, 15, 19]. Recently, Blom, Smeulders, and Spieksma [6] also introduced a framework to capture fairness via a game-theoretical concept of rejections. They translate this into an algorithmic task that asks for a solution that is not rejected by any agent. We study the resulting algorithmic task. To introduce it, we first define the concept of rejections.

Recall the original KE-$d$ problem on directed graphs. To encode multiple agents into the input, we partition the vertex set of the input graph over the agents. In the obtained graph, we refer to a cycle that only contains vertices from a single agent $i$ as an $i$-internal cycle. Like in the original KE-$d$ problem, a solution consists of a packing $𝒞$ of pairwise vertex-disjoint $d$-cycles. A given such packing $𝒞$ will be rejected by an agent under the conditions listed in the definition below. See also Figure 1 for an example, adapted from a figure by Blom et al.

This definition captures that the rejecting agent $i$ could modify a given cycle packing $𝒞$ into another packing ${𝒞}^{\prime }$ that benefits more of their own patients by only making changes pertaining to patients within their control. We call a packing that is not rejected by any agent rejection-proof. Then, a guarantee to always find such a solution also serves as a guarantee for agents that participation in the joint program is never detrimental to their personal interests. This led Blom et al. [6] to introduce the following problem, whose parameterized complexity we investigate in this work.

Rejection-Proof Kidney Exchange with $d$-cycles (RPKE-$d$) Input: A directed graph $G$ where $V(G)=V_1\cup \mathrm{\dots }\cup V_p$ is partitioned among $p$ agents, and an integer $k$. Task: Determine whether there is a rejection-proof set $𝒞$ of pairwise vertex-disjoint $d$-cycles such that $𝒞$ covers at least $k$ vertices.

For ease of notation, we refer to any packing of pairwise vertex-disjoint $d$-cycles that covers at least $k$ vertices in an RPKE-$d$ instance as a candidate solution. Hence, a packing of $d$-cycles forms a solution to an instance if it is both a candidate solution and rejection-proof.

The above problem takes a leap in complexity compared to the single-agent problem KE-$d$. Whereas KE-$d$ is known to be NP-complete for all finite $d\ge 3$ [1], Blom et al. have shown RPKE-$d$ to be ${\mathrm{\Sigma }}_2^P$-complete for $d\ge 3$, even when there are only two participating agents [6, Theorem 1]. In fact, it can be shown that checking whether a given agent rejects a given candidate solution is already NP-hard since this is at least as hard as checking whether a given packing is optimal in the NP-hard setting of only one agent. Partly motivated by this observation, we also consider a more restricted definition of rejections.

For some integer $c\ge 0$, we say that an agent $c$-rejects a packing $𝒞$ if the rejection criterion from Definition 1.1 can be satisfied with $|{𝒞}_{\mathrm{rej}}|\le c$. We call a packing that no agent $c$-rejects $c$-rejection-proof. Now, for each pair of positive integers $c$ and $d$ we define the problem $c$-Rejection-Proof Kidney Exchange with $d$-cycles ($c$-RPKE-$d$) as the variant of the above RPKE-$d$ problem in which we aim to determine whether the input contains a candidate solution that is $c$-rejection-proof.

The integer $c$ in this definition indicates some level of complexity that a rejection can have. Additionally, it provides a way to interpolate between the problems KE-$d$ ($c=0$) and RPKE-$d$ ($c=\mathrm{\infty }$). More importantly, for any constant $c$, we observe that the task of determining whether a given agent $c$-rejects a given packing $𝒞$ of $d$-cycles is polynomial-time solvable when $d$ is also constant. This is witnessed by the fact that, if an agent $c$-rejects the packing $𝒞$, an alternative packing can always be obtained by rejecting a constant number of cycles and including a constant number of internal cycles. It follows that $c$-RPKE-$d$ is contained in NP when $c$ and $d$ are constants, as opposed to the ${\mathrm{\Sigma }}_2^P$-complete RPKE-$d$ problem that does not limit the number of cycles that agents are allowed to reject.

We study the complexity of RPKE-$d$ and $c$-RPKE-$d$ parameterized by $k$, the number of vertices to be covered, and we present both positive and negative results. We prove our positive results on related set packing problems that generalize the two graph problems. This allows us to use some of the tools developed for such problems. Prior to our work, the only positive result known for RPKE-$d$ was a polynomial-time algorithm for $d=2$ [8].

We give an algorithm that, for constant values of $d$, solves RPKE-$d$ in $2^{𝒪(k\log k)}+n^{𝒪(1)}$ time on $n$-vertex graphs. It consists of two parts, the first of which is a kernelization algorithm. It takes an arbitrary instance as input and outputs an equivalent instance of size $𝒪\left({(k^{d+1})}^d\right)$ in polynomial time, via a careful agent-aware application of the sunflower lemma [12] to eliminate transplantation cycles. In set packing problems, removing sets during preprocessing typically comes at the risk of removing sets that are required to make an optimal solution, thereby possibly transforming YES-instances into NO-instances. The sunflower lemma provides a tool to circumvent this. Our rejection-proof problem settings introduce an additional type of behavior that needs care: transplantation cycles that do not belong to optimal solutions may still play a role in rejections. Removing the wrong cycles may cause an agent not to reject a certain candidate solution that it otherwise would have. We present a two-step reduction approach guaranteed to preserve the answer. The second part of the algorithm consists of brute-force on the reduced instance.

We give a reduction from Subgraph Isomorphism to show that, under the Exponential Time Hypothesis (ETH), the algorithm is asymptotically optimal in terms of $n$ and $k$. We even show the stronger bound (independent of $k$) that a $2^{o(n\log n)}$ time algorithm for RPKE-$d$ or $c$-RPKE-$d$ would violate the ETH for any $c\ge 2$ and $d\ge 3$. We exploit the mechanism of rejections to facilitate our reduction from the Subgraph Isomorphism problem, for which such a superexponential ETH-based lower bound is known [10]. This gives the rejection-proof kidney exchange problems a similar complexity status to other problems in the literature, such as Metric Dimension and Geodetic Set parameterized by vertex cover number, for which a brute-force algorithm on a polynomial kernel is also ETH-optimal [14].

To complement the ETH-hardness of $c$-RPKE-$d$ with $c\ge 2$, we give a $3^n\cdot n^{𝒪(1)}$ time algorithm for the problem when $c=1$. This allows us to see surprising jumps in the algorithmic complexity of $c$-RPKE-$d$ for varying values of $c$. While no big difference in complexity is obtained between $c=1$ and $c=0$ (in which case the problem can be solved in $2^n\cdot n^{𝒪(1)}$ time with a standard application of dynamic programming over subsets [10, Chapter 6]), our results show that the problem does become computationally harder from a parameterized perspective when $c=2$ (assuming the ETH). We also see that no more jumps in parameterized complexity appear for larger values of $c$. The surprising aspect here is that this one discrete jump in the parameterized complexity of $c$-RPKE-$d$ does not coincide with the jump in the classical complexity of the problem between being contained in NP vs. not being contained in NP: we have seen that, for constant $d\ge 3$, the $c$-RPKE-$d$ problem is contained in NP for every constant value of $c$, while the RPKE-$d$ problem is ${\mathrm{\Sigma }}_2^P$-complete.

Another jump in complexity is observed when looking at the number of vertices that are not covered by a solution. When asked to find a solution that covers all vertices in the input, the problem again collapses to the NP-complete packing problem KE-$d$. However, our ETH-hardness proof shows that finding a solution that covers all but one vertex is essentially as difficult as the general problem in terms of running time, assuming the ETH. Combined, our results yield a good understanding of what makes rejection-proof kidney exchange hard.

The remainder of this work is organized as follows. We start with some preliminaries in Section 2. Next, we give a polynomial kernel and an FPT algorithm for a set packing generalization of RPKE-$d$ in Section 3, and we present a matching ETH-lower bound in Section 4. In Section 5, we give a single-exponential algorithm under $1$-rejections and we conclude in Section 6. The proofs of statements marked $(\mathrm{★})$ are deferred to the full version of this paper.

As mentioned, we present our positive results for problems that generalize the kidney exchange problems defined in the introduction. Intuitively, one may think of translating an RPKE-$d$ instance on a graph $G$ into this generalized setting by constructing a set system $(U,𝒮)$ with $U=V(G)$ and including a set in $𝒮$ for every vertex set that forms a $d$-cycle in $G$. Related definitions follow analogously, but we briefly reiterate and name them below. To represent $p$ different agents in a set system $(U,𝒮)$, the universe $U=U_1\cup \mathrm{\dots }\cup U_p$ is partitioned into $p$ sets. A set $S\in 𝒮$ is called $i$-internal if $S\subseteq U_i$.

We call a packing that is not rejected by any agent rejection-proof, and we use this notation to introduce the following generalized problem statement.

Rejection-Proof $d$-Set Packing (RP-$d$-SP) Input: A universe $U=U_1\cup \mathrm{\dots }\cup U_p$ that is partitioned over $p$ agents, a collection $𝒮\subseteq 2^U$ of sets of size $\le d$, and an integer $k$. Task: Determine whether there is a rejection-proof collection $𝒳\subseteq 𝒮$ of disjoint sets that covers at least $k$ elements from $U$.

Like in the graph setting, we call any packing of pairwise disjoint sets that cover at least $k$ vertices a candidate solution. Further, for some integer $c\ge 0$, we say that an agent $c$-rejects a given packing $𝒳$ if the rejection criterion from Definition 2.4 can be satisfied with $|{𝒳}_{\mathrm{rej}}|\le c$. A packing that no agent $c$-rejects is called $c$-rejection-proof. We define $c$-Rejection-Proof $d$-Set Packing ($c$-RP-$d$-SP) as a problem with the same input as RP-$d$-SP, but in which the goal is to determine whether the input contains a $c$-rejection-proof candidate solution.

In Section 4, we derive a hardness result that is conditional on the well-known ETH. This is a technical conjecture implying that the satisfiability of Boolean $3$-CNF formulas cannot be checked in subexponential time [17]. Specifically, we use a known hardness result for the Subgraph Isomorphism problem conditional on the ETH. This problem takes two undirected graphs $G$ and $H$ as input and asks whether $H$ is isomorphic to a subgraph of $G$. More formally, the problem asks whether there is an injective function $\phi :V(H)\to V(G)$ such that $\{u,v\}\in E(H)$ implies $\{\phi (u),\phi (v)\}\in E(G)$. Such a function is called a subgraph isomorphism from $H$ to $G$. The following conditional lower bound on the computational complexity of this problem is known.

Clearly, $𝒳$ is also a candidate solution in $I_2$. Now, suppose for contradiction that some agent $i$ rejects $𝒳$ by proposing an alternative packing $(𝒳\setminus {𝒳}_{\mathrm{rej}})\cup {𝒳}_{\mathrm{int}}$. This alternative packing can also be constructed in $I_1$, contradicting that $𝒳$ is rejection-proof in $I_1$. $◀$

The above observation captures that an agent $i$ cannot gain anything by rejecting a set that is not intersected by an $i$-internal set. Thus, we can assume they will not reject such sets. $𝒳$ and ${𝒳}^{\prime }$ become identical after removing these sets, so the observation is correct.

Now, we present two reduction rules that act on an input instance $(U_1,\mathrm{\dots },U_p,𝒮,k)$ of RP-$d$-SP and prove that they are safe. A reduction rule is safe if its application preserves the YES/NO answer to the decision problem. The first rule aims to reduce the number of internal sets.

Let $I=(U_1,\mathrm{\dots },U_p,𝒮,k)$ be an instance of RP-$d$-SP where there exists some $i\in [p]$ and sunflower $ℱ\subseteq 𝒮[U_i]$ of size $d(k\cdot d-1)+2$ with core $Y$. Let $S$ be the set of minimum size in $ℱ$ that is removed by Reduction rule 1 to create the instance $I^{\prime }=(U_1,\mathrm{\dots },U_p,𝒮\setminus \{S\},k)$. We will now argue that $I$ is a YES-instance if and only if $I^{\prime }$ is a YES-instance.

Assume $I$ has a solution $𝒳$. We claim there is a solution for $I$ that does not use $S$. If $S\notin 𝒳$, our claim holds. Suppose $S\in 𝒳$. Invoking Lemma 2.3 with $h=k\cdot d$ yields that a $S^{\prime }\in ℱ$ exists such that the sets in ${𝒳}^{\prime }=(𝒳\setminus \{S\})\cup \{S^{\prime }\}$ are pairwise disjoint. Since $S$ is a minimum-size set in $ℱ$, it follows that $|S^{\prime }|\ge |S|$, so the collection ${𝒳}^{\prime }$ covers at least $k$ elements. To show that ${𝒳}^{\prime }$ is rejection-proof, suppose for contradiction that some agent $j$ rejects ${𝒳}^{\prime }$ by proposing the alternate packing $({𝒳}^{\prime }\setminus {𝒳}_{\mathrm{rej}}^{\prime })\cup {𝒳}_{\mathrm{int}}^{\prime }$. We distinguish three cases:

• $\mathrm{■}$

  $j\ne i$. Since $S\in 𝒮[U_i]$, each set $J\in 𝒮$ with $J\cap U_j\ne \mathrm{\varnothing }$ is contained in ${𝒳}^{\prime }$ if and only if it is contained in $𝒳$. From Observation 3.2 it follows that agent $j$ would reject $𝒳$.

• $\mathrm{■}$

  $j=i$ and $S^{\prime }\in {𝒳}_{\mathrm{rej}}^{\prime }$. Let ${𝒳}_{\mathrm{rej}}=({𝒳}_{\mathrm{rej}}^{\prime }\setminus \{S^{\prime }\})\cup \{S\}$ and note that ${𝒳}^{\prime }\setminus {𝒳}_{\mathrm{rej}}^{\prime }=𝒳\setminus {𝒳}_{\mathrm{rej}}$. By the definition of rejection $(𝒳\setminus {𝒳}_{\mathrm{rej}})\cup {𝒳}_{\mathrm{int}}^{\prime }$ is a collection of disjoint sets. Both $S$ and $S^{\prime }$ are $j$-internal and $|S|\le |S^{\prime }|$, hence $𝒳$ covers at most as many elements of $U_j$ as ${𝒳}^{\prime }$ does. By definition of rejection, $({𝒳}^{\prime }\setminus {𝒳}_{\mathrm{rej}}^{\prime })\cup {𝒳}_{\mathrm{int}}^{\prime }=(𝒳\setminus {𝒳}_{\mathrm{rej}})\cup {𝒳}_{\mathrm{int}}^{\prime }$ covers more elements from $U_j$ than ${𝒳}^{\prime }$ does, thus also more than $𝒳$ covers. This would mean that $𝒳$ would be rejected by agent $j$ by rejecting the sets ${𝒳}_{\mathrm{rej}}\subseteq 𝒳$ and replacing these with the sets ${𝒳}_{\mathrm{int}}^{\prime }$.

• $\mathrm{■}$

  $j=i$ and $S^{\prime }\notin {𝒳}_{\mathrm{rej}}^{\prime }$. Let ${𝒳}_{\mathrm{rej}}={𝒳}_{\mathrm{rej}}^{\prime }\cup \{S\}$ and ${𝒳}_{\mathrm{int}}={𝒳}_{\mathrm{int}}^{\prime }\cup \{S^{\prime }\}$. Observe that ${𝒳}_{\mathrm{int}}\subseteq 𝒮[U_j]$ and $(𝒳\setminus {𝒳}_{\mathrm{rej}})\cup {𝒳}_{\mathrm{int}}=({𝒳}^{\prime }\setminus {𝒳}_{\mathrm{rej}}^{\prime })\cup {𝒳}_{\mathrm{int}}^{\prime }$. Hence agent $j$ would reject $𝒳$.

As all cases contradict the assumption that $𝒳$ is rejection-proof, ${𝒳}^{\prime }$ is a solution for $I$ that does not contain $S$. Now Lemma 3.1 implies that $I^{\prime }$ has a solution and is a YES-instance.

Assume $I^{\prime }$ has a solution ${𝒳}^{\prime }$. We claim that ${𝒳}^{\prime }$ is also a solution for the instance $I$. It suffices to show that no rejection can take place where $S\in {𝒳}_{\mathrm{int}}$, as the other requirements for ${𝒳}^{\prime }$ to be a solution for $I$ follow directly from ${𝒳}^{\prime }$ being a solution for $I^{\prime }$.

Assume, for sake of contradiction, that agent $i$ rejects ${𝒳}^{\prime }$ by rejecting ${𝒳}_{\mathrm{rej}}$ and replacing these sets with ${𝒳}_{\mathrm{int}}$, where $S\in {𝒳}_{\mathrm{int}}$. Because $({𝒳}^{\prime }\setminus {𝒳}_{\mathrm{rej}})\cap {𝒳}_{\mathrm{int}}$ is a collection of disjoint sets and $S\in ℱ$ it follows from Lemma 2.3 with $h=k\cdot d$ that there exists some set $S^{\prime }\in ℱ$ such that $((({𝒳}^{\prime }\setminus {𝒳}_{\mathrm{rej}})\cap {𝒳}_{\mathrm{int}})\setminus \{S\})\cup \{S^{\prime }\}$ is a collection of disjoint sets. Note that $|S^{\prime }|\ge |S|$ and $S,S^{\prime }\in 𝒮[U_i]$. Hence agent $i$ can also reject ${𝒳}^{\prime }$ as a solution for $I$ by rejecting ${𝒳}_{\mathrm{rej}}$ and replacing these sets with $({𝒳}_{\mathrm{int}}\setminus \{S\})\cup \{S^{\prime }\}$. Similarly, agent $i$ can reject ${𝒳}^{\prime }$ as a solution for $I^{\prime }$; a contradiction. Hence ${𝒳}^{\prime }$ is a solution for $I$, which means $I$ is a YES-instance. $◀$

Observe that in the forward direction of the proof we increase the number of sets that are rejected by some agent $j$. This is possible because an agent can reject an unbounded number of sets in RPKE-$d$. The proof as written does not work in the setting of $c$-RPKE-$d$. Our second reduction rule aims to reduce the number of sets that are not internal.

The proof of the lemma follows the same structure as the proof of Lemma 3.3. The restrictions placed on the sunflower used in Reduction rule 2 together with Lemma 3.1 can be used to prove one direction of the proof. The other direction follows from the fact that any removed set is not internal and can thus not be used as a replacement set in a rejection.

To bound the kernel size we define $f_d(k)=d\cdot d!{(d(k\cdot d-1)+1)}^d$ and $g_d(k)=d\cdot d!{\left(d^{d-1}\cdot (d(k\cdot d-1)+1)+d\cdot k\cdot f_d(k)\right)}^d$. Note that $g_d(k)=𝒪\left({\left(k^{d+1}\right)}^d\right)$ for fixed $d$.

It can easily be shown that an instance in which at least $k$ agents have an internal set is a YES-instance. Else, if the instance contains at least $k\cdot f_d(k)$ internal sets, we can use Lemma 2.2 to show that Reduction rule 1 can be applied in polynomial time. Otherwise, the number of internal sets is bounded, and we show that Reduction rule 2 can be applied. In that case, the number of petals in a sunflower that are intersected by internal sets is also bounded and the core of a sunflower is intersected by internal sets from at most $d$ agents. Since $|𝒮|\ge g_d(k)$, Lemma 2.2 yields a sufficiently large sunflower such that some of its sets have the same number of elements from each agent with an internal set intersecting the core. Some subset of this is a sunflower meeting the prerequisites from Reduction rule 2 and this can be found in polynomial time. $◀$

Now, the above insights can be used to give the kernel. Given an RP-$d$-SP instance $I$, it starts by greedily computing an inclusion-wise maximal packing $𝒳$ of disjoint sets. In the full version, we show that $I$ is a YES-instance if $|𝒳|>k$. Otherwise, the union of all sets in $𝒳$ forms a hitting set of size $\le k\cdot d$, meaning that Reduction rules 1 and 2 are safe to apply. Lemma 3.5 shows that at least one of them is applicable if $|𝒳|\ge g_d(k)$ and we repeatedly apply one until an instance is obtained with at most $g_d(k)$ sets. This proves the following.

This kernel can be used as a subroutine to solve RP-$d$-SP. Since it outputs an equivalent instance with a bounded hitting set, the number of collections of pairwise disjoint sets is also bounded. This limits the number of candidate solutions and alternative packings that a brute-force algorithm needs to consider, and it allows us to prove the following statement.

Let $c\ge 2$ be arbitrary. We prove the statement by a reduction from Subgraph Isomorphism. The resulting instance can serve as an input to both RPKE-$3$ and $c$-RPKE-$3$. First, we give the reduction after which we prove it is correct for both problems. A visual example of the reduction can be seen in Figure 2.

Let $(G,H)$ be an input for the Subgraph Isomorphism problem consisting of two graphs and let $n_G:=|V(G)|$ and $n_H:=|V(H)|$. We assume that $n_H\le n_G$, as $(G,H)$ would trivially be a NO-instance otherwise. Now, we give our reduction by showing how to modify the input $(G,H)$ to an input $(G^{\prime },V_1^{\prime },V_2^{\prime },k)$ with two agents for RPKE-$3$ and $c$-RPKE-$3$.

We start by defining the vertex set of $G^{\prime }$. To define the complete vertex set, it is useful to think of it as six separate parts: five sets $W_1,W_2,W_3,W_4$, and $W_5$, and a separate vertex $z$. First, for every vertex $u\in V(H)$, we add a vertex $u_1$ to $W_1$ and a vertex $u_2$ to $W_2$. Next, for every vertex $x\in V(G)$, we add a vertex $x_3$ to $W_3$. Then, for every integer $i\in [n_G-n_H]$ we add a vertex $i_4$ to $W_4$ and a vertex $i_5$ to $W_5$. Finally, we add the additional vertex $z$ to the graph. The vertex set is partitioned over the two agents by defining $V_1^{\prime }:=W_1\cup W_3\cup W_5\cup \{z\}$ and $V_2^{\prime }:=W_2\cup W_4$. Remark that $|W_1\cup W_4|=|W_2\cup W_5|=|W_3|=n_G$, so that $|V(G^{\prime })|=3n_G+1$.

Next, we define the edge set of $G^{\prime }$. Although $G$ and $H$ are undirected graphs, recall that $G^{\prime }$, being part of a kidney exchange instance, is a directed graph.

1. 1.

   For every $\{u,v\}\in E(H)$, we add $(u_1,v_1)$ and $(v_1,u_1)$ to $E(G^{\prime })$.

2. 2.

   For every $u\in V(H)$, we add $(u_1,u_2)$ to $E(G^{\prime })$.

3. 3.

   For every $u\in V(H)$ and every $x\in V(G)$, we add $(u_2,x_3)$ and $(x_3,u_1)$ to $E(G^{\prime })$.

4. 4.

   For every $i\in [n_G-n_H]$, we add $(i_4,i_5)$ to $E(G^{\prime })$.

5. 5.

   For every $x\in V(G)$ and every $i\in [n_G-n_H]$, we add $(x_3,i_4)$ and $(i_5,x_3)$ to $E(G^{\prime })$.

6. 6.

   For every $x\in V(G)$, we add $(x_3,z)$ and $(z,x_3)$ to $E(G^{\prime })$.

7. 7.

   We fix an arbitrary ordering $\prec$ on $V(G)$. Then, for every $x,y\in V(G)$ such that $\{x,y\}\notin E(G)$ and $x\prec y$, we add $(x_3,y_3)$ to $E(G^{\prime })$.

Finally, we define $k=3\cdot n_G$. Note that this is one less than the total number of vertices in $G^{\prime }$, denoted as $n:=|V(G^{\prime })|=3n_G+1$. This concludes the description of the reduction.

We distinguish six different classes of $3$-cycles that live in $G^{\prime }$. Below, we describe for each of these classes what their intuitive role is in the reduction and we indicate each class of cycles with a letter to refer to them more easily later in the proof. See also Figure 2.

• $\mathrm{■}$

  For every edge $\{u,v\}\in E(H)$, the graph $G^{\prime }$ contains the cycle $⟨u_1,v_1⟩$. We call such cycles A-cycles for encoding the adjacencies in $H$.

• $\mathrm{■}$

  For every triangle in $H$ on vertices $u$, $v$, and $w$, the graph $G^{\prime }$ contains both orientations of the directed cycle on vertices $u_1$, $v_1$ and $w_1$. We call such cycles T-cycles due to their correspondence to triangles in the graph $H$. These cycles originate merely as a byproduct of constructing the A-cycles and serve no explicit purpose in our reduction.

• $\mathrm{■}$

  For every $u\in V(H)$ and every $x\in V(G)$, the graph $G^{\prime }$ contains the cycle $⟨u_1,u_2,x_3⟩$. We call such cycles I-cycles, as they are used to encode subgraph isomorphisms from $H$ to $G$: including a cycle $⟨u_1,u_2,x_3⟩$ will correspond to mapping $u\in V(H)$ to $x\in V(G)$ in a subgraph isomorphism. See also Figure 3 (left image) for an example.

• $\mathrm{■}$

  For every $x\in V(G)$ and every $i\in [n_G-n_H]$, the graph $G^{\prime }$ contains the cycle $⟨x_3,i_4,i_5⟩$. We call such cycles F-cycles as they are used in the construction of optimal solutions as filler cycles to cover vertices in $W_3$ that are not already covered by I-cycles.

• $\mathrm{■}$

  For every $x,y\in V(G)$ with $\{x,y\}\notin E(G)$, the graph $G^{\prime }$ contains the cycle $⟨x_3,y_3,z⟩$ (or $⟨y_3,x_3,z⟩$ depending on whether $x\prec y$). We call such cycles N-cycles for encoding the non-adjacencies in $G$.

• $\mathrm{■}$

  Finally, for every $x\in V(G)$, the graph $G^{\prime }$ contains the cycle $⟨x_3,z⟩$. Much like T-cycles, these cycles serve no explicit purpose in our reduction and they originate merely as byproduct of constructing the N-cycles. We call them R-cycles, since optimal rejection-proof solutions typically do not include any of them, making these cycles mostly redundant.

Before proving the correctness of our reduction, observe that $G^{\prime }$ does not contain any $3$-cycles other than those contained in the six classes described above. In particular, note that $G^{\prime }[W_3]$ is a DAG as the obvious extension of $\prec$ to $W_3$ forms a topological ordering. Finally, cycles whose length is greater than $3$ will not be relevant in our proof, since RPKE-$3$ and $c$-RPKE-$3$ only deal with $3$-cycles by definition.

Most of the remainder of this proof is used to show the correctness of the reduction. We do this by proving that $H$ is isomorphic to a subgraph of $G$ if and only if $G^{\prime }$ has a ($c$-)rejection-proof packing of $3$-cycles that covers at least $k$ vertices. Below, we prove the two directions of this bi-implication separately.

Let $𝒞$ be a $2$-rejection-proof packing of $3$-cycles in $G^{\prime }$ that covers at least $k=3\cdot n_G$ vertices. Before showing how to construct from $𝒞$ a subgraph isomorphism from $H$ to $G$, we derive some structural properties of $𝒞$. We start by observing that at most one vertex from $G^{\prime }$ is not covered by $𝒞$. We use this property to show that $𝒞$ must contain $n_H$ I-cycles.

First, we argue that the number of I-cycles in $𝒞$ must be more than $n_H-2$. Since vertices from $W_2$ only appear in I-cycles and each I-cycle contains exactly one of these vertices, at least two vertices from $W_2$ would be uncovered by $𝒞$ otherwise. This would contradict the assumption that $𝒞$ leaves at most one vertex uncovered.

Next, we argue that the number of I-cycles in $𝒞$ cannot be exactly $n_H-1$. In that case exactly one vertex $u_1$ from $W_1$ and exactly one vertex $v_2$ from $W_2$ would not be covered by an I-cycle in $𝒞$. If $v_2$ is not covered by an I-cycle in $𝒞$, this means that it is not covered at all by $𝒞$. Furthermore, $u_1$ only appears in I-cycles, A-cycles, and T-cycles. By assumption, it is not covered by an I-cycle in $𝒞$. Moreover, it cannot be covered by an A-cycle or T-cycle in $𝒞$ either: such cycles contain at least two vertices from $W_1$, but $u_1$ is the only vertex in $W_1$ that is not covered by an I-cycle in $𝒞$. As such, $𝒞$ does not contain A-cycles or T-cycles since these would not be vertex-disjoint from all I-cycles in $𝒞$. This means that neither $v_2$ nor $u_1$ is covered by $𝒞$, contradicting that $𝒞$ leaves at most one vertex uncovered.

By arguing that the number of I-cycles in $𝒞$ must be strictly more than $n_H-2$ but not exactly $n_H-1$, we have shown that the number of I-cycles in $𝒞$ is exactly $n_H$. This means that all vertices from $W_1$ and $W_2$ are covered by I-cycles in $𝒞$.

Next, we see that $𝒞$ must include $n_G-n_H$ F-cycles. If it were to contain less F-cycles, at least one vertex from $W_4$ and $W_5$ each would not be covered by F-cycles. Since vertices from these two sets appear only in F-cycles, this would mean that they are not covered by $𝒞$ at all. In turn, this would contradict the observation that leaves $𝒞$ at most one vertex uncovered.

By including $n_H$ I-cycles and $(n_G-n_H)$ F-cycles, all vertices of $G^{\prime }$ except $z$ are covered. Since every cycle contains a vertex different from $z$, the packing $𝒞$ does not contain any other cycles. Knowing the structure of $𝒞$ allows us to construct a subgraph isomorphism $\phi :V(H)\to V(G)$.

Let $u\in V(H)$ be arbitrary, and let $C_u\in 𝒞$ be the unique I-cycle from $𝒞$ that contains $u_1$. Since every vertex from $W_1$ is contained in exactly one I-cycle in $𝒞$, this is well-defined. Let $x_3\in W_3$ be the unique vertex from $W_3$ in $C_u$. Then, we define $\phi (u)=x$. To complete the construction of $\phi$, we do the same for every $u\in V(H)$.

This construction yields a function $\phi$ that maps every vertex in $H$ to a unique vertex in $G$. To show that $\phi$ is in particular a subgraph isomorphism, it remains to show that for every $\{u,v\}\in E(H)$ it holds that $\{\phi (u),\phi (v)\}\in E(G)$. Suppose for contradiction that there is some $\{u,v\}\in E(H)$ for which this is not the case, i.e. $\{\phi (u),\phi (v)\}\notin E(G)$. We show that agent $1$ would then reject $𝒞$. The right image in Figure 3 shows an example of this situation.

Let $x=\phi (u)$ and $y=\phi (v)$. Assume w.l.o.g. that $x\prec y$ in the arbitrary ordering fixed onto $V(G)$ in step 7 of the construction of $E(G^{\prime })$. Then the following cycles exist:

• $\mathrm{■}$

  Because $\{u,v\}\in E(H)$, the A-cycle $⟨u_1,v_1⟩$ is added to $G^{\prime }$ in construction step 1.

• $\mathrm{■}$

  Because $\{x,y\}\notin E(G)$, the N-cycle $⟨x_3,y_3,z⟩$ is added to $G^{\prime }$ in steps 6 and 7.

Now, agent $1$ can reject the solution by proposing an alternative packing to $𝒞$ in which $⟨u_1,u_2,x_3⟩$ and $⟨v_1,v_2,y_3⟩$ are removed and the cycles $⟨u_1,v_1⟩$ and $⟨x_3,y_3,z⟩$ are added.

This modification to $𝒞$ yields a packing of cycles that are still pairwise disjoint and which cover all vertices of $V_1^{\prime }$. Moreover, the two cycles added by agent $1$ are indeed $1$-internal cycles in the graph, which means that agent $1$ will indeed reject $𝒞$ whenever there is a $\{u,v\}\in E(H)$ such that $\{\phi (u),\phi (v)\}\notin E(G)$. This contradicts the assumption that $𝒞$ is 2-rejection-proof, so we conclude that $\phi$ is a valid subgraph isomorphism from $H$ to $G$. $\mathrm{⊲}$

Let $\phi :V(H)\to V(G)$ be a subgraph isomorphism from $H$ to $G$. To encode this isomorphism as a packing of $3$-cycles, we include the I-cycle $⟨u_1,u_2,x_3⟩$ for every $u\in V(H)$ and $x\in V(G)$ such that $x=\phi (u)$. We extend this to a packing $𝒞$ that covers $k$ vertices by adding arbitrary but disjoint F-cycles that cover the $n_G-n_H$ vertices from $W_3$ that are not contained in any of the added I-cycles. It remains to show that this packing is rejection-proof.

As $𝒞$ leaves only the vertex $z$ uncovered, which belongs to $V_1^{\prime }$, only agent $1$ can reject and must do so by constructing an alternative packing that covers all vertices of $V_1^{\prime }$. In particular, they must propose to add some internal cycle $C_z$ that includes $z$. By construction of $G^{\prime }$, this cycle is either an R-cycle or an N-cycle and we can show with a case distinction that neither of those two options extends to a valid rejection for agent $1$. $\mathrm{⊲}$

Finally, we argue that Claims 4.2 and 4.3 combine to prove the original lemma statement. Together, they prove the correctness of the reduction from Subgraph Isomorphism to both RPKE-$3$ and $c$-RPKE-$3$. Moreover, the reduction can be executed in polynomial time. Hence, if an algorithm were to exist that solves either RPKE-$3$ or $c$-RPKE-$3$ in $2^{o(n\log n)}$ time, this algorithm could be used to determine in $2^{o(n\log n)}=2^{o(n_G\log n_G)}$ time whether $H$ is isomorphic to a subgraph of $G$. By Lemma 2.5, this is not possible assuming the ETH. $◀$

For completeness, we remark without proof that the construction above can be modified to prove that for any $d\ge 3$ and $c\ge 3$, an algorithm that solves $c$-RPKE-$d$ in time $2^{o(n\log n)}$ would violate the ETH.

The main idea for solving an instance $I=(U_1,\mathrm{\dots },U_p,𝒮,k)$ of $1$-RP-$d$-SP is as follows. Let $U:={\bigcup }_{i\in [p]}{U}_i$ be the complete universe. The algorithm iterates over all subsets $U^{\prime }\subseteq U$ of size at least $k$, each of which could be the set of elements covered by a solution to $I$. It then tries to find a solution covering exactly $U^{\prime }$. The main insight now is the following: whether or not a set $A\in 𝒮[U^{\prime }]$ leads to a $1$-rejection by agent $i$ in a solution that covers exactly $U^{\prime }$, is uniquely determined by the combination of $U^{\prime }$ and $A$. It is independent of the identities of the other sets used in the solution. Agent $i$ performs a $1$-rejection for $A$ if and only if there is a collection of pairwise disjoint $i$-internal sets avoiding $U^{\prime }\setminus A$ that covers more elements from $U_i$ than $A$ does. For each choice of $U^{\prime }$ we can therefore compute a collection ${𝒮}^{\prime }$ of sets that are feasible to be used in a $1$-rejection-proof solution covering exactly $U^{\prime }$. Testing whether there is a $1$-rejection-proof solution covering exactly $U^{\prime }$ then turns into an instance of Exact Set Cover over a universe of size $|U^{\prime }|\le |U|$, which can be solved efficiently via Lemma 2.1. The exact running time follows from some small optimizations and the binomial theorem. $◀$