14:10 Exploring the Kernelization Borders for Hitting Cycles

In the following, we state an easy observation, which follows from non-applicability of Reduction Rule 1 to 4.

**Observation 11.** Let $(G, H, R, k)$ be an instance of $\mathcal{D}_d$-DCF-FVS, where none of Reduction Rule 1 to 4 apply. Then the degree of each vertex in $G$ is bounded by $\mathcal{O}(k^2)$.

**Proof.** As Reduction Rule 3 is not applicable, then there is no $k+1$-flower in $G$. Now, if there is $v \in V(G)$ with degree at least $4k + (k+2)2k$, then Reduction Rule 4 would be applicable. ◀

To design our next reduction rule, we construct an auxiliary graph $G^*$. Intuitively speaking, $G^*$ is obtained from $G$ by shortcutting all degree two vertices. That is, vertex set of $G^*$ comprises of all the vertices of degree at least three in 3. From now on, vertices of degree at least 3 (in $G$) will be referred to as high degree vertices. For each $uv \in E(G)$, where $u, v$ are high degree vertices, we add the edge $uv$ in $G^*$. Furthermore, for an induced maximal path $P_{uv}$, between $u$ and $v$ where all the internal vertices of $P_{uv}$ are degree two vertices in $G$, we add the (multi) edge $uv$ to $E(G^*)$. Next, we will use the following result to bound the number of vertices and edges in $G^*$.

**Proposition 12.** [8] A graph $G$ with minimum degree at least 3, maximum degree $\Delta$, and a feedback vertex set of size at most $k$ has at most $(\Delta + 1)k$ vertices and $2\Delta k$ edges.

The above result (together with the construction of $G^*$) gives us the following (safe) reduction rule.

**Reduction Rule 5.** If $|V(G^*)| \ge 4k^2 + 2k^2(k+2)$ or $|E(G^*)| \ge 8k^2 + 4k^2(k+2)$, then return NO.

**Lemma 13.** Let $(G, H, R, k)$ be an instance of $\mathcal{D}_d$-DCF-FVS, where none of the Reduction Rules 1 to 5 are applicable. Then we obtain the following bounds:

- The number of vertices of degree at least 3 in $G$ is bounded by $\mathcal{O}(k^3)$.

- The number of maximal degree two induced paths in $G$ is bounded by $\mathcal{O}(k^3)$.

Having shown the above bounds, it remains to bound the number of degree two vertices in $G$. We start by applying the following simple reduction rule to eliminate vertices of degree two in $G$, which are also in $R$.

**Reduction Rule 6.** Let $v \in R$, $d_G(v) = 2$, and $x, y$ be the neighbors of $v$ in $G$. Delete $v$ from the graphs $G, H$ and the set $R$. Furthermore, add the edge $xy$ in $G$.

The correctness of this reduction rule follows from the fact that vertices in $R$ can not be part of any solution and all the cycles passing through $v$ also passes through its neighbors.

In the polynomial kernel for the FEEDBACK VERTEX SET problem (with no conflict constraints), we can short-circuit degree two vertices. But in our case, we cannot perform this operation, since we also need the solution to be an independent set in the conflict graph. Thus to reduce the number of degree two vertices in $G$, we exploit the properties of a $d$-degenerate graph. To this end, we use the tool that we developed in Section 3. This immediately gives us the following reduction rule.

**Reduction Rule 7.** Let $P$ be a maximal degree two induced path in $G$. If $|V(P)| \ge n_{d+1}+1$, apply Algorithm 1 with input $(H, V(P) \setminus R)$. Let $\hat{V}(P)$ be the set returned by Algorithm 1. Let $v \in (V(P) \setminus R) \setminus \hat{V}(P)$, and $x, y$ be the neighbors of $v$ in $G$. Delete $v$ from the graphs $G, H$. Furthermore, add edge $xy$ in $G$.
14:10 Exploring the Kernelization Borders for Hitting Cycles

In the following, we state an easy observation, which follows from non-applicability of Reduction Rule 1 to 4.

**Observation 11.** Let $(G, H, R, k)$ be an instance of $\mathcal{D}_d$-DCF-FVS, where none of Reduction Rule 1 to 4 apply. Then the degree of each vertex in $G$ is bounded by $\mathcal{O}(k^2)$.

**Proof.** As Reduction Rule 3 is not applicable, then there is no $k+1$-flower in $G$. Now, if there is $v \in V(G)$ with degree at least $4k + (k+2)2k$, then Reduction Rule 4 would be applicable. ◀

To design our next reduction rule, we construct an auxiliary graph $G^*$. Intuitively speaking, $G^*$ is obtained from $G$ by shortcutting all degree two vertices. That is, vertex set of $G^*$ comprises of all the vertices of degree at least three in 3. From now on, vertices of degree at least 3 (in $G$) will be referred to as high degree vertices. For each $uv \in E(G)$, where $u, v$ are high degree vertices, we add the edge $uv$ in $G^*$. Furthermore, for an induced maximal path $P_{uv}$, between $u$ and $v$ where all the internal vertices of $P_{uv}$ are degree two vertices in $G$, we add the (multi) edge $uv$ to $E(G^*)$. Next, we will use the following result to bound the number of vertices and edges in $G^*$.

**Proposition 12.** [8] A graph $G$ with minimum degree at least 3, maximum degree $\Delta$, and a feedback vertex set of size at most $k$ has at most $(\Delta + 1)k$ vertices and $2\Delta k$ edges.

The above result (together with the construction of $G^*$) gives us the following (safe) reduction rule.

**Reduction Rule 5.** If $|V(G^*)| \ge 4k^2 + 2k^2(k+2)$ or $|E(G^*)| \ge 8k^2 + 4k^2(k+2)$, then return NO.

**Lemma 13.** Let $(G, H, R, k)$ be an instance of $\mathcal{D}_d$-DCF-FVS, where none of the Reduction Rules 1 to 5 are applicable. Then we obtain the following bounds:

- The number of vertices of degree at least 3 in $G$ is bounded by $\mathcal{O}(k^3)$.

- The number of maximal degree two induced paths in $G$ is bounded by $\mathcal{O}(k^3)$.

Having shown the above bounds, it remains to bound the number of degree two vertices in $G$. We start by applying the following simple reduction rule to eliminate vertices of degree two in $G$, which are also in $R$.

**Reduction Rule 6.** Let $v \in R$, $d_G(v) = 2$, and $x, y$ be the neighbors of $v$ in $G$. Delete $v$ from the graphs $G, H$ and the set $R$. Furthermore, add the edge $xy$ in $G$.

The correctness of this reduction rule follows from the fact that vertices in $R$ can not be part of any solution and all the cycles passing through $v$ also passes through its neighbors.

In the polynomial kernel for the FEEDBACK VERTEX SET problem (with no conflict constraints), we can short-circuit degree two vertices. But in our case, we cannot perform this operation, since we also need the solution to be an independent set in the conflict graph. Thus to reduce the number of degree two vertices in $G$, we exploit the properties of a $d$-degenerate graph. To this end, we use the tool that we developed in Section 3. This immediately gives us the following reduction rule.

**Reduction Rule 7.** Let $P$ be a maximal degree two induced path in $G$. If $|V(P)| \ge n_{d+1}+1$, apply Algorithm 1 with input $(H, V(P) \setminus R)$. Let $\hat{V}(P)$ be the set returned by Algorithm 1. Let $v \in (V(P) \setminus R) \setminus \hat{V}(P)$, and $x, y$ be the neighbors of $v$ in $G$. Delete $v$ from the graphs $G, H$. Furthermore, add edge $xy$ in $G$.
► **Lemma 14.** *Reduction Rule 7 is safe.*

**Proof.** Let $(G, H, R, k)$ be an instance of $\mathcal{D}_d$-DCF-FVS and $v$ be a vertex in a maximal degree two path $P$ with neighbors $x$ and $y$, with respect to which Reduction Rule 14 is applied. Furthermore, let $(G', H', R, k)$ be the resulting instance after application of the reduction rule. We will show that $(G, H, R, k)$ is a YES instance of $\mathcal{D}_d$-DCF-FVS if and only if $(G', H', R, k)$ is a YES instance of $\mathcal{D}_d$-DCF-FVS.

In the forward direction, let $(G, H, R, k)$ be a YES instance of $\mathcal{D}_d$-DCF-FVS and $S$ be one of its minimal solution. Consider the case when $v \notin S$. In this case, we claim that $S$ is also a solution of $\mathcal{D}_d$-DCF-FVS for $(G', H', R, k)$. Suppose not then either $S$ is not an independent set in $H'$ or $G' - S$ contains a cycle. Since, $H'$ is an induced subgraph of $H$, we have that $S'$ is also an independent set in $H'$. So we assume that $G' - S$ has a cycle, say $C$. If $C$ does not contain the edge $xy$, then $C$ is also a cycle in $G - S$. Therefore, we assume that $C$ contains the edge $xy$. But then $(C \setminus \{xy\}) \cup \{xv, vy\}$ is a cycle in $G - S$. Next, we consider the case when $v \in S$. By Lemma 5 we have a vertex $v' \in V(P) \setminus \{v\}$ such that $(S \setminus \{v\}) \cup \{v'\}$ is an independent set in $H'$. By using the fact that any cycle that passes through $v$ also contains all vertices in $P$ (together with the discussions above) imply that $(S \setminus \{v\}) \cup \{v'\}$ is a solution of $\mathcal{D}_d$-DCF-FVS for $(G', H', R, k)$.

In the reverse direction, let $(G', H', R, k)$ be a YES instance of $\mathcal{D}_d$-DCF-FVS and $S'$ be one of its minimal solution. We claim that $S'$ is also a solution of $\mathcal{D}_d$-DCF-FVS for $(G, H, R, k)$. Suppose not, then either $S$ is not an independent set in $H$ or $G - S$ contains a cycle. Since, $H'$ is an induced subgraph of $H$, we have that $S'$ is also an independent set in $H$. Next, assume that there is a cycle $C$ in $G - S$. The cycle $C$ must contain $v$, otherwise, $C$ is also a cycle in $G' - S'$. Since $v$ is a degree two vertex in $G$, therefore any cycle that contains $v$, must also contain $x$ and $y$. As observed before, $G - \{xv, vy\}$ is identical to $G' - \{xy\}$. But then, $(C \setminus \{xv, vy\}) \cup \{xy\}$ is a cycle in $G' - S'$, a contradiction. This concludes that $S'$ is a solution of $\mathcal{D}_d$-DCF-FVS for $(G, H, R, k)$. ◀

► **Lemma 15.** $(\star)$ Let $(G, H, R, k)$ be an instance of $\mathcal{D}_d$-DCF-FVS, where none of the Reduction Rules 1 to 7 are applicable. Then the number of vertices in a degree two induced path in $G$ is bounded by $O(k^{O(d)})$.

► **Theorem 16.** $\mathcal{D}_d$-DCF-FVS admits a kernel with $O(k^{O(d)})$ vertices.

► **Lemma 17.** $(\star)$ There is a polynomial time parameter preserving reduction from $\mathcal{D}_d$-DCF-FVS to $\mathcal{D}_d$-CF-FVS.

By Theorem 16 and Lemma 17, we obtain the following result.

► **Theorem 18.** $\mathcal{D}_d$-CF-FVS admits a kernel with $O(k^{O(d)})$ vertices.

# 5 Kernelization Complexity of $\mathcal{P}_{\le 3}^{**}$-CF-OCT

In this section, we show that CF-OCT does not admit a polynomial kernel when the conflict graph belongs to the family $\mathcal{P}_{\le 3}^{**}$. Let $\mathcal{P}_{\le 3}$ denotes the family of disjoint union of paths of length at most three, and $\mathcal{P}_{\le 3}^{*}$ denotes the family of disjoint union of paths of length at most three and a star graph. We give parameter preserving reduction from $\mathcal{P}_{\le 3}^{*}$-CONFLICT FREE $s-t$ CUT ($\mathcal{P}_{\le 3}^{*}$-CF-$s-t$ CUT) to $\mathcal{P}_{\le 3}^{**}$-CF-OCT.

We first prove that $\mathcal{P}_{\le 3}^{*}$-CF-$s-t$ CUT is NP-hard. Then, we prove that $\mathcal{P}_{\le 3}^{*}$-CF-$s-t$ CUT does not admit a polynomial compression, unless $\mathrm{NP} \subseteq \mathrm{coNP}/\mathrm{poly}$ using the method of cross-composition.
► **Lemma 14.** *Reduction Rule 7 is safe.*

**Proof.** Let $(G, H, R, k)$ be an instance of $\mathcal{D}_d$-DCF-FVS and $v$ be a vertex in a maximal degree two path $P$ with neighbors $x$ and $y$, with respect to which Reduction Rule 14 is applied. Furthermore, let $(G', H', R, k)$ be the resulting instance after application of the reduction rule. We will show that $(G, H, R, k)$ is a YES instance of $\mathcal{D}_d$-DCF-FVS if and only if $(G', H', R, k)$ is a YES instance of $\mathcal{D}_d$-DCF-FVS.

In the forward direction, let $(G, H, R, k)$ be a YES instance of $\mathcal{D}_d$-DCF-FVS and $S$ be one of its minimal solution. Consider the case when $v \notin S$. In this case, we claim that $S$ is also a solution of $\mathcal{D}_d$-DCF-FVS for $(G', H', R, k)$. Suppose not then either $S$ is not an independent set in $H'$ or $G' - S$ contains a cycle. Since, $H'$ is an induced subgraph of $H$, we have that $S'$ is also an independent set in $H'$. So we assume that $G' - S$ has a cycle, say $C$. If $C$ does not contain the edge $xy$, then $C$ is also a cycle in $G - S$. Therefore, we assume that $C$ contains the edge $xy$. But then $(C \setminus \{xy\}) \cup \{xv, vy\}$ is a cycle in $G - S$. Next, we consider the case when $v \in S$. By Lemma 5 we have a vertex $v' \in V(P) \setminus \{v\}$ such that $(S \setminus \{v\}) \cup \{v'\}$ is an independent set in $H'$. By using the fact that any cycle that passes through $v$ also contains all vertices in $P$ (together with the discussions above) imply that $(S \setminus \{v\}) \cup \{v'\}$ is a solution of $\mathcal{D}_d$-DCF-FVS for $(G', H', R, k)$.

In the reverse direction, let $(G', H', R, k)$ be a YES instance of $\mathcal{D}_d$-DCF-FVS and $S'$ be one of its minimal solution. We claim that $S'$ is also a solution of $\mathcal{D}_d$-DCF-FVS for $(G, H, R, k)$. Suppose not, then either $S$ is not an independent set in $H$ or $G - S$ contains a cycle. Since, $H'$ is an induced subgraph of $H$, we have that $S'$ is also an independent set in $H$. Next, assume that there is a cycle $C$ in $G - S$. The cycle $C$ must contain $v$, otherwise, $C$ is also a cycle in $G' - S'$. Since $v$ is a degree two vertex in $G$, therefore any cycle that contains $v$, must also contain $x$ and $y$. As observed before, $G - \{xv, vy\}$ is identical to $G' - \{xy\}$. But then, $(C \setminus \{xv, vy\}) \cup \{xy\}$ is a cycle in $G' - S'$, a contradiction. This concludes that $S'$ is a solution of $\mathcal{D}_d$-DCF-FVS for $(G, H, R, k)$. ◀

► **Lemma 15.** $(\star)$ Let $(G, H, R, k)$ be an instance of $\mathcal{D}_d$-DCF-FVS, where none of the Reduction Rules 1 to 7 are applicable. Then the number of vertices in a degree two induced path in $G$ is bounded by $O(k^{O(d)})$.

► **Theorem 16.** $\mathcal{D}_d$-DCF-FVS admits a kernel with $O(k^{O(d)})$ vertices.

► **Lemma 17.** $(\star)$ There is a polynomial time parameter preserving reduction from $\mathcal{D}_d$-DCF-FVS to $\mathcal{D}_d$-CF-FVS.

By Theorem 16 and Lemma 17, we obtain the following result.

► **Theorem 18.** $\mathcal{D}_d$-CF-FVS admits a kernel with $O(k^{O(d)})$ vertices.

# 5 Kernelization Complexity of $\mathcal{P}_{\le 3}^{**}$-CF-OCT

In this section, we show that CF-OCT does not admit a polynomial kernel when the conflict graph belongs to the family $\mathcal{P}_{\le 3}^{**}$. Let $\mathcal{P}_{\le 3}$ denotes the family of disjoint union of paths of length at most three, and $\mathcal{P}_{\le 3}^{*}$ denotes the family of disjoint union of paths of length at most three and a star graph. We give parameter preserving reduction from $\mathcal{P}_{\le 3}^{*}$-CONFLICT FREE $s-t$ CUT ($\mathcal{P}_{\le 3}^{*}$-CF-$s-t$ CUT) to $\mathcal{P}_{\le 3}^{**}$-CF-OCT.

We first prove that $\mathcal{P}_{\le 3}^{*}$-CF-$s-t$ CUT is NP-hard. Then, we prove that $\mathcal{P}_{\le 3}^{*}$-CF-$s-t$ CUT does not admit a polynomial compression, unless $\mathrm{NP} \subseteq \mathrm{coNP}/\mathrm{poly}$ using the method of cross-composition.
<figure><img src="image_82.png" /></figure>

■ **Figure 1** An illustration of construction of graph $G'$ and $H'$ in reduction from $\mathcal{P}_{\le 3}^*\text{-CF-s-t CUT}$ to $\mathcal{P}_{\le 3}^{**}\text{-CF-OCT.}$

► **Theorem 19** (⋆). $\mathcal{P}_{\le 3}^*\text{-CF-s-t CUT}$ does not admit a polynomial compression unless $NP \subseteq \text{coNP/poly}$.

**Lower Bound for Kernel of $\mathcal{P}_{\le 3}^{**}$-CF-OCT.** In this subsection, we prove the main result of this section. We show that there does not exist a polynomial kernel of $\mathcal{P}_{\le 3}^{**}$-CF-OCT. Towards this we give a parameter preserving reduction from $\mathcal{P}_{\le 3}^*\text{-CF-s-t CUT}$ to $\mathcal{P}_{\le 3}^{**}$-CF-OCT. Given an instance $(G, H, s, t, k)$ of $\mathcal{P}_{\le 3}^*\text{-CF-s-t CUT}$, we construct an instance $(G', H', k+1)$ of $\mathcal{P}_{\le 3}^{**}$-CF-OCT as follows. Initially, we have $V(G') = V(H') = V(G) \cup \{z, a, b\}$. Now, for each edge $e_i \in E(G)$, add a vertex $w_i$ to $V(G')$ and $V(H')$. Now, we define the edge set of $G'$. Let $x_i, y_i$ be end points of $e_i \in E(G)$. For each $e_i \in E(G)$, add edges $x_i w_i$ and $y_i w_i$ to $E(G')$. Also, add a self loop on $z$ in $G'$ and edges $sa, ab$ and $bt$ to $E(G')$. To construct the edge set of $H'$, we set $E(H') = E(H - \{s, t\})$. Additionally, we add $zs, zt, za, zt$, and $zw_i$ for each $w_i \in V(H')$ to $E(H')$. Figure 1 describes the construction of $G'$ and $H'$.

Clearly, $H'$ belongs to $\mathcal{P}_3^{**}$ and this construction can be carried out in the polynomial time. Now, we prove the equivalence between the instances $(G, H, s, t, k)$ of $\mathcal{P}_{\le 3}^*\text{-CF-s-t CUT}$ and $(G', H', k+1)$ of $\mathcal{P}_{\le 3}^{**}$-CF-OCT in the following lemma.

► **Lemma 20.** $(G, H, s, t, k)$ is a yes-instance of $\mathcal{P}_{\le 3}^*\text{-CF-s-t CUT}$ if and only if $(G', H', k+1)$ is a yes-instance of $\mathcal{P}_{\le 3}^{**}\text{-CF-OCT}$.

**Proof.** In the forward direction, let $(G, H, s, t, k)$ be a yes-instance of $\mathcal{P}_{\le 3}^*\text{-CF-s-t CUT}$ and $S$ be one of its solution. We claim that $S \cup \{z\}$ is a solution to $\mathcal{P}_{\le 3}^{**}\text{-CF-OCT}$ in $(G', H', k+1)$. In the graph $G'$, since we subdivide each edge, all the paths from $s-t$ are of even length. Since, we subdivide each edge of $G, G' - \{a, b, z\}$ is a bipartite graph. Hence, an odd cycle in $G' - z$ consists of an $s-t$ path in $G' - \{a, b\}$ and edges $sa, ab$ and $bt$. Clearly, by the construction of $G'$, $(G' - \{a, b\}) \setminus S$ does not contain an $s-t$ path and hence $G' - z$ does not contain an odd cycle. Since, $H[S]$ is edgeless, $S \cup \{z\}$ is an independent set in $H'$. This completes the proof in the forward direction.

In the reverse direction, let $S$ be a solution to $\mathcal{P}_{\le 3}^{**}\text{-CF-OCT in } (G', H', k+1)$. Since, $z \in S$, therefore, $s, t, a, b, w_i \notin S$ for any $w_i \in V(H')$. We claim that $S' = S \setminus \{z\}$ is a solution to $\mathcal{P}_{\le 3}^*\text{-CF-s-t CUT in } (G, H, s, t, k)$. Suppose not, then there exists a $s-t$ path $(s, x_1, x_2, \cdots, x_l, t)$ in $G \setminus S'$. Correspondingly, there exists a $s-t$ path $(s, w_1, x_1, w_2, x_2, \cdots, x_l, w_{l+1}, t)$ in $G'$ of even length which results into an odd cycle $(s, w_1, x_1, w_2, x_2, \cdots, x_l, w_{l+1}, t, b, a)$ in $G' \setminus S$, a contradiction. This completes the proof. ◀

Now, we present the main result of this section in the following theorem.

► **Theorem 21.** $\mathcal{P}_{\le 3}^{**}$-CF-OCT does not admit a polynomial kernel. unless $NP \subseteq \text{coNP/poly}$.
<figure><img src="image_85.png" /><figcaption>■ **Figure 1** An illustration of construction of graph $G'$ and $H'$ in reduction from $\mathcal{P}_{\le 3}^*\text{-CF-s-t CUT}$ to $\mathcal{P}_{\le 3}^{**}\text{-CF-OCT.}$</figcaption></figure>

► **Theorem 19** (⋆). $\mathcal{P}_{\le 3}^*\text{-CF-s-t CUT}$ does not admit a polynomial compression unless $NP \subseteq \text{coNP/poly}$.

**Lower Bound for Kernel of $\mathcal{P}_{\le 3}^{**}$-CF-OCT.** In this subsection, we prove the main result of this section. We show that there does not exist a polynomial kernel of $\mathcal{P}_{\le 3}^{**}$-CF-OCT. Towards this we give a parameter preserving reduction from $\mathcal{P}_{\le 3}^*\text{-CF-s-t CUT}$ to $\mathcal{P}_{\le 3}^{**}$-CF-OCT. Given an instance $(G, H, s, t, k)$ of $\mathcal{P}_{\le 3}^*\text{-CF-s-t CUT}$, we construct an instance $(G', H', k+1)$ of $\mathcal{P}_{\le 3}^{**}$-CF-OCT as follows. Initially, we have $V(G') = V(H') = V(G) \cup \{z, a, b\}$. Now, for each edge $e_i \in E(G)$, add a vertex $w_i$ to $V(G')$ and $V(H')$. Now, we define the edge set of $G'$. Let $x_i, y_i$ be end points of $e_i \in E(G)$. For each $e_i \in E(G)$, add edges $x_i w_i$ and $y_i w_i$ to $E(G')$. Also, add a self loop on $z$ in $G'$ and edges $sa, ab$ and $bt$ to $E(G')$. To construct the edge set of $H'$, we set $E(H') = E(H - \{s, t\})$. Additionally, we add $zs, zt, za, zt$, and $zw_i$ for each $w_i \in V(H')$ to $E(H')$. Figure 1 describes the construction of $G'$ and $H'$.

Clearly, $H'$ belongs to $\mathcal{P}_3^{**}$ and this construction can be carried out in the polynomial time. Now, we prove the equivalence between the instances $(G, H, s, t, k)$ of $\mathcal{P}_{\le 3}^*\text{-CF-s-t CUT}$ and $(G', H', k+1)$ of $\mathcal{P}_{\le 3}^{**}$-CF-OCT in the following lemma.

► **Lemma 20.** $(G, H, s, t, k)$ is a yes-instance of $\mathcal{P}_{\le 3}^*\text{-CF-s-t CUT}$ if and only if $(G', H', k+1)$ is a yes-instance of $\mathcal{P}_{\le 3}^{**}\text{-CF-OCT}$.

**Proof.** In the forward direction, let $(G, H, s, t, k)$ be a yes-instance of $\mathcal{P}_{\le 3}^*\text{-CF-s-t CUT}$ and $S$ be one of its solution. We claim that $S \cup \{z\}$ is a solution to $\mathcal{P}_{\le 3}^{**}\text{-CF-OCT}$ in $(G', H', k+1)$. In the graph $G'$, since we subdivide each edge, all the paths from $s-t$ are of even length. Since, we subdivide each edge of $G, G' - \{a, b, z\}$ is a bipartite graph. Hence, an odd cycle in $G' - z$ consists of an $s-t$ path in $G' - \{a, b\}$ and edges $sa, ab$ and $bt$. Clearly, by the construction of $G'$, $(G' - \{a, b\}) \setminus S$ does not contain an $s-t$ path and hence $G' - z$ does not contain an odd cycle. Since, $H[S]$ is edgeless, $S \cup \{z\}$ is an independent set in $H'$. This completes the proof in the forward direction.

In the reverse direction, let $S$ be a solution to $\mathcal{P}_{\le 3}^{**}\text{-CF-OCT in } (G', H', k+1)$. Since, $z \in S$, therefore, $s, t, a, b, w_i \notin S$ for any $w_i \in V(H')$. We claim that $S' = S \setminus \{z\}$ is a solution to $\mathcal{P}_{\le 3}^*\text{-CF-s-t CUT in } (G, H, s, t, k)$. Suppose not, then there exists a $s-t$ path $(s, x_1, x_2, \cdots, x_l, t)$ in $G \setminus S'$. Correspondingly, there exists a $s-t$ path $(s, w_1, x_1, w_2, x_2, \cdots, x_l, w_{l+1}, t)$ in $G'$ of even length which results into an odd cycle $(s, w_1, x_1, w_2, x_2, \cdots, x_l, w_{l+1}, t, b, a)$ in $G' \setminus S$, a contradiction. This completes the proof. ◀

Now, we present the main result of this section in the following theorem.

► **Theorem 21.** $\mathcal{P}_{\le 3}^{**}$-CF-OCT does not admit a polynomial kernel. unless $NP \subseteq \text{coNP/poly}$.
# 6 Conclusion

In this paper we studied kernelization complexity of $\mathcal{D}_d$-CF-FVS and $\mathcal{D}_d$-CF-OCT. We showed that the former admits a polynomial kernel of size $k^{O(d)}$, while $\mathcal{D}_d$-CF-OCT does not admit any polynomial kernel unless $NP \subseteq \text{coNP}$, $\text{poly}$. In fact, the later does not admit polynomial kernel even for much more specialized problem, namely $\mathcal{P}^{\star\star}_{\le 3}$-CF-OCT. Using much more involved marking scheme we can show that $\mathcal{D}_d$-CF-ECT admits polynomial kernel of size $k^{O(d)}$. Similarly, we can extend the known polynomial kernel for OCT to CF-OCT when the conflict graph $H$ has maximum degree at most one. Two most interesting questions that still remain open form our work are following: (a) does CF-FVS admit uniform polynomial kernel on graphs of bounded expansion; and (b) does CF-OCT admit a polynomial kernel when $H$ is disjoint union of paths of length at most 2.

# References

1. Esther M. Arkin, Aritra Banik, Paz Carmi, Gui Citovsky, Matthew J. Katz, Joseph S. B. Mitchell, and Marina Simakov. Choice is Hard. In *ISAAC*, pages 318–328, 2015.

2. Esther M. Arkin, Aritra Banik, Paz Carmi, Gui Citovsky, Matthew J. Katz, Joseph S. B. Mitchell, and Marina Simakov. Conflict-free Covering. In *CCCG*, pages 17–23, 2015.

3. Aritra Banik, Fahad Panolan, Venkatesh Raman, and Vibha Sahlot. Fréchet Distance Between a Line and Avatar Point Set. *FSTTCS*, pages 32:1–32:14, 2016.

4. Hans L. Bodlaender. On disjoint cycles. In *WG*, volume 570, pages 230–238, 1992.

5. Hans L. Bodlaender. A Cubic Kernel for Feedback Vertex Set. In *STACS*, volume 4393, pages 320–331, 2007.

6. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernelization Lower Bounds by Cross-Composition. *J. Discrete Math.*, 28:277–305, 2014.

7. Kevin Burrage, Vladimir Estivill-Castro, Michael R. Fellows, Michael A. Langston, Shev Mac, and Frances A. Rosamond. The Undirected Feedback Vertex Set Problem Has a Poly($k$) Kernel. In *IWPEC*, volume 4169, pages 192–202, 2006.

8. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. *Parameterized Algorithms*. Springer, 2015.

9. Andreas Darmann, Ulrich Pferschy, and Joachim Schauer. Determining a Minimum Spanning Tree with Disjunctive Constraints. In *ADT*, volume 5783, pages 414–423, 2009.

10. Andreas Darmann, Ulrich Pferschy, Joachim Schauer, and Gerhard J. Woeginger. Paths, trees and matchings under disjunctive constraints. *Discrete Applied Mathematics*, 159(16):1726–1735, 2011.

11. Rodney G. Downey and Michael R. Fellows. Fixed Parameter Tractability and Completeness. In *Complexity Theory: Current Research*, pages 191–225, 1992.

12. Leah Epstein, Lene M. Favrholdt, and Asaf Levin. Online variable-sized bin packing with conflicts. *Discrete Optimization*, 8(2):333–343, 2011.

13. Guy Even, Magnús M. Halldórsson, Lotem Kaplan, and Dana Ron. Scheduling with conflicts: online and offline algorithms. *J. Scheduling*, 12(2):199–224, 2009.

14. Pallavi Jain, Lawqueen Kanesh, and Pranabendu Misra. Conflict Free Version of Covering Problems on Graphs: Classical and Parameterized. *CSR*, pages 194–206, 2018.

15. Viggo Kann. Polynomially bounded minimization problems which are hard to approximate. In *ICALP*, pages 52–63, 1993.

16. Stefan Kratsch and Magnus Wahlström. Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal. *ACM Trans. Algorithms*, 10(4):20:1–20:15, 2014.
# 6 Conclusion

In this paper we studied kernelization complexity of $\mathcal{D}_d$-CF-FVS and $\mathcal{D}_d$-CF-OCT. We showed that the former admits a polynomial kernel of size $k^{O(d)}$, while $\mathcal{D}_d$-CF-OCT does not admit any polynomial kernel unless $NP \subseteq \text{coNP}$, $\text{poly}$. In fact, the later does not admit polynomial kernel even for much more specialized problem, namely $\mathcal{P}^{\star\star}_{\le 3}$-CF-OCT. Using much more involved marking scheme we can show that $\mathcal{D}_d$-CF-ECT admits polynomial kernel of size $k^{O(d)}$. Similarly, we can extend the known polynomial kernel for OCT to CF-OCT when the conflict graph $H$ has maximum degree at most one. Two most interesting questions that still remain open form our work are following: (a) does CF-FVS admit uniform polynomial kernel on graphs of bounded expansion; and (b) does CF-OCT admit a polynomial kernel when $H$ is disjoint union of paths of length at most 2.

# References

1. Esther M. Arkin, Aritra Banik, Paz Carmi, Gui Citovsky, Matthew J. Katz, Joseph S. B. Mitchell, and Marina Simakov. Choice is Hard. In *ISAAC*, pages 318–328, 2015.

2. Esther M. Arkin, Aritra Banik, Paz Carmi, Gui Citovsky, Matthew J. Katz, Joseph S. B. Mitchell, and Marina Simakov. Conflict-free Covering. In *CCCG*, pages 17–23, 2015.

3. Aritra Banik, Fahad Panolan, Venkatesh Raman, and Vibha Sahlot. Fréchet Distance Between a Line and Avatar Point Set. *FSTTCS*, pages 32:1–32:14, 2016.

4. Hans L. Bodlaender. On disjoint cycles. In *WG*, volume 570, pages 230–238, 1992.

5. Hans L. Bodlaender. A Cubic Kernel for Feedback Vertex Set. In *STACS*, volume 4393, pages 320–331, 2007.

6. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernelization Lower Bounds by Cross-Composition. *J. Discrete Math.*, 28:277–305, 2014.

7. Kevin Burrage, Vladimir Estivill-Castro, Michael R. Fellows, Michael A. Langston, Shev Mac, and Frances A. Rosamond. The Undirected Feedback Vertex Set Problem Has a Poly($k$) Kernel. In *IWPEC*, volume 4169, pages 192–202, 2006.

8. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. *Parameterized Algorithms*. Springer, 2015.

9. Andreas Darmann, Ulrich Pferschy, and Joachim Schauer. Determining a Minimum Spanning Tree with Disjunctive Constraints. In *ADT*, volume 5783, pages 414–423, 2009.

10. Andreas Darmann, Ulrich Pferschy, Joachim Schauer, and Gerhard J. Woeginger. Paths, trees and matchings under disjunctive constraints. *Discrete Applied Mathematics*, 159(16):1726–1735, 2011.

11. Rodney G. Downey and Michael R. Fellows. Fixed Parameter Tractability and Completeness. In *Complexity Theory: Current Research*, pages 191–225, 1992.

12. Leah Epstein, Lene M. Favrholdt, and Asaf Levin. Online variable-sized bin packing with conflicts. *Discrete Optimization*, 8(2):333–343, 2011.

13. Guy Even, Magnús M. Halldórsson, Lotem Kaplan, and Dana Ron. Scheduling with conflicts: online and offline algorithms. *J. Scheduling*, 12(2):199–224, 2009.

14. Pallavi Jain, Lawqueen Kanesh, and Pranabendu Misra. Conflict Free Version of Covering Problems on Graphs: Classical and Parameterized. *CSR*, pages 194–206, 2018.

15. Viggo Kann. Polynomially bounded minimization problems which are hard to approximate. In *ICALP*, pages 52–63, 1993.

16. Stefan Kratsch and Magnus Wahlström. Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal. *ACM Trans. Algorithms*, 10(4):20:1–20:15, 2014.
14:14 Exploring the Kernelization Borders for Hitting Cycles

17 Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Roohani Sharma, and Meirav Zehavi. Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms. In *SODA*, pages 2785–2800, 2018.

18 David W. Matula and Leland L. Beck. Smallest-Last Ordering and clustering and Graph Coloring Algorithms. *J. ACM*, 30(3):417–427, 1983.

19 Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, and Saket Saurabh. On Parameterized Independent Feedback Vertex Set. *Theor. Comput. Sci.*, 461:65–75, 2012.

20 Pranabendu Misra, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. Parameterized Algorithms for Even Cycle Transversal. In *WG*, volume 7551, pages 172–183, 2012.

21 Ulrich Pferschy and Joachim Schauer. The Maximum Flow Problem with Conflict and Forcing Conditions. In *INOC*, volume 6701, pages 289–294, 2011.

22 Ulrich Pferschy and Joachim Schauer. The maximum flow problem with disjunctive constraints. *J. Comb. Optim.*, 26(1):109–119, 2013.

23 Ulrich Pferschy and Joachim Schauer. Approximation of knapsack problems with conflict and forcing graphs. *J. Comb. Optim.*, 33(4):1300–1323, 2017.

24 Bruce A. Reed, Kaleigh Smith, and Adrian Vetta. Finding odd cycle transversals. *Oper. Res. Lett.*, 32(4):299–301, 2004.

25 Stéphan Thomassé. A $4k^2$ kernel for feedback vertex set. *ACM Trans. Algorithms*, 6(2):32:1–32:8, 2010.
14:14 Exploring the Kernelization Borders for Hitting Cycles

17 Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Roohani Sharma, and Meirav Zehavi. Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms. In *SODA*, pages 2785–2800, 2018.

18 David W. Matula and Leland L. Beck. Smallest-Last Ordering and clustering and Graph Coloring Algorithms. *J. ACM*, 30(3):417–427, 1983.

19 Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, and Saket Saurabh. On Parameterized Independent Feedback Vertex Set. *Theor. Comput. Sci.*, 461:65–75, 2012.

20 Pranabendu Misra, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. Parameterized Algorithms for Even Cycle Transversal. In *WG*, volume 7551, pages 172–183, 2012.

21 Ulrich Pferschy and Joachim Schauer. The Maximum Flow Problem with Conflict and Forcing Conditions. In *INOC*, volume 6701, pages 289–294, 2011.

22 Ulrich Pferschy and Joachim Schauer. The maximum flow problem with disjunctive constraints. *J. Comb. Optim.*, 26(1):109–119, 2013.

23 Ulrich Pferschy and Joachim Schauer. Approximation of knapsack problems with conflict and forcing graphs. *J. Comb. Optim.*, 33(4):1300–1323, 2017.

24 Bruce A. Reed, Kaleigh Smith, and Adrian Vetta. Finding odd cycle transversals. *Oper. Res. Lett.*, 32(4):299–301, 2004.

25 Stéphan Thomassé. A $4k^2$ kernel for feedback vertex set. *ACM Trans. Algorithms*, 6(2):32:1–32:8, 2010.
# Best-Case and Worst-Case Sparsifiability of Boolean CSPs

## Hubie Chen

Birkbeck, University of London, Malet Street, Bloomsbury, London WC1E 7HX, United Kingdom
hubie@dcs.bbk.ac.uk

## Bart M. P. Jansen<fnref n="1" />

Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands
b.m.p.jansen@tue.nl

## Astrid Pieterse<fnref n="2" />

Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands
a.pieterse@tue.nl

### Abstract

We continue the investigation of polynomial-time sparsification for NP-complete Boolean Constraint Satisfaction Problems (CSPs). The goal in sparsification is to reduce the number of constraints in a problem instance without changing the answer, such that a bound on the number of resulting constraints can be given in terms of the number of variables *n*. We investigate how the worst-case sparsification size depends on the types of constraints allowed in the problem formulation (the constraint language). Two algorithmic results are presented. The first result essentially shows that for any arity *k*, the only constraint type for which no nontrivial sparsification is possible has exactly one falsifying assignment, and corresponds to logical OR (up to negations). Our second result concerns linear sparsification, that is, a reduction to an equivalent instance with $O(n)$ constraints. Using linear algebra over rings of integers modulo prime powers, we give an elegant necessary and sufficient condition for a constraint type to be captured by a degree-1 polynomial over such a ring, which yields linear sparsifications. The combination of these algorithmic results allows us to prove two characterizations that capture the optimal sparsification sizes for a range of Boolean CSPs. For NP-complete Boolean CSPs whose constraints are symmetric (the satisfaction depends only on the number of 1 values in the assignment, not on their positions), we give a complete characterization of which constraint languages allow for a linear sparsification. For Boolean CSPs in which every constraint has arity at most three, we characterize the optimal size of sparsifications in terms of the largest OR that can be expressed by the constraint language.

**2012 ACM Subject Classification** Computing methodologies → Symbolic and algebraic algorithms, Theory of computation → Problems, reductions and completeness, Theory of computation → Parameterized complexity and exact algorithms

**Keywords and phrases** constraint satisfaction problems, kernelization, sparsification, lower bounds

**Digital Object Identifier** 10.4230/LIPIcs.IPEC.2018.15

**Related Version** A full version is available at [4], https://arxiv.org/abs/1809.06171v1.

**Acknowledgements** We would like to thank Emil Jeřábek for the proof of Lemma 4.2.

<figure><img src="image_83.png" /></figure>

<footnote n="1">¹ Supported by NWO Gravitation grant “Networks”.</footnote>

<footnote n="2">² Supported by NWO Gravitation grant “Networks”.</footnote>
# Best-Case and Worst-Case Sparsifiability of Boolean CSPs

**Hubie Chen**

Birkbeck, University of London, Malet Street, Bloomsbury, London WC1E 7HX, United Kingdom
hubie@dcs.bbk.ac.uk

**Bart M. P. Jansen<fnref n="1" />**

Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands
b.m.p.jansen@tue.nl

**Astrid Pieterse<fnref n="2" />**

Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands
a.pieterse@tue.nl

## Abstract

We continue the investigation of polynomial-time sparsification for NP-complete Boolean Constraint Satisfaction Problems (CSPs). The goal in sparsification is to reduce the number of constraints in a problem instance without changing the answer, such that a bound on the number of resulting constraints can be given in terms of the number of variables *n*. We investigate how the worst-case sparsification size depends on the types of constraints allowed in the problem formulation (the constraint language). Two algorithmic results are presented. The first result essentially shows that for any arity *k*, the only constraint type for which no nontrivial sparsification is possible has exactly one falsifying assignment, and corresponds to logical OR (up to negations). Our second result concerns linear sparsification, that is, a reduction to an equivalent instance with $O(n)$ constraints. Using linear algebra over rings of integers modulo prime powers, we give an elegant necessary and sufficient condition for a constraint type to be captured by a degree-1 polynomial over such a ring, which yields linear sparsifications. The combination of these algorithmic results allows us to prove two characterizations that capture the optimal sparsification sizes for a range of Boolean CSPs. For NP-complete Boolean CSPs whose constraints are symmetric (the satisfaction depends only on the number of 1 values in the assignment, not on their positions), we give a complete characterization of which constraint languages allow for a linear sparsification. For Boolean CSPs in which every constraint has arity at most three, we characterize the optimal size of sparsifications in terms of the largest OR that can be expressed by the constraint language.

**2012 ACM Subject Classification** Computing methodologies → Symbolic and algebraic algorithms, Theory of computation → Problems, reductions and completeness, Theory of computation → Parameterized complexity and exact algorithms

**Keywords and phrases** constraint satisfaction problems, kernelization, sparsification, lower bounds

**Digital Object Identifier** 10.4230/LIPIcs.IPEC.2018.15

**Related Version** A full version is available at [4], https://arxiv.org/abs/1809.06171v1.

**Acknowledgements** We would like to thank Emil Jeřábek for the proof of Lemma 4.2.

<figure><img src="image_86.png" /></figure>

<footnote n="1">¹ Supported by NWO Gravitation grant “Networks”.</footnote>

<footnote n="2">² Supported by NWO Gravitation grant “Networks”.</footnote>
# 1 Introduction

## Background

The framework of constraint satisfaction problems (CSPs) provides a unified way to study the computational complexity of a wide variety of combinatorial problems such as CNF-SATISFIABILITY, GRAPH COLORING, and NOT-ALL-EQUAL SAT. The framework uncovers algorithmic approaches that simultaneously apply to several problems, and also identifies common sources of intractability. For the purposes of this discussion, a CSP is specified using a (finite) constraint language, which is a set of (finite) relations; the problem is to decide the satisfiability of a set of constraints, where each constraint has a relation coming from the constraint language. The fact that many problems can be viewed as CSPs motivates the following investigation: how does the complexity of a CSP depend its constraint language? A key result in this area is Schaefer's dichotomy theorem [18], which classifies each CSP over the Boolean domain as polynomial-time solvable or NP-complete.

Continuing a recent line of investigation [10, 12, 15], we aim to understand for which NP-complete CSPs an instance can be sparsified in polynomial time, without changing the answer. In particular, we investigate the following questions. Can the number of constraints be reduced to a small function of the number of variables $n$? How does the sparsifiability of a CSP depend on its constraint language? We utilize the framework of kernelization [5, 8, 16], originating in parameterized complexity theory, to answer such questions.

The first results concerning polynomial-time sparsification in terms of the number $n$ of variables or vertices were mainly negative. Under the assumption that $NP \not\subseteq coNP/poly$ (which we tacitly assume throughout this introduction), Dell and van Melkebeek [7] proved a strong lower bound: For any integer $d \ge 3$ and positive real $\varepsilon$, there cannot be a polynomial-time algorithm that compresses any instance $\varphi$ of $d$-CNF-SAT on $n$ variables, into an equivalent SAT instance $\varphi'$ of bitsize $O(n^{d-\varepsilon})$. In fact, there cannot even be an algorithm that transforms such $\varphi$ into small equivalent instances $\psi$ of an arbitrary decision problem. Since an instance of $d$-CNF-SAT has at most $2^d n^d \in O(n^d)$ distinct clauses, it can trivially be sparsified to $O(n^d)$ clauses by removing duplicates, and can be compressed to size $O(n^d)$ by storing it as a bitstring indicating for each possible clause whether or not it is present. The cited lower bound therefore shows that the trivial sparsification for $d$-CNF-SAT cannot be significantly improved; we say that the problem does not admit nontrivial (polynomial-time) sparsification. Following these lower bounds for SAT, a number of other results were published [6, 9, 14] proving other problems do not admit nontrivial sparsification either.

This pessimistic state of affairs concerning nontrivial sparsification algorithms changed several years ago, when a subset of the authors [12] showed that the $d$-NOT-ALL-EQUAL SAT problem does have a nontrivial sparsification. In this problem, clauses have size at most $d$ and are satisfied if the literals do not all evaluate to the same value. While there can be $\Omega(n^d)$ different clauses in an instance, there is an efficient algorithm that finds a subset of $O(n^{d-1})$ clauses that preserves the answer, resulting in a compression of bitsize $O(n^{d-1} \log n)$. The first proof of this result was based on an ad-hoc application of a theorem of Lovász [17]. Later, the underlying proof technique was extracted and applied to a wider range of problems [10]. This led to the following understanding: if each relation in the constraint language can be represented by a polynomial of degree at most $d$, in a certain technical sense, then this allows the number of constraints in an $n$-variable instance of such a CSP to be reduced to $O(n^d)$. The sparsification for $d$-NOT-ALL-EQUAL SAT is then explained by noting that such constraints can be captured by polynomials of degree $d-1$. It is therefore apparent that finding a low-degree polynomial to capture the constraints of a CSP is a powerful tool
# 1 Introduction

## Background

The framework of constraint satisfaction problems (CSPs) provides a unified way to study the computational complexity of a wide variety of combinatorial problems such as CNF-SATISFIABILITY, GRAPH COLORING, and NOT-ALL-EQUAL SAT. The framework uncovers algorithmic approaches that simultaneously apply to several problems, and also identifies common sources of intractability. For the purposes of this discussion, a CSP is specified using a (finite) constraint language, which is a set of (finite) relations; the problem is to decide the satisfiability of a set of constraints, where each constraint has a relation coming from the constraint language. The fact that many problems can be viewed as CSPs motivates the following investigation: how does the complexity of a CSP depend its constraint language? A key result in this area is Schaefer's dichotomy theorem [18], which classifies each CSP over the Boolean domain as polynomial-time solvable or NP-complete.

Continuing a recent line of investigation [10, 12, 15], we aim to understand for which NP-complete CSPs an instance can be sparsified in polynomial time, without changing the answer. In particular, we investigate the following questions. Can the number of constraints be reduced to a small function of the number of variables $n$? How does the sparsifiability of a CSP depend on its constraint language? We utilize the framework of kernelization [5, 8, 16], originating in parameterized complexity theory, to answer such questions.

The first results concerning polynomial-time sparsification in terms of the number $n$ of variables or vertices were mainly negative. Under the assumption that $NP \not\subseteq coNP/poly$ (which we tacitly assume throughout this introduction), Dell and van Melkebeek [7] proved a strong lower bound: For any integer $d \ge 3$ and positive real $\varepsilon$, there cannot be a polynomial-time algorithm that compresses any instance $\varphi$ of $d$-CNF-SAT on $n$ variables, into an equivalent SAT instance $\varphi'$ of bitsize $O(n^{d-\varepsilon})$. In fact, there cannot even be an algorithm that transforms such $\varphi$ into small equivalent instances $\psi$ of an arbitrary decision problem. Since an instance of $d$-CNF-SAT has at most $2^d n^d \in O(n^d)$ distinct clauses, it can trivially be sparsified to $O(n^d)$ clauses by removing duplicates, and can be compressed to size $O(n^d)$ by storing it as a bitstring indicating for each possible clause whether or not it is present. The cited lower bound therefore shows that the trivial sparsification for $d$-CNF-SAT cannot be significantly improved; we say that the problem does not admit nontrivial (polynomial-time) sparsification. Following these lower bounds for SAT, a number of other results were published [6, 9, 14] proving other problems do not admit nontrivial sparsification either.

This pessimistic state of affairs concerning nontrivial sparsification algorithms changed several years ago, when a subset of the authors [12] showed that the $d$-NOT-ALL-EQUAL SAT problem does have a nontrivial sparsification. In this problem, clauses have size at most $d$ and are satisfied if the literals do not all evaluate to the same value. While there can be $\Omega(n^d)$ different clauses in an instance, there is an efficient algorithm that finds a subset of $O(n^{d-1})$ clauses that preserves the answer, resulting in a compression of bitsize $O(n^{d-1} \log n)$. The first proof of this result was based on an ad-hoc application of a theorem of Lovász [17]. Later, the underlying proof technique was extracted and applied to a wider range of problems [10]. This led to the following understanding: if each relation in the constraint language can be represented by a polynomial of degree at most $d$, in a certain technical sense, then this allows the number of constraints in an $n$-variable instance of such a CSP to be reduced to $O(n^d)$. The sparsification for $d$-NOT-ALL-EQUAL SAT is then explained by noting that such constraints can be captured by polynomials of degree $d-1$. It is therefore apparent that finding a low-degree polynomial to capture the constraints of a CSP is a powerful tool
to obtain sparsification algorithms for it. Finding such polynomials of a certain degree $d$, or
determining that they do not exist, proved a challenging and time-intensive task (cf. [11]).

The polynomial-based framework [10] also resulted in some *linear* sparsifications. Since
“1-in-$d$” constraints (to satisfy a clause, *exactly one* out of its $\le d$ literals should evaluate to
true) can be captured by *linear* polynomials, the 1-in-$d$-SAT problem has a sparsification
with $O(n)$ constraints for each constant $d$. This prompted a detailed investigation into
linear sparsifications for CSPs by Lagerkvist and Wahlström [15], who used the toolkit of
universal algebra in an attempt to obtain a characterization of the Boolean CSPs with a
linear sparsification. Their results give a necessary and sufficient condition on the constraint
language of a CSP for having a so-called Maltsev embedding over an infinite domain. They
also show that when a CSP has a Maltsev embedding over a *finite* domain, then this
can be used to obtain a linear sparsification. Alas, it remains unclear whether Maltsev
embeddings over infinite domains can be exploited algorithmically, and a characterization of
the linearly-sparsifiable CSPs is currently not known.

## Our contributions

We analyze and demonstrate the power of the polynomial-based framework for sparsifying
CSPs using universal algebra, linear algebra over rings, and relational analysis. We present
two new algorithmic results. These allow us to characterize the sparsifiability of Boolean
CSPs in two settings, wherein we show that the polynomial-based framework yields *optimal*
sparsifications. In comparison to previous work [10], our results are much more fine-grained
and based on a deeper understanding of the reasons why a certain CSP *cannot* be captured
by low-degree polynomials.

**Algorithmic results.** Our first result (Section 3) shows that, contrary to the pessimistic
picture that arose during the initial investigation of sparsifiability, the phenomenon of
nontrivial sparsification is widespread and occurs for almost all Boolean CSPs! We prove
that if $\Gamma$ is a constraint language whose largest constraint has arity $k$, then the *only* reason
that CSP($\Gamma$) does not have a nontrivial sparsification, is that it contains an arity-$k$ relation
that is essentially the $k$-ary OR (up to negating variables). When $R \subseteq \{0,1\}^k$ is a relation
with $|\{0,1\}^k \setminus R| \ne 1$ (the number of assignments that fail to satisfy the constraint is not
equal to 1), then it can be captured by a polynomial of degree $k-1$. This yields a nontrivial
sparsification compared to the $\Omega(n^k)$ distinct applications of this constraint that can be in
such an instance.

Our second algorithmic result (Section 4) concerns the power of the polynomial-based
framework for obtaining linear sparsifications. We give a necessary and sufficient condition
for a relation to be captured by a degree-1 polynomial. Say that a Boolean relation $R \subseteq
\{0,1\}^k$ is *balanced* if there is *no* sequence of vectors $s_1, \dots, s_{2n}, s_{2n+1} \in R$ for $n \ge 1$ such
that $s_1 - s_2 + s_3 - \dots - s_{2n} + s_{2n+1} = u \in \{0,1\}^k \setminus R$. (The same vector may appear
multiple times in this sum.) In other words: $R$ is balanced if one cannot find an odd-length
sequence of vectors in $R$ for which alternating between adding and subtracting these vectors
component-wise results in a 0/1-bitvector $u$ that is outside $R$. For example, the binary OR
relation $2-OR = \{0,1\}^2 \setminus \{(0,0)\}$ is *not* balanced, since $(0,1) - (1,1) + (1,0) = (0,0) \notin 2-OR$,
but the 1-in-3 relation $R_{=1} = \{(1,0,0), (0,1,0), (0,0,1)\}$ is. We prove that if a Boolean
relation $R$ is balanced, then it can efficiently be captured by a degree-1 polynomial and
the number of constraints that are applications of this relation can be reduced to $O(n)$.
Hence when all relations in a constraint language $\Gamma$ are balanced—we call such a constraint
language *balanced*—then CSP($\Gamma$) has a sparsification with $O(n)$ constraints. We also show
to obtain sparsification algorithms for it. Finding such polynomials of a certain degree $d$, or
determining that they do not exist, proved a challenging and time-intensive task (cf. [11]).

The polynomial-based framework [10] also resulted in some *linear* sparsifications. Since
“1-in-$d$” constraints (to satisfy a clause, *exactly one* out of its $\le d$ literals should evaluate to
true) can be captured by *linear* polynomials, the 1-in-$d$-SAT problem has a sparsification
with $O(n)$ constraints for each constant $d$. This prompted a detailed investigation into
linear sparsifications for CSPs by Lagerkvist and Wahlström [15], who used the toolkit of
universal algebra in an attempt to obtain a characterization of the Boolean CSPs with a
linear sparsification. Their results give a necessary and sufficient condition on the constraint
language of a CSP for having a so-called Maltsev embedding over an infinite domain. They
also show that when a CSP has a Maltsev embedding over a *finite* domain, then this
can be used to obtain a linear sparsification. Alas, it remains unclear whether Maltsev
embeddings over infinite domains can be exploited algorithmically, and a characterization of
the linearly-sparsifiable CSPs is currently not known.

## Our contributions

We analyze and demonstrate the power of the polynomial-based framework for sparsifying
CSPs using universal algebra, linear algebra over rings, and relational analysis. We present
two new algorithmic results. These allow us to characterize the sparsifiability of Boolean
CSPs in two settings, wherein we show that the polynomial-based framework yields *optimal*
sparsifications. In comparison to previous work [10], our results are much more fine-grained
and based on a deeper understanding of the reasons why a certain CSP *cannot* be captured
by low-degree polynomials.

**Algorithmic results.** Our first result (Section 3) shows that, contrary to the pessimistic
picture that arose during the initial investigation of sparsifiability, the phenomenon of
nontrivial sparsification is widespread and occurs for almost all Boolean CSPs! We prove
that if $\Gamma$ is a constraint language whose largest constraint has arity $k$, then the *only* reason
that CSP($\Gamma$) does not have a nontrivial sparsification, is that it contains an arity-$k$ relation
that is essentially the $k$-ary OR (up to negating variables). When $R \subseteq \{0,1\}^k$ is a relation
with $|\{0,1\}^k \setminus R| \ne 1$ (the number of assignments that fail to satisfy the constraint is not
equal to 1), then it can be captured by a polynomial of degree $k-1$. This yields a nontrivial
sparsification compared to the $\Omega(n^k)$ distinct applications of this constraint that can be in
such an instance.

Our second algorithmic result (Section 4) concerns the power of the polynomial-based
framework for obtaining linear sparsifications. We give a necessary and sufficient condition
for a relation to be captured by a degree-1 polynomial. Say that a Boolean relation $R \subseteq
\{0,1\}^k$ is *balanced* if there is *no* sequence of vectors $s_1, \dots, s_{2n}, s_{2n+1} \in R$ for $n \ge 1$ such
that $s_1 - s_2 + s_3 - \dots - s_{2n} + s_{2n+1} = u \in \{0,1\}^k \setminus R$. (The same vector may appear
multiple times in this sum.) In other words: $R$ is balanced if one cannot find an odd-length
sequence of vectors in $R$ for which alternating between adding and subtracting these vectors
component-wise results in a 0/1-bitvector $u$ that is outside $R$. For example, the binary OR
relation $2-OR = \{0,1\}^2 \setminus \{(0,0)\}$ is *not* balanced, since $(0,1) - (1,1) + (1,0) = (0,0) \notin 2-OR$,
but the 1-in-3 relation $R_{=1} = \{(1,0,0), (0,1,0), (0,0,1)\}$ is. We prove that if a Boolean
relation $R$ is balanced, then it can efficiently be captured by a degree-1 polynomial and
the number of constraints that are applications of this relation can be reduced to $O(n)$.
Hence when all relations in a constraint language $\Gamma$ are balanced—we call such a constraint
language *balanced*—then CSP($\Gamma$) has a sparsification with $O(n)$ constraints. We also show
15:4 Best-Case and Worst-Case Sparsifiability of Boolean CSPs

that, on the other hand, if a Boolean relation *R* is not balanced, then there does not exist a
degree-1 polynomial over any ring that captures *R* in the sense required for application of the
polynomial framework. The property of being balanced is (as defined) a universal-algebraic
property; these results thus tightly bridge universal algebra and the polynomial framework.

**Characterizations.** The property of being balanced gives an easy way to prove that certain Boolean CSPs admit linear sparsifications. But perhaps more importantly, this characterization constructively exhibits a certain *witness* when a relation can *not* be captured by a degree-1 polynomial, in the form of the alternating sum of satisfying assignments that yield an unsatisfying assignment. In several scenarios, we can turn this witness structure against degree-1 polynomials into a lower bound proving that the problem does not have a linear sparsification. As a consequence, we can prove two fine-grained characterizations of sparsification complexity.

**Characterization of symmetric CSPs with a linear sparsification (Section 5)**

We say that a Boolean relation is *symmetric* if the satisfaction of a constraint only depends on the *number* of 1-values taken by the variables (the *weight* of the assignment), but does not depend on the *positions* where these values appear. For example, “1-in-*k*”-constraints are symmetric, just as “not-all-equal”-constraints, but the relation $R_{a \to b} = \{(0,0), (0,1), (1,1)\}$ corresponding to the truth value of $a \to b$ is not. We prove that if a symmetric Boolean relation *R* is not balanced, then it can implement (Definition 2.7) a binary OR using constants and negations but without having to introduce fresh variables. Building on this, we prove that if such an unbalanced symmetric relation *R* occurs in a constraint language $\Gamma$ for which CSP($\Gamma$) is NP-complete, then CSP($\Gamma$) does *not* admit a sparsification of size $O(n^{2-\epsilon})$ for any $\epsilon > 0$. Consequently, we obtain a characterization of the sparsification complexity of NP-complete Boolean CSPs whose constraint language consists of symmetric relations: there is a linear sparsification if and only if the constraint language is balanced. This yields linear sparsifications in several new scenarios that were not known before.

**Characterization of sparsification complexity for CSPs of low arity (Section 6)**

By combining the linear sparsifications guaranteed by balanced constraint languages with the
nontrivial sparsification when the largest-arity relations do not have exactly one falsifying
assignment, we obtain an exact characterization of the optimal sparsification size for all
Boolean CSPs where each relation has arity at most three. For a Boolean constraint language $\Gamma$
consisting of relations of arity at most three, we characterize the sparsification complexity
of $\Gamma$ as an integer $k \in \{1, 2, 3\}$ that represents the largest OR that $\Gamma$ can implement using
constants and negations, but without introducing fresh variables. Then we prove that CSP($\Gamma$)
has a sparsification of size $O(n^k)$, but no sparsification of size $O(n^{k-\epsilon})$ for any $\epsilon > 0$, giving
matching upper and lower bounds. Hence for all Boolean CSPs with constraints of arity at
most three, the polynomial-based framework gives provably *optimal* sparsifications.

2 Preliminaries

For a positive integer $n$, define $[n] := \{1, 2, \dots, n\}$. For an integer $q$, we let $\mathbb{Z}/q\mathbb{Z}$ denote the integers modulo $q$. These form a field if $q$ is prime, and a ring otherwise. We will use $x \equiv_q y$ to denote that $x$ and $y$ are congruent modulo $q$, and $x \not\equiv_q y$ to denote that they are incongruent modulo $q$. For statements marked with a star (★), the (full) proof can be found in the full version [4].
15:4 Best-Case and Worst-Case Sparsifiability of Boolean CSPs

that, on the other hand, if a Boolean relation *R* is not balanced, then there does not exist a
degree-1 polynomial over any ring that captures *R* in the sense required for application of the
polynomial framework. The property of being balanced is (as defined) a universal-algebraic
property; these results thus tightly bridge universal algebra and the polynomial framework.

**Characterizations.** The property of being balanced gives an easy way to prove that certain Boolean CSPs admit linear sparsifications. But perhaps more importantly, this characterization constructively exhibits a certain *witness* when a relation can *not* be captured by a degree-1 polynomial, in the form of the alternating sum of satisfying assignments that yield an unsatisfying assignment. In several scenarios, we can turn this witness structure against degree-1 polynomials into a lower bound proving that the problem does not have a linear sparsification. As a consequence, we can prove two fine-grained characterizations of sparsification complexity.

**Characterization of symmetric CSPs with a linear sparsification (Section 5)**

We say that a Boolean relation is *symmetric* if the satisfaction of a constraint only depends on the *number* of 1-values taken by the variables (the *weight* of the assignment), but does not depend on the *positions* where these values appear. For example, “1-in-*k*”-constraints are symmetric, just as “not-all-equal”-constraints, but the relation $R_{a \to b} = \{(0,0), (0,1), (1,1)\}$ corresponding to the truth value of $a \to b$ is not. We prove that if a symmetric Boolean relation *R* is not balanced, then it can implement (Definition 2.7) a binary OR using constants and negations but without having to introduce fresh variables. Building on this, we prove that if such an unbalanced symmetric relation *R* occurs in a constraint language $\Gamma$ for which CSP($\Gamma$) is NP-complete, then CSP($\Gamma$) does *not* admit a sparsification of size $O(n^{2-\epsilon})$ for any $\epsilon > 0$. Consequently, we obtain a characterization of the sparsification complexity of NP-complete Boolean CSPs whose constraint language consists of symmetric relations: there is a linear sparsification if and only if the constraint language is balanced. This yields linear sparsifications in several new scenarios that were not known before.

**Characterization of sparsification complexity for CSPs of low arity (Section 6)**

By combining the linear sparsifications guaranteed by balanced constraint languages with the
nontrivial sparsification when the largest-arity relations do not have exactly one falsifying
assignment, we obtain an exact characterization of the optimal sparsification size for all
Boolean CSPs where each relation has arity at most three. For a Boolean constraint language $\Gamma$
consisting of relations of arity at most three, we characterize the sparsification complexity
of $\Gamma$ as an integer $k \in \{1, 2, 3\}$ that represents the largest OR that $\Gamma$ can implement using
constants and negations, but without introducing fresh variables. Then we prove that CSP($\Gamma$)
has a sparsification of size $O(n^k)$, but no sparsification of size $O(n^{k-\epsilon})$ for any $\epsilon > 0$, giving
matching upper and lower bounds. Hence for all Boolean CSPs with constraints of arity at
most three, the polynomial-based framework gives provably *optimal* sparsifications.

2 Preliminaries

For a positive integer $n$, define $[n] := \{1, 2, \dots, n\}$. For an integer $q$, we let $\mathbb{Z}/q\mathbb{Z}$ denote the integers modulo $q$. These form a field if $q$ is prime, and a ring otherwise. We will use $x \equiv_q y$ to denote that $x$ and $y$ are congruent modulo $q$, and $x \not\equiv_q y$ to denote that they are incongruent modulo $q$. For statements marked with a star (★), the (full) proof can be found in the full version [4].
**Parameterized complexity.** A parameterized problem $\mathcal{Q}$ is a subset of $\Sigma^* \times \mathbb{N}$, where $\Sigma$ is a finite alphabet. Let $\mathcal{Q}, \mathcal{Q}' \subseteq \Sigma^* \times \mathbb{N}$ be parameterized problems and let $h: \mathbb{N} \to \mathbb{N}$ be a computable function. A generalized kernel for $\mathcal{Q}$ into $\mathcal{Q}'$ of size $h(k)$ is an algorithm that, on input $(x, k) \in \Sigma^* \times \mathbb{N}$, takes time polynomial in $|x| + k$ and outputs an instance $(x', k')$ such that: (i) $|x'|$ and $k'$ are bounded by $h(k)$, and (ii) $(x', k') \in \mathcal{Q}'$ if and only if $(x, k) \in \mathcal{Q}$. The algorithm is a kernel for $\mathcal{Q}$ if $\mathcal{Q}' = \mathcal{Q}$.

Since a polynomial-time reduction to an equivalent sparse instance yields a generalized kernel, lower bounds against generalized kernels can be used to prove the non-existence of such sparsification algorithms. To relate the sparsifiability of different problems to each other, the following notion is useful.

**Definition 2.1.** Let $\mathcal{P}, \mathcal{Q} \subseteq \Sigma^* \times \mathbb{N}$ be two parameterized problems. A linear-parameter transformation from $\mathcal{P}$ to $\mathcal{Q}$ is a polynomial-time algorithm that, given an instance $(x, k) \in \Sigma^* \times \mathbb{N}$ of $\mathcal{P}$, outputs an instance $(x', k') \in \Sigma^* \times \mathbb{N}$ of $\mathcal{Q}$ such that the following holds:

1. $(x, k) \in \mathcal{Q}$ if and only if $(x', k') \in \mathcal{P}$, and

2. $k' \in \mathcal{O}(k)$.

It is well-known [1, 2] that the existence of a linear-parameter transformation from problem $\mathcal{P}$ to $\mathcal{Q}$ implies that any generalized kernelization lower bound for $\mathcal{P}$, also holds for $\mathcal{Q}$.

**Operations, relations, and preservation.** A Boolean operation is a mapping from $\{0, 1\}^k$ to $\{0, 1\}$, where $k$ is a natural number, is said to be the *arity* of the operation; we assume throughout that operations have positive *arity*. From here, we define a *partial Boolean operation* in the usual way, that is, it is a mapping from a subset of $\{0, 1\}^k$ to $\{0, 1\}$. We say that a partial Boolean operation $f$ of *arity* $k$ is *idempotent* if $f(0, \dots, 0) = 0$ and $f(1, \dots, 1) = 1$; and, *self-dual* if for all $(a_1, \dots, a_k) \in \{0, 1\}^k$, when $f(a_1, \dots, a_k)$ is defined, it holds that $f(\neg a_1, \dots, \neg a_k)$ is defined and $f(a_1, \dots, a_k) = \neg f(\neg a_1, \dots, \neg a_k)$.

**Definition 2.2.** A partial Boolean operation $f: \{0, 1\}^k \to \{0, 1\}$ is *balanced* if there exist integer values $\alpha_1, \dots, \alpha_k$, called the *coefficients* of $f$, such that

$$ \sum_{i \in [k]} \alpha_i = 1, $$

$$ (x_1, \dots, x_k) \text{ is in the domain of } f \text{ if and only if } \sum_{i \in [k]} \alpha_i x_i \in \{0, 1\}, \text{ and} $$

$$ f(x_1, \dots, x_k) = \sum_{i \in [k]} \alpha_i x_i \text{ for all tuples in its domain.} $$

A relation over the set $D$ is a subset of $D^k$; here, $k$ is a natural number called the *arity* of the relation. Throughout, we assume that each relation is over a finite set $D$. A Boolean relation is a relation over $\{0, 1\}$.

**Definition 2.3.** For each $k \ge 1$, we use $k$-OR to denote the relation $\{0, 1\}^k \setminus \{(0, \dots, 0)\}$.

A constraint language over $D$ is a finite set of relations over $D$; a Boolean constraint language is a constraint language over $\{0, 1\}$. For a Boolean constraint language $\Gamma$, we define CSP($\Gamma$) as follows.

**CSP($\Gamma$)**

**Parameter:** The number of variables $|V|$.

**Input:** A tuple $(C, V)$, where $C$ is a finite set of constraints, $V$ is a finite set of variables, and each constraint is a pair $R(x_1, \dots, x_k)$ for $R \in \Gamma$ and $x_1, \dots, x_k \in V$.

**Question:** Does there exist a *satisfying assignment*, that is, an assignment $f: V \to \{0, 1\}$ such that for each constraint $R(x_1, \dots, x_k) \in C$ it holds that $(f(x_1), \dots, f(x_k)) \in R$?

Let $f: \{0, 1\}^k \to \{0, 1\}$ be a partial Boolean operation, and let $T \subseteq \{0, 1\}^n$ be a Boolean relation. We say that $T$ is *preserved* by $f$ when, for any tuples $t^1 = (t_1^1, \dots, t_n^1), \dots, t^k = (t_1^k, \dots, t_n^k) \in T$, $f(t^1) \in \{0, 1\}^n$.
**Parameterized complexity.** A parameterized problem $\mathcal{Q}$ is a subset of $\Sigma^* \times \mathbb{N}$, where $\Sigma$ is a finite alphabet. Let $\mathcal{Q}, \mathcal{Q}' \subseteq \Sigma^* \times \mathbb{N}$ be parameterized problems and let $h: \mathbb{N} \to \mathbb{N}$ be a computable function. A generalized kernel for $\mathcal{Q}$ into $\mathcal{Q}'$ of size $h(k)$ is an algorithm that, on input $(x, k) \in \Sigma^* \times \mathbb{N}$, takes time polynomial in $|x| + k$ and outputs an instance $(x', k')$ such that: (i) $|x'|$ and $k'$ are bounded by $h(k)$, and (ii) $(x', k') \in \mathcal{Q}'$ if and only if $(x, k) \in \mathcal{Q}$. The algorithm is a kernel for $\mathcal{Q}$ if $\mathcal{Q}' = \mathcal{Q}$.

Since a polynomial-time reduction to an equivalent sparse instance yields a generalized kernel, lower bounds against generalized kernels can be used to prove the non-existence of such sparsification algorithms. To relate the sparsifiability of different problems to each other, the following notion is useful.

**Definition 2.1.** Let $\mathcal{P}, \mathcal{Q} \subseteq \Sigma^* \times \mathbb{N}$ be two parameterized problems. A linear-parameter transformation from $\mathcal{P}$ to $\mathcal{Q}$ is a polynomial-time algorithm that, given an instance $(x, k) \in \Sigma^* \times \mathbb{N}$ of $\mathcal{P}$, outputs an instance $(x', k') \in \Sigma^* \times \mathbb{N}$ of $\mathcal{Q}$ such that the following holds:

1. $(x, k) \in \mathcal{Q}$ if and only if $(x', k') \in \mathcal{P}$, and

2. $k' \in \mathcal{O}(k)$.

It is well-known [1, 2] that the existence of a linear-parameter transformation from problem $\mathcal{P}$ to $\mathcal{Q}$ implies that any generalized kernelization lower bound for $\mathcal{P}$, also holds for $\mathcal{Q}$.

**Operations, relations, and preservation.** A Boolean operation is a mapping from $\{0, 1\}^k$ to $\{0, 1\}$, where $k$ is a natural number, is said to be the *arity* of the operation; we assume throughout that operations have positive *arity*. From here, we define a *partial Boolean operation* in the usual way, that is, it is a mapping from a subset of $\{0, 1\}^k$ to $\{0, 1\}$. We say that a partial Boolean operation $f$ of *arity* $k$ is *idempotent* if $f(0, \dots, 0) = 0$ and $f(1, \dots, 1) = 1$; and, *self-dual* if for all $(a_1, \dots, a_k) \in \{0, 1\}^k$, when $f(a_1, \dots, a_k)$ is defined, it holds that $f(\neg a_1, \dots, \neg a_k)$ is defined and $f(a_1, \dots, a_k) = \neg f(\neg a_1, \dots, \neg a_k)$.

**Definition 2.2.** A partial Boolean operation $f: \{0, 1\}^k \to \{0, 1\}$ is *balanced* if there exist integer values $\alpha_1, \dots, \alpha_k$, called the *coefficients* of $f$, such that

$$ \sum_{i \in [k]} \alpha_i = 1, $$

$$ (x_1, \dots, x_k) \text{ is in the domain of } f \text{ if and only if } \sum_{i \in [k]} \alpha_i x_i \in \{0, 1\}, \text{ and} $$

$$ f(x_1, \dots, x_k) = \sum_{i \in [k]} \alpha_i x_i \text{ for all tuples in its domain.} $$

A relation over the set $D$ is a subset of $D^k$; here, $k$ is a natural number called the *arity* of the relation. Throughout, we assume that each relation is over a finite set $D$. A Boolean relation is a relation over $\{0, 1\}$.

**Definition 2.3.** For each $k \ge 1$, we use $k$-OR to denote the relation $\{0, 1\}^k \setminus \{(0, \dots, 0)\}$.

A constraint language over $D$ is a finite set of relations over $D$; a Boolean constraint language is a constraint language over $\{0, 1\}$. For a Boolean constraint language $\Gamma$, we define CSP($\Gamma$) as follows.

**CSP($\Gamma$)**

**Parameter:** The number of variables $|V|$.

**Input:** A tuple $(C, V)$, where $C$ is a finite set of constraints, $V$ is a finite set of variables, and each constraint is a pair $R(x_1, \dots, x_k)$ for $R \in \Gamma$ and $x_1, \dots, x_k \in V$.

**Question:** Does there exist a *satisfying assignment*, that is, an assignment $f: V \to \{0, 1\}$ such that for each constraint $R(x_1, \dots, x_k) \in C$ it holds that $(f(x_1), \dots, f(x_k)) \in R$?

Let $f: \{0, 1\}^k \to \{0, 1\}$ be a partial Boolean operation, and let $T \subseteq \{0, 1\}^n$ be a Boolean relation. We say that $T$ is *preserved* by $f$ when, for any tuples $t^1 = (t_1^1, \dots, t_n^1), \dots, t^k = (t_1^k, \dots, t_n^k) \in T$, $f(t^1) \in \{0, 1\}^n$.
15:6 Best-Case and Worst-Case Sparsifiability of Boolean CSPs

$(t_1^k, \dots, t_n^k) \in T$, if all entries of the tuple $(f(t_1^1, \dots, t_1^k), \dots, f(t_n^1, \dots, t_n^k))$ are defined, then this tuple is in $T$. We say that a Boolean constraint language $\Gamma$ is *preserved* by $f$ if each relation in $\Gamma$ is preserved by $f$. We say that a Boolean relation is *balanced* if it is preserved by all balanced operations, and that a Boolean constraint language is *balanced* if each relation therein is balanced.

Define an *alternating operation* to be a balanced operation $f: \{0,1\}^k \to \{0,1\}$ such that $k$ is odd and the coefficients alternate between +1 and -1, so that $\alpha_1 = +1$, $\alpha_2 = -1$, $\alpha_3 = +1$, ..., $\alpha_k = +1$. We have the following.

**Proposition 2.4 (★)**. A Boolean relation $R$ is balanced if and only if for all odd $k \ge 1$, the relation $R$ is preserved by the alternating operation of arity $k$.

We will use the following straightforwardly verified fact tacitly, throughout.

**Observation 2.5.** Each balanced operation is idempotent and self-dual.

For $b \in \{0,1\}$, let $u_b: \{0,1\} \to \{0,1\}$ be the unary operation defined by $u_b(0) = u_b(1) = b$; let **major**: $\{0,1\}^3 \to \{0,1\}$ to be the operation defined by **major**($x, y, z$) = $(x \land y) \lor (x \land z) \lor (y \land z$); and, let **minor**: $\{0,1\}^3 \to \{0,1\}$ to be the operation defined by **minor**($x, y, z$) = $x \oplus y \oplus z$, where $\oplus$ denotes exclusive OR. We say that a Boolean constraint language $\Gamma$ is *tractable* if it is preserved by one of the six following operations: $u_0, u_1, \land, \lor, \text{minor}, \text{major}$; we say that $\Gamma$ is *intractable* otherwise. It is known that, in terms of classical complexity, the problem CSP($\Gamma$) is polynomial-time decidable when $\Gamma$ is tractable, and that the problem CSP($\Gamma$) is NP-complete when $\Gamma$ is intractable (see [3] for a proof; in particular, refer there to the proof of Theorem 3.21).

Constraint Satisfaction and Definability.

**Assumption 2.6.** By default, we assume in the sequel that the operations, relations, and constraint languages under discussion are Boolean, and that said operations and relations are of positive arity. We nonetheless sometimes describe them as being Boolean, for emphasis.

**Definition 2.7.** Let us say that a Boolean relation $T$ of arity $m$ is *cone-definable* from a Boolean relation $U$ of arity $n$ if there exists a tuple $(y_1, \dots, y_n)$ where:

- for each $j \in [n]$, it holds that $y_j$ is an element of $\{0,1\} \cup \{x_1, \dots, x_m\} \cup \{\neg x_1, \dots, \neg x_m\}$;

- for each $i \in [m]$, there exists $j \in [n]$ such that $y_j \in \{x_i, \neg x_i\}$; and,

- for each $f: \{x_1, \dots, x_m\} \to \{0,1\}$, it holds that $(f(x_1), \dots, f(x_m)) \in T$ if and only if $(\hat{f}(y_1), \dots, \hat{f}(y_n)) \in U$. Here, $\hat{f}$ denotes the natural extension of $f$ where $\hat{f}(0) = 0$, $\hat{f}(1) = 1$, and $\hat{f}(\neg x_i) = \neg f(x_i)$.

(The prefix cone indicates the allowing of constants and negation.)

**Example 2.8.** Let $R = \{(0,0), (0,1)\}$ and let $S = \{(0,1), (1,1)\}$. We have that $R$ is cone-definable from $S$ via the tuple $(\neg x_2, \neg x_1)$; also, $S$ is cone-definable from $R$ via the same tuple.

When $\Gamma$ is a constraint language over $D$, we use $\Gamma^*$ to denote the expansion of $\Gamma$ where each element of $D$ appears as a relation, that is, we define $\Gamma^*$ as $\Gamma \cup \{(d) \mid d \in D\}$.

The following is a key property of cone-definability; it states that relations that are cone-definable from a constraint language $\Gamma$ may be simulated by the constraint language, and thus used to prove hardness results for CSP($\Gamma$).

**Proposition 2.9 (★).** Suppose that $\Gamma$ is an intractable constraint language, and that $\Delta$ is a constraint language such that each relation in $\Delta$ is cone-definable from a relation in $\Gamma$. Then, there exists a linear-parameter transformation from CSP($\Gamma^* \cup \Delta$) to CSP($\Gamma$).
15:6 Best-Case and Worst-Case Sparsifiability of Boolean CSPs

$(t_1^k, \dots, t_n^k) \in T$, if all entries of the tuple $(f(t_1^1, \dots, t_1^k), \dots, f(t_n^1, \dots, t_n^k))$ are defined, then this tuple is in $T$. We say that a Boolean constraint language $\Gamma$ is *preserved* by $f$ if each relation in $\Gamma$ is preserved by $f$. We say that a Boolean relation is *balanced* if it is preserved by all balanced operations, and that a Boolean constraint language is *balanced* if each relation therein is balanced.

Define an *alternating operation* to be a balanced operation $f: \{0,1\}^k \to \{0,1\}$ such that $k$ is odd and the coefficients alternate between $+1$ and $-1$, so that $\alpha_1 = +1, \alpha_2 = -1, \alpha_3 = +1, \dots, \alpha_k = +1$. We have the following.

**Proposition 2.4 (★)**. A Boolean relation $R$ is balanced if and only if for all odd $k \ge 1$, the relation $R$ is preserved by the alternating operation of arity $k$.

We will use the following straightforwardly verified fact tacitly, throughout.

**Observation 2.5.** Each balanced operation is idempotent and self-dual.

For $b \in \{0,1\}$, let $u_b: \{0,1\} \to \{0,1\}$ be the unary operation defined by $u_b(0) = u_b(1) = b$; let **major**: $\{0,1\}^3 \to \{0,1\}$ to be the operation defined by **major**$(x, y, z) = (x \land y) \lor (x \land z) \lor (y \land z)$; and, let **minor**: $\{0,1\}^3 \to \{0,1\}$ to be the operation defined by **minor**$(x, y, z) = x \oplus y \oplus z$, where $\oplus$ denotes exclusive OR. We say that a Boolean constraint language $\Gamma$ is *tractable* if it is preserved by one of the six following operations: $u_0, u_1, \land, \lor, \text{minor}, \text{major}$; we say that $\Gamma$ is *intractable* otherwise. It is known that, in terms of classical complexity, the problem CSP($\Gamma$) is polynomial-time decidable when $\Gamma$ is tractable, and that the problem CSP($\Gamma$) is NP-complete when $\Gamma$ is intractable (see [3] for a proof; in particular, refer there to the proof of Theorem 3.21).

Constraint Satisfaction and Definability.

**Assumption 2.6.** By default, we assume in the sequel that the operations, relations, and constraint languages under discussion are Boolean, and that said operations and relations are of positive arity. We nonetheless sometimes describe them as being Boolean, for emphasis.

**Definition 2.7.** Let us say that a Boolean relation $T$ of arity $m$ is *cone-definable* from a Boolean relation $U$ of arity $n$ if there exists a tuple $(y_1, \dots, y_n)$ where:

- for each $j \in [n]$, it holds that $y_j$ is an element of $\{0,1\} \cup \{x_1, \dots, x_m\} \cup \{\neg x_1, \dots, \neg x_m\}$;

- for each $i \in [m]$, there exists $j \in [n]$ such that $y_j \in \{x_i, \neg x_i\}$; and,

- for each $f: \{x_1, \dots, x_m\} \to \{0,1\}$, it holds that $(f(x_1), \dots, f(x_m)) \in T$ if and only if $(\hat{f}(y_1), \dots, \hat{f}(y_n)) \in U$. Here, $\hat{f}$ denotes the natural extension of $f$ where $\hat{f}(0) = 0$, $\hat{f}(1) = 1$, and $\hat{f}(\neg x_i) = \neg f(x_i)$.

(The prefix cone indicates the allowing of constants and negation.)

**Example 2.8.** Let $R = \{(0,0), (0,1)\}$ and let $S = \{(0,1), (1,1)\}$. We have that $R$ is cone-definable from $S$ via the tuple $(\neg x_2, \neg x_1)$; also, $S$ is cone-definable from $R$ via the same tuple.

When $\Gamma$ is a constraint language over $D$, we use $\Gamma^*$ to denote the expansion of $\Gamma$ where each element of $D$ appears as a relation, that is, we define $\Gamma^*$ as $\Gamma \cup \{(\{d\} | d \in D)\}$.

The following is a key property of cone-definability; it states that relations that are cone-definable from a constraint language $\Gamma$ may be simulated by the constraint language, and thus used to prove hardness results for CSP($\Gamma$).

**Proposition 2.9 (★).** Suppose that $\Gamma$ is an intractable constraint language, and that $\Delta$ is a constraint language such that each relation in $\Delta$ is cone-definable from a relation in $\Gamma$. Then, there exists a linear-parameter transformation from CSP($\Gamma^* \cup \Delta$) to CSP($\Gamma$).
### 3 Trivial versus non-trivial sparsification

It is well known that k-CNF-SAT allows no non-trivial sparsification, for each $k \ge 3$ [7]. This means that we cannot efficiently reduce the number of clauses in such a formula to $O(n^{k-\epsilon})$. The k-or relation is special, in the sense that there is exactly one k-tuple that is not contained in the relation. We show in this section that when considering k-ary relations for which there is more than one k-tuple not contained in the relation, a non-trivial sparsification is always possible. In particular, the number of constraints of any input can efficiently be reduced to $O(n^{k-1})$. Using Lemmas 3.4 and 3.6, we will completely classify the constraint languages that allow a non-trivial sparsification as follows.

**Theorem 3.1 (★).** Let $\Gamma$ be an intractable (Boolean) constraint language. Let $k$ be the maximum arity of any relation $R \in \Gamma$. The following dichotomy holds.

- If for all $R \in \Gamma$ it holds that $|R| \ne 2^k - 1$, then CSP($\Gamma$) has a kernel with $O(n^{k-1})$ constraints that can be stored in $O(n^{k-1} \log n)$ bits.

- If there exists $R \in \Gamma$ with $|R| = 2^k - 1$, then CSP($\Gamma$) has no generalized kernel of bitsize $O(n^{k-\epsilon})$ for any $\epsilon > 0$, unless NP $\subseteq$ coNP/poly.

To obtain the kernels given in this section, we will heavily rely on the following notion for representing constraints by polynomials.

**Definition 3.2.** Let $R$ be a $k$-ary Boolean relation. We say that a polynomial $p_u$ over a ring $E_u$ captures an unsatisfying assignment $u \in \{0, 1\}^k \setminus R$ with respect to $R$, if the following two conditions hold over $E_u$.

$$p_u(x_1, \dots, x_k) = 0 \text{ for all } (x_1, \dots, x_k) \in R, \text{ and} \quad (1)$$

$$p_u(u_1, \dots, u_k) \ne 0. \quad (2)$$

The following Theorem is a generalization of Theorem 16 in [13]. The main improvement is that we now allow the usage of different polynomials, over different rings, for each $u \notin R$. Previously, all polynomials had to be given over the same ring, and each constraint was captured by a single polynomial.

**Theorem 3.3 (★).** Let $R \subseteq \{0, 1\}^k$ be a fixed $k$-ary relation, such that for every $u \in \{0, 1\}^k \setminus R$ there exists a ring $E_u \in \{\mathbb{Q}\} \cup \{\mathbb{Z}/q_u\mathbb{Z} \mid q_u \text{ is a prime power}\}$ and polynomial $p_u$ over $E_u$ of degree at most $d$ that captures $u$ with respect to $R$. Then there exists a polynomial-time algorithm that, given a set of constraints $C$ over $\{R\}$ over $n$ variables, outputs $C' \subseteq C$ with $|C'| = O(n^d)$, such that any Boolean assignment satisfies all constraints in $C$ if and only if it satisfies all constraints in $C'$.

The next lemma states that any $k$-ary Boolean relation $R$ with $|R| < 2^k - 1$ admits a non-trivial sparsification. To prove the lemma, we show that such relations can be represented by polynomials of degree at most $k-1$, such that the sparsification can be obtained using Theorem 3.3. Since relations with $|R| = 2^k$ have a sparsification of size $O(1)$, as constraints over such relations are satisfied by any assignment, it will follow that $k$-ary relations with $|\{0, 1\}^k \setminus R| \ne 1$ always allow a non-trivial sparsification.

**Lemma 3.4 (★).** Let $R$ be a $k$-ary Boolean relation with $|R| < 2^k - 1$. Let $C$ be a set of constraints over $\{R\}$, using $n$ variables. Then there exists a polynomial-time algorithm that outputs $C' \subseteq C$ with $|C'| = O(n^{k-1})$, such that a Boolean assignment satisfies all constraints in $C'$ if and only if it satisfies all constraints in $C$.
### 3 Trivial versus non-trivial sparsification

It is well known that $k$-CNF-SAT allows no non-trivial sparsification, for each $k \ge 3$ [7]. This means that we cannot efficiently reduce the number of clauses in such a formula to $O(n^{k-\epsilon})$. The $k$-OR relation is special, in the sense that there is exactly one $k$-tuple that is not contained in the relation. We show in this section that when considering $k$-ary relations for which there is more than one $k$-tuple not contained in the relation, a non-trivial sparsification is always possible. In particular, the number of constraints of any input can efficiently be reduced to $O(n^{k-1})$. Using Lemmas 3.4 and 3.6, we will completely classify the constraint languages that allow a non-trivial sparsification as follows.

**Theorem 3.1 (★).** Let $\Gamma$ be an intractable (Boolean) constraint language. Let $k$ be the maximum arity of any relation $R \in \Gamma$. The following dichotomy holds.

- If for all $R \in \Gamma$ it holds that $|R| \ne 2^k - 1$, then CSP($\Gamma$) has a kernel with $O(n^{k-1})$ constraints that can be stored in $O(n^{k-1} \log n)$ bits.

- If there exists $R \in \Gamma$ with $|R| = 2^k - 1$, then CSP($\Gamma$) has no generalized kernel of bitsize $O(n^{k-\epsilon})$ for any $\epsilon > 0$, unless $\mathrm{NP} \subseteq \mathrm{coNP/poly}$.

To obtain the kernels given in this section, we will heavily rely on the following notion for representing constraints by polynomials.

**Definition 3.2.** Let $R$ be a $k$-ary Boolean relation. We say that a polynomial $p_u$ over a ring $E_u$ captures an unsatisfying assignment $u \in \{0, 1\}^k \setminus R$ with respect to $R$, if the following two conditions hold over $E_u$.

$$p_u(x_1, \dots, x_k) = 0 \text{ for all } (x_1, \dots, x_k) \in R, \text{ and} \quad (1)$$

$$p_u(u_1, \dots, u_k) \ne 0. \quad (2)$$

The following Theorem is a generalization of Theorem 16 in [13]. The main improvement is that we now allow the usage of different polynomials, over different rings, for each $u \notin R$. Previously, all polynomials had to be given over the same ring, and each constraint was captured by a single polynomial.

**Theorem 3.3 (★).** Let $R \subseteq \{0, 1\}^k$ be a fixed $k$-ary relation, such that for every $u \in \{0, 1\}^k \setminus R$ there exists a ring $E_u \in \{\mathbb{Q}\} \cup \{\mathbb{Z}/q_u\mathbb{Z} \mid q_u \text{ is a prime power}\}$ and polynomial $p_u$ over $E_u$ of degree at most $d$ that captures $u$ with respect to $R$. Then there exists a polynomial-time algorithm that, given a set of constraints $C$ over $\{R\}$ over $n$ variables, outputs $C' \subseteq C$ with $|C'| = O(n^d)$, such that any Boolean assignment satisfies all constraints in $C$ if and only if it satisfies all constraints in $C'$.

The next lemma states that any $k$-ary Boolean relation $R$ with $|R| < 2^k - 1$ admits a non-trivial sparsification. To prove the lemma, we show that such relations can be represented by polynomials of degree at most $k-1$, such that the sparsification can be obtained using Theorem 3.3. Since relations with $|R| = 2^k$ have a sparsification of size $O(1)$, as constraints over such relations are satisfied by any assignment, it will follow that $k$-ary relations with $|\{0, 1\}^k \setminus R| \ne 1$ always allow a non-trivial sparsification.

**Lemma 3.4 (★).** Let $R$ be a $k$-ary Boolean relation with $|R| < 2^k - 1$. Let $C$ be a set of constraints over $\{R\}$, using $n$ variables. Then there exists a polynomial-time algorithm that outputs $C' \subseteq C$ with $|C'| = O(n^{k-1})$, such that a Boolean assignment satisfies all constraints in $C'$ if and only if it satisfies all constraints in $C$.
15:8 Best-Case and Worst-Case Sparsifiability of Boolean CSPs

**Proof sketch.** We will show that for every $u \in \{0,1\}^k \setminus R$, there exists a degree-(k-1) polynomial $p_u$ over $\mathbb{Q}$ that captures $u$, such that the result follows from Theorem 3.3. We will prove the existence of such a polynomial by induction on $k$. For $k=1$, the lemma statement implies that $R = \emptyset$. Thereby, for any $u \notin R$, we simply choose $p_u(x_1) := 1$. This polynomial satisfies the requirements, and has degree 0. Let $k > 1$ and let $u = (u_1, \dots, u_k) \in \{0,1\}^k \setminus R$. Since $|R| < 2^k - 1$, we can choose $w = (w_1, \dots, w_k)$ such that $w \in \{0,1\}^k \setminus R$ and $w \neq u$. We distinguish two cases, depending on whether $u$ and $w$ agree on some position.

Suppose $u_i \neq w_i$ for all $i$, and assume for concreteness that $u = (0, \dots, 0)$ and $w = (1, \dots, 1)$. Then the polynomial $p_u(x_1, \dots, x_k) := \prod_{i=1}^{k-1} (i - \sum_{j=1}^k x_j)$ suffices: $p_u(0, \dots, 0) = \prod_{j=1}^{k-1} j \neq 0$, while for any $(x_1, \dots, x_k) \in R$, it holds that $\sum_{i=1}^k x_i \in [k-1]$ and thereby $p_u(x_1, \dots, x_k) = 0$; the product has a 0-term. Other values of $u$ and $w$ are handled similarly.

Now suppose $u_i = w_i$ for some $i \in [k]$, and assume for concreteness that $u_1 = w_1 = 1$. Define $R' := \{(x_2, \dots, x_k) | (1, x_2, \dots, x_k) \in R\}$ and let $u' := (u_2, \dots, u_k)$. Since $(u_2, \dots, u_k)$ and $(w_2, \dots, w_k)$ are distinct tuples not in $R'$, by induction there is a polynomial $p_{u'}$ of degree $k-2$ that captures $u'$ with respect to $R'$. Then the polynomial $p_u(x_1, \dots, x_k) := x_1 \cdot p_{u'}(x_2, \dots, x_k)$ has degree $k-1$ and captures $u$ with respect to $R$. $\quad$

To show the other part of the dichotomy, we will need the following theorem.

**▶ Theorem 3.5 (★).** Let $\Gamma$ be an intractable (Boolean) constraint language, and let $k \ge 1$. If there exists $R \in \Gamma$ such that $R$ cone-defines $k$-OR, then CSP($\Gamma$) does not have a generalized kernel of size $O(n^{k-\epsilon})$, unless $NP \subseteq \text{coNP/poly}$.

The next lemma formalizes the idea that any $k$-ary relation with $|\{0,1\}^k \setminus R| = 1$ is equivalent to $k$-OR, up to negation of variables. The proof of the dichotomy given in Theorem 3.1 will follow from Lemma 3.4, together with the next lemma and Theorem 3.5.

**▶ Lemma 3.6 (★).** Let $R$ be a $k$-ary relation with $|R| = 2^k - 1$. Then $R$ cone-defines $k$-OR.

4 From balanced operations to linear sparsification

The main result of this section is the following theorem, which we prove below.

**▶ Theorem 4.1.** Let $\Gamma$ be a balanced (Boolean) constraint language. Then CSP($\Gamma$) has a kernel with $O(n)$ constraints that are a subset of the original constraints. The kernel can be stored using $O(n \log n)$ bits.

To prove the theorem, we will use two additional technical lemmas. To state them, we introduce some notions from linear algebra. Given a set $S = \{s_1, \dots, s_n\}$ of $k$-ary vectors in $\mathbb{Z}^k$, we define $\text{span}_Z(S)$ as the set of all vectors $y$ in $\mathbb{Z}^k$ for which there exist $\alpha_1, \dots, \alpha_n \in \mathbb{Z}$ such that $y = \sum_{i \in [n]} \alpha_i s_i$. Similarly, we define $\text{span}_q(S)$ as the set of all $k$-ary vectors $y$ over $\mathbb{Z}/q\mathbb{Z}$, such that there exist $\alpha_1, \dots, \alpha_n$ such that $y \equiv_q \sum_{i \in [n]} \alpha_i s_i$. For an $m \times n$ matrix $S$, we use $s_i$ for $i \in [m]$ to denote the $i$'th row of $S$.

**▶ Lemma 4.2 (★).** Let $S$ be an $m \times n$ integer matrix. Let $u \in \mathbb{Z}^n$ be a row vector. If $u \in \text{span}_q(\{s_1, \dots, s_m\})$ for all prime powers $q$, then $u \in \text{span}_Z(\{s_1, \dots, s_m\})$.

**▶ Lemma 4.3 (★).** Let $q$ be a prime power. Let $A$ be an $m \times n$ matrix over $\mathbb{Z}/q\mathbb{Z}$. Suppose there exists no constant $c \neq_q 0$ for which the system $Ax \equiv_q b$ has a solution, where $b := (0, \dots, 0, c)^T$ is the vector with $c$ on the last position and zeros in all other positions.
Then $a_m \in \text{span}_q(\{a_1, \dots, a_{m-1}\})$.
15:8 Best-Case and Worst-Case Sparsifiability of Boolean CSPs

**Proof sketch.** We will show that for every $u \in \{0,1\}^k \setminus R$, there exists a degree-(k-1) polynomial $p_u$ over $\mathbb{Q}$ that captures $u$, such that the result follows from Theorem 3.3. We will prove the existence of such a polynomial by induction on $k$. For $k=1$, the lemma statement implies that $R = \emptyset$. Thereby, for any $u \notin R$, we simply choose $p_u(x_1) := 1$. This polynomial satisfies the requirements, and has degree 0. Let $k > 1$ and let $u = (u_1, \dots, u_k) \in \{0,1\}^k \setminus R$. Since $|R| < 2^k - 1$, we can choose $w = (w_1, \dots, w_k)$ such that $w \in \{0,1\}^k \setminus R$ and $w \neq u$. We distinguish two cases, depending on whether $u$ and $w$ agree on some position.

Suppose $u_i \neq w_i$ for all $i$, and assume for concreteness that $u = (0, \dots, 0)$ and $w = (1, \dots, 1)$. Then the polynomial $p_u(x_1, \dots, x_k) := \prod_{i=1}^{k-1} (i - \sum_{j=1}^k x_j)$ suffices: $p_u(0, \dots, 0) = \prod_{j=1}^{k-1} j \neq 0$, while for any $(x_1, \dots, x_k) \in R$, it holds that $\sum_{i=1}^k x_i \in [k-1]$ and thereby $p_u(x_1, \dots, x_k) = 0$; the product has a 0-term. Other values of $u$ and $w$ are handled similarly.

Now suppose $u_i = w_i$ for some $i \in [k]$, and assume for concreteness that $u_1 = w_1 = 1$. Define $R' := \{(x_2, \dots, x_k) | (1, x_2, \dots, x_k) \in R\}$ and let $u' := (u_2, \dots, u_k)$. Since $(u_2, \dots, u_k)$ and $(w_2, \dots, w_k)$ are distinct tuples not in $R'$, by induction there is a polynomial $p_{u'}$ of degree $k-2$ that captures $u'$ with respect to $R'$. Then the polynomial $p_u(x_1, \dots, x_k) := x_1 \cdot p_{u'}(x_2, \dots, x_k)$ has degree $k-1$ and captures $u$ with respect to $R$. $\quad$

To show the other part of the dichotomy, we will need the following theorem.

**▶ Theorem 3.5 (★).** Let $\Gamma$ be an intractable (Boolean) constraint language, and let $k \ge 1$. If there exists $R \in \Gamma$ such that $R$ cone-defines $k$-OR, then CSP($\Gamma$) does not have a generalized kernel of size $O(n^{k-\epsilon})$, unless $\mathrm{NP} \subseteq \mathrm{coNP/poly}$.

The next lemma formalizes the idea that any $k$-ary relation with $|\{0,1\}^k \setminus R| = 1$ is equivalent to $k$-OR, up to negation of variables. The proof of the dichotomy given in Theorem 3.1 will follow from Lemma 3.4, together with the next lemma and Theorem 3.5.

**▶ Lemma 3.6 (★).** Let $R$ be a $k$-ary relation with $|R| = 2^k - 1$. Then $R$ cone-defines $k$-OR.

4 From balanced operations to linear sparsification

The main result of this section is the following theorem, which we prove below.

**▶ Theorem 4.1.** Let $\Gamma$ be a balanced (Boolean) constraint language. Then CSP($\Gamma$) has a kernel with $O(n)$ constraints that are a subset of the original constraints. The kernel can be stored using $O(n \log n)$ bits.

To prove the theorem, we will use two additional technical lemmas. To state them, we introduce some notions from linear algebra. Given a set $S = \{s_1, \dots, s_n\}$ of $k$-ary vectors in $\mathbb{Z}^k$, we define $\mathrm{span}_Z(S)$ as the set of all vectors $y$ in $\mathbb{Z}^k$ for which there exist $\alpha_1, \dots, \alpha_n \in \mathbb{Z}$ such that $y = \sum_{i \in [n]} \alpha_i s_i$. Similarly, we define $\mathrm{span}_q(S)$ as the set of all $k$-ary vectors $y$ over $\mathbb{Z}/q\mathbb{Z}$, such that there exist $\alpha_1, \dots, \alpha_n$ such that $y \equiv_q \sum_{i \in [n]} \alpha_i s_i$. For an $m \times n$ matrix $S$, we use $s_i$ for $i \in [m]$ to denote the $i$'th row of $S$.

**▶ Lemma 4.2 (★).** Let $S$ be an $m \times n$ integer matrix. Let $u \in \mathbb{Z}^n$ be a row vector. If $u \in \mathrm{span}_q(\{s_1, \dots, s_m\})$ for all prime powers $q$, then $u \in \mathrm{span}_Z(\{s_1, \dots, s_m\})$.

**▶ Lemma 4.3 (★).** Let $q$ be a prime power. Let $A$ be an $m \times n$ matrix over $\mathbb{Z}/q\mathbb{Z}$. Suppose there exists no constant $c \neq_q 0$ for which the system $Ax \equiv_q b$ has a solution, where $b := (0, \dots, 0, c)^T$ is the vector with $c$ on the last position and zeros in all other positions.
Then $a_m \in \mathrm{span}_q(\{a_1, \dots, a_{m-1}\})$.
Using these tools from linear algebra, we now prove the main sparsification result.

**Proof of Theorem 4.1.** We show that for all relations $R$ in the balanced constraint language $\Gamma$, for all $u \notin R$, there exists a linear polynomial $p_u$ over a ring $E_u \in \{\mathbb{Z}/q_u\mathbb{Z} | q_u$ is a prime power\} that captures $u$ with respect to $R$. By applying Theorem 3.3 once for each relation $R \in \Gamma$, to reduce the number of constraints involving $R$ to $O(n)$, we then reduce any $n$-variable instance of CSP($\Gamma$) to an equivalent one on $|\Gamma| \cdot O(n) \in O(n)$ constraints.

Suppose for a contradiction that there exists $R \in \Gamma$ and $u \notin R$, such that no prime power $q$ and polynomial $p$ over $\mathbb{Z}/q\mathbb{Z}$ exist that satisfy conditions (1) and (2). We can view the process of finding such a linear polynomial, as solving a set of linear equations whose unknowns are the coefficients of the polynomial. We have a linear equation for each evaluation of the polynomial for which we want to enforce a certain value.

Let $R = \{r_1, \dots, r_\ell\}$. By the non-existence of $p$ and $q$, the system

$$ \begin{pmatrix} 1 & r_{1,1} & r_{1,2} & \dots & r_{1,k} \\ 1 & r_{2,1} & r_{2,2} & \dots & r_{2,k} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & r_{\ell,1} & r_{\ell,2} & \dots & r_{\ell,k} \\ 1 & u_1 & u_2 & \dots & u_k \end{pmatrix} \begin{pmatrix} \alpha_0 \\ \alpha_1 \\ \alpha_2 \\ \vdots \\ \alpha_k \end{pmatrix} \equiv_q \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 0 \\ c \end{pmatrix} $$

has no solution for any prime power $q$ and $c \neq q \neq 0$. Otherwise, it is easy to verify that $q$ is the desired prime power and $p(x_1, \dots, x_k) := \alpha_0 + \sum_{i=1}^k \alpha_i x_i$ is the desired polynomial.

The fact that no solution exists, implies that $(1, u_1, \dots, u_k)$ is in the span of the remaining rows of the matrix, by Lemma 4.3. But this implies that for any prime power $q$, there exist coefficients $\beta_1, \dots, \beta_\ell$ over $\mathbb{Z}/q\mathbb{Z}$ such that $u \equiv_q \sum \beta_i r_i$. Furthermore, since the first column of the matrix is the all-ones column, we obtain that $\sum \beta_i \equiv_q 1$. By Lemma 4.2, it follows that there exist integer coefficients $\gamma_1, \dots, \gamma_\ell$ such that $\sum \gamma_i = 1$ and furthermore $u = \sum \gamma_i r_i$. But it immediately follows that $R \in \Gamma$ is not preserved by the balanced operation given by $f(x_1, \dots, x_\ell) := \sum \gamma_i x_i$, which contradicts the assumption that $\Gamma$ is balanced. ◀

The kernelization result above is obtained by using the fact that when $\Gamma$ is balanced, the constraints in CSP($\Gamma$) can be replaced by linear polynomials. We show in the next theorem that this approach fails when $\Gamma$ is not balanced.

**Theorem 4.4 (★).** Let $R$ be a $k$-ary relation that is not balanced. Then there exists $u \in \{0, 1\}^k \setminus R$ for which there exists no polynomial $p_u$ over any ring $E$ that captures $u$ with respect to $R$.

# 5 Characterization of symmetric CSPs with linear sparsification

In this section, we characterize the symmetric constraint languages $\Gamma$ for which CSP($\Gamma$) has a linear sparsification.

**Definition 5.1.** We say a $k$-ary Boolean relation $R$ is symmetric, if there exists $S \subseteq \{0, 1, \dots, k\}$ such that a tuple $x = (x_1, \dots, x_k)$ is in $R$ if and only if $\text{weight}(x) \in S$. We call $S$ the set of satisfying weights for $R$.

We will say that a constraint language $\Gamma$ is symmetric, if it only contains symmetric relations. We will prove the following theorem at the end of this section.

**Theorem 5.2.** Let $\Gamma$ be a finite Boolean symmetric intractable constraint language.
Using these tools from linear algebra, we now prove the main sparsification result.

**Proof of Theorem 4.1.** We show that for all relations $R$ in the balanced constraint language $\Gamma$, for all $u \notin R$, there exists a linear polynomial $p_u$ over a ring $E_u \in \{\mathbb{Z}/q_u\mathbb{Z} | q_u$ is a prime power\} that captures $u$ with respect to $R$. By applying Theorem 3.3 once for each relation $R \in \Gamma$, to reduce the number of constraints involving $R$ to $O(n)$, we then reduce any $n$-variable instance of CSP($\Gamma$) to an equivalent one on $|\Gamma| \cdot O(n) \in O(n)$ constraints.

Suppose for a contradiction that there exists $R \in \Gamma$ and $u \notin R$, such that no prime power $q$ and polynomial $p$ over $\mathbb{Z}/q\mathbb{Z}$ exist that satisfy conditions (1) and (2). We can view the process of finding such a linear polynomial, as solving a set of linear equations whose unknowns are the coefficients of the polynomial. We have a linear equation for each evaluation of the polynomial for which we want to enforce a certain value.

Let $R = \{r_1, \dots, r_\ell\}$. By the non-existence of $p$ and $q$, the system

$$ \begin{pmatrix} 1 & r_{1,1} & r_{1,2} & \dots & r_{1,k} \\ 1 & r_{2,1} & r_{2,2} & \dots & r_{2,k} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & r_{\ell,1} & r_{\ell,2} & \dots & r_{\ell,k} \\ 1 & u_1 & u_2 & \dots & u_k \end{pmatrix} \begin{pmatrix} \alpha_0 \\ \alpha_1 \\ \alpha_2 \\ \vdots \\ \alpha_k \end{pmatrix} \equiv_q \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 0 \\ c \end{pmatrix} $$

has no solution for any prime power $q$ and $c \neq q \neq 0$. Otherwise, it is easy to verify that $q$ is the desired prime power and $p(x_1, \dots, x_k) := \alpha_0 + \sum_{i=1}^k \alpha_i x_i$ is the desired polynomial.

The fact that no solution exists, implies that $(1, u_1, \dots, u_k)$ is in the span of the remaining rows of the matrix, by Lemma 4.3. But this implies that for any prime power $q$, there exist coefficients $\beta_1, \dots, \beta_\ell$ over $\mathbb{Z}/q\mathbb{Z}$ such that $u \equiv_q \sum \beta_i r_i$. Furthermore, since the first column of the matrix is the all-ones column, we obtain that $\sum \beta_i \equiv_q 1$. By Lemma 4.2, it follows that there exist integer coefficients $\gamma_1, \dots, \gamma_\ell$ such that $\sum \gamma_i = 1$ and furthermore $u = \sum \gamma_i r_i$. But it immediately follows that $R \in \Gamma$ is not preserved by the balanced operation given by $f(x_1, \dots, x_\ell) := \sum \gamma_i x_i$, which contradicts the assumption that $\Gamma$ is balanced. ◀

The kernelization result above is obtained by using the fact that when $\Gamma$ is balanced, the constraints in CSP($\Gamma$) can be replaced by linear polynomials. We show in the next theorem that this approach fails when $\Gamma$ is not balanced.

**Theorem 4.4 (★).** Let $R$ be a $k$-ary relation that is not balanced. Then there exists $u \in \{0, 1\}^k \setminus R$ for which there exists no polynomial $p_u$ over any ring $E$ that captures $u$ with respect to $R$.

# 5 Characterization of symmetric CSPs with linear sparsification

In this section, we characterize the symmetric constraint languages $\Gamma$ for which CSP($\Gamma$) has a linear sparsification.

**Definition 5.1.** We say a $k$-ary Boolean relation $R$ is symmetric, if there exists $S \subseteq \{0, 1, \dots, k\}$ such that a tuple $x = (x_1, \dots, x_k)$ is in $R$ if and only if weight($x) \in S$. We call $S$ the set of satisfying weights for $R$.

We will say that a constraint language $\Gamma$ is symmetric, if it only contains symmetric relations. We will prove the following theorem at the end of this section.

**Theorem 5.2.** Let $\Gamma$ be a finite Boolean symmetric intractable constraint language.
15:10 Best-Case and Worst-Case Sparsifiability of Boolean CSPs

■ If $\Gamma$ is balanced, then CSP($\Gamma$) has a kernel with $O(n)$ constraints that can be stored in $O(n \log n)$ bits.

■ If $\Gamma$ is not balanced, then CSP($\Gamma$) does not have a generalized kernel of size $O(n^{2-\epsilon})$ for any $\epsilon > 0$, unless NP $\subseteq$ coNP/poly.

To show this, we use the following lemma.

**Lemma 5.3 (★)**. Let $R$ be a $k$-ary symmetric relation with satisfying weights $S \subseteq \{0, 1, \dots, k\}$. Let $U := \{0, 1, \dots, k\} \setminus S$. If there exist $a, b, c \in S$ and $d \in U$ such that $a - b + c = d$, then $R$ cone-defines 2-OR.

**Proof sketch.** We will demonstrate the result in the case that $b \le a$, $b \le c$, and $b \le d$; the other cases are similar. We use the following tuple to express $x_1 \lor x_2$.

$$ \underbrace{(\neg x_1, \dots, \neg x_1)}_{(a-b) \text{ copies}}, \underbrace{(\neg x_2, \dots, \neg x_2)}_{(c-b) \text{ copies}}, \underbrace{1, \dots, 1}_{b \text{ copies}}, \underbrace{0, \dots, 0}_{(k-d) \text{ copies}} $$

Let $f: \{x_1, x_2\} \to \{0, 1\}$, then $(\neg f(x_1), \dots, \neg f(x_1), \neg f(x_2), \dots, \neg f(x_2), 1, \dots, 1, 0, \dots, 0)$ has weight $d \notin S$ when $f(x_1) = f(x_2) = 0$. It is easy to verify that in all other cases, the weight is one of $a, b, c \in S$ and hence the tuple belongs to $R$. The other cases are similar. ◀

We now give the main lemma that is needed to prove Theorem 5.2. It shows that if a relation is symmetric and not balanced, it must cone-define 2-OR.

**Lemma 5.4.** Let $R$ be a symmetric (Boolean) relation of arity $k$. If $R$ is not balanced, then $R$ cone-defines 2-OR.

**Proof.** Let $f$ be a balanced operation that does not preserve $R$. Since $f$ has integer coefficients, it follows that there exist (not necessarily distinct) $r_1, \dots, r_m \in R$, such that $r_1 - r_2 + r_3 - r_4 \cdots + r_m = u$ for some $u \in \{0, 1\}^k \setminus R$ and odd $m \ge 3$. Thereby, weight($r_1$) - weight($r_2$) + weight($r_3$) - weight($r_4$) + weight($r_m$) = weight($u$). Let $S$ be the set of satisfying weights for $R$ and let $U := \{0, \dots, k\} \setminus S$. Define $s_i := \text{weight}(r_i)$ for $i \in [m]$, and $t = \text{weight}(u)$, such that $s_1 - s_2 + s_3 - s_4 \cdots + s_m = t$, and furthermore $s_i \in S$ for all $i$, and $t \in U$. We show that there exist $a, b, c \in S$ and $d \in U$ such that $a - b + c = d$, such that the result follows from Lemma 5.3. We do this by induction on the length of the alternating sum.

If $m = 3$, we have that $s_1 - s_2 + s_3 = t$ and define $a := s_1, b := s_2, c := s_3$, and $d := t$.

If $m > 3$, we will use the following claim.

**Claim 5.5 (★).** Let $s_1, \dots, s_m \in S$ and $t \in U$ such that $s_1 - s_2 + s_3 - s_4 \cdots + s_m = t$. There exist distinct $i, j, \ell \in [m]$ with $i, j$ odd and $\ell$ even, such that $s_i - s_\ell + s_j \in \{0, \dots, k\}$.

Use Claim 5.5 to find $i, j, \ell$ such that $s_i - s_\ell + s_j \in \{0, \dots, k\}$. We consider two options. If $s_i - s_\ell + s_j \in U$, then define $d := s_i - s_\ell + s_j$, $a := s_i$, $b := s_\ell$, and $c := s_j$ and we are done. The other option is that $s_i - s_\ell + s_j = s \in S$. Replacing $s_i - s_\ell + s_j$ by $s$ in $s_1 - s_2 + s_3 - s_4 \cdots + s_m$ gives a shorter alternating sum with result $t$. We obtain $a, b, c$, and $d$ by the induction hypothesis.

Thereby, we have obtained $a, b, c \in S$, $d \in U$ such that $a - b + c = d$. It now follows from Lemma 5.3 that $R$ cone-defines 2-OR. ◀

Using the lemma above, we can now prove Theorem 5.2.
15:10 Best-Case and Worst-Case Sparsifiability of Boolean CSPs

■ If $\Gamma$ is balanced, then CSP($\Gamma$) has a kernel with $\mathcal{O}(n)$ constraints that can be stored in $\mathcal{O}(n \log n)$ bits.

■ If $\Gamma$ is not balanced, then CSP($\Gamma$) does not have a generalized kernel of size $\mathcal{O}(n^{2-\epsilon})$ for any $\epsilon > 0$, unless NP $\subseteq$ coNP/poly.

To show this, we use the following lemma.

**Lemma 5.3 (★)**. Let $R$ be a $k$-ary symmetric relation with satisfying weights $S \subseteq \{0, 1, \dots, k\}$. Let $U := \{0, 1, \dots, k\} \setminus S$. If there exist $a, b, c \in S$ and $d \in U$ such that $a - b + c = d$, then $R$ cone-defines 2-OR.

**Proof sketch.** We will demonstrate the result in the case that $b \le a$, $b \le c$, and $b \le d$; the other cases are similar. We use the following tuple to express $x_1 \lor x_2$.

$$ \underbrace{(\neg x_1, \dots, \neg x_1)}_{(a-b) \text{ copies}}, \underbrace{(\neg x_2, \dots, \neg x_2)}_{(c-b) \text{ copies}}, \underbrace{1, \dots, 1}_{b \text{ copies}}, \underbrace{0, \dots, 0}_{(k-d) \text{ copies}} $$

Let $f: \{x_1, x_2\} \to \{0, 1\}$, then $(\neg f(x_1), \dots, \neg f(x_1), \neg f(x_2), \dots, \neg f(x_2), 1, \dots, 1, 0, \dots, 0)$ has weight $d \notin S$ when $f(x_1) = f(x_2) = 0$. It is easy to verify that in all other cases, the weight is one of $a, b, c \in S$ and hence the tuple belongs to $R$. The other cases are similar. ◀

We now give the main lemma that is needed to prove Theorem 5.2. It shows that if a relation is symmetric and not balanced, it must cone-define 2-OR.

**Lemma 5.4.** Let $R$ be a symmetric (Boolean) relation of arity $k$. If $R$ is not balanced, then $R$ cone-defines 2-OR.

**Proof.** Let $f$ be a balanced operation that does not preserve $R$. Since $f$ has integer coefficients, it follows that there exist (not necessarily distinct) $r_1, \dots, r_m \in R$, such that $r_1 - r_2 + r_3 - r_4 \cdots + r_m = u$ for some $u \in \{0, 1\}^k \setminus R$ and odd $m \ge 3$. Thereby, weight($r_1$) - weight($r_2$) + weight($r_3$) - weight($r_4$) + weight($r_m$) = weight($u$). Let $S$ be the set of satisfying weights for $R$ and let $U := \{0, \dots, k\} \setminus S$. Define $s_i := \text{weight}(r_i)$ for $i \in [m]$, and $t = \text{weight}(u)$, such that $s_1 - s_2 + s_3 - s_4 + \dots + s_m = t$, and furthermore $s_i \in S$ for all $i$, and $t \in U$. We show that there exist $a, b, c \in S$ and $d \in U$ such that $a - b + c = d$, such that the result follows from Lemma 5.3. We do this by induction on the length of the alternating sum.

If $m = 3$, we have that $s_1 - s_2 + s_3 = t$ and define $a := s_1, b := s_2, c := s_3$, and $d := t$.

If $m > 3$, we will use the following claim.

**Claim 5.5 (★).** Let $s_1, \dots, s_m \in S$ and $t \in U$ such that $s_1 - s_2 + s_3 - s_4 + \dots + s_m = t$. There exist distinct $i, j, \ell \in [m]$ with $i, j$ odd and $\ell$ even, such that $s_i - s_\ell + s_j \in \{0, \dots, k\}$.

Use Claim 5.5 to find $i, j, \ell$ such that $s_i - s_\ell + s_j \in \{0, \dots, k\}$. We consider two options. If $s_i - s_\ell + s_j \in U$, then define $d := s_i - s_\ell + s_j$, $a := s_i$, $b := s_\ell$, and $c := s_j$ and we are done. The other option is that $s_i - s_\ell + s_j = s \in S$. Replacing $s_i - s_\ell + s_j$ by $s$ in $s_1 - s_2 + s_3 - s_4 + \dots + s_m$ gives a shorter alternating sum with result $t$. We obtain $a, b, c$, and $d$ by the induction hypothesis.

Thereby, we have obtained $a, b, c \in S$, $d \in U$ such that $a - b + c = d$. It now follows from Lemma 5.3 that $R$ cone-defines 2-OR. ◀

Using the lemma above, we can now prove Theorem 5.2.
**Proof of Theorem 5.2.** If $\Gamma$ is balanced, it follows from Theorem 4.1 that CSP($\Gamma$) has a kernel with $O(n)$ constraints that can be stored in $O(n \log n)$ bits. Note that the assumption that $\Gamma$ is symmetric is not needed in this case.

If the symmetric constraint language $\Gamma$ is not balanced, then $\Gamma$ contains a symmetric relation $R$ that is not balanced. It follows from Lemma 5.4 that $R$ cone-defines the 2-or relation. Thereby, we obtain from Theorem 3.5 that CSP($\Gamma$) has no generalized kernel of size $O(n^{2-\epsilon})$ for any $\epsilon > 0$, unless NP $\subseteq$ coNP/poly. ◀

# 6 Low-arity classification

In this section, we will give a full classification of the sparsifiability for constraint languages that consist only of low-arity relations. The next results will show that in this case, if the constraint language is not balanced, it can cone-define the 2-or relation.

* **Observation 6.1.** Each relation of arity 1 is balanced.

* **Theorem 6.2 (★).** A relation of arity 2 is balanced if and only if it is not cone-interdefinable with the 2-or relation.

* **Theorem 6.3 (★).** Suppose that $U \subseteq \{0,1\}^3$ is an arity 3 Boolean relation that is not balanced. Then, the 2-or relation is cone-definable from $U$.

Combining the results in this section with the results in previous sections, allows us to give a full classification of the sparsifiability of constraint languages that only contain relations of arity at most three. Observe that any $k$-ary relation $R$ such that $R \neq \emptyset$ and $\{0,1\}^k \setminus R \neq \emptyset$ cone-defines the 1-or relation. Since we assume that $\Gamma$ is intractable in the next theorem, it follows that $k$ is always defined and $k \in \{1,2,3\}$.

* **Theorem 6.4.** Let $\Gamma$ be an intractable Boolean constraint language such that each relation therein has arity $\le 3$. Let $k \in \mathbb{N}$ be the largest value for which $k$-or can be cone-defined from a relation in $\Gamma$. Then CSP($\Gamma$) has a kernel with $O(n^k)$ constraints that can be encoded in $O(n^k \log k)$ bits, but for any $\epsilon > 0$ there is no kernel of size $O(n^{k-\epsilon})$, unless NP $\subseteq$ coNP/poly.

*Proof.* To show that there is a kernel with $O(n^k)$ constraints, we do a case distinction on $k$.

- ($k=1$) If $k=1$, there is no relation in $\Gamma$ that cone-defines the 2-or relation. It follows from Observation 6.1 and Theorems 6.2 and 6.3 that thereby, $\Gamma$ is balanced. It now follows from Theorem 4.1 that CSP($\Gamma$) has a kernel with $O(n)$ constraints that can be stored in $O(n \log n)$ bits.

- ($k=2$) If $k=2$, there is no relation $R \in \Gamma$ with $|R| = 2^3 - 1 = 7$, as otherwise by Lemma 3.6 such a relation $R$ would cone-define 3-or which is a contradiction. Thereby, it follows from Theorem 3.1 that CSP($\Gamma$) has a sparsification with $O(n^{3-1}) = O(n^2)$ constraints that can be encoded in $O(n^2 \log n)$ bits.

- ($k=3$) Given an instance $(C, V)$, it is easy to obtain a kernel of with $O(n^3)$ constraints by simply removing duplicate constraints. This kernel can be stored in $O(n^3)$ bits, by storing for each relation $R \in \Gamma$ and for each tuple $(x_1, x_2, x_3) \in V^3$ whether $R(x_1, x_2, x_3) \in C$. Since $|\Gamma|$ is constant and there are $O(n^3)$ such tuples, this results in using $O(n^3)$ bits.

It remains to prove the lower bound. By definition, there exists $R \in \Gamma$ such that $R$ cone-defines the $k$-or relation. Thereby, the result follows immediately from Theorem 3.5. Thus, CSP($\Gamma$) has no kernel of size $O(n^{k-\epsilon})$ for any $\epsilon > 0$, unless NP $\subseteq$ coNP/poly. ◀
**Proof of Theorem 5.2.** If $\Gamma$ is balanced, it follows from Theorem 4.1 that CSP($\Gamma$) has a kernel with $O(n)$ constraints that can be stored in $O(n \log n)$ bits. Note that the assumption that $\Gamma$ is symmetric is not needed in this case.

If the symmetric constraint language $\Gamma$ is not balanced, then $\Gamma$ contains a symmetric relation $R$ that is not balanced. It follows from Lemma 5.4 that $R$ cone-defines the 2-or relation. Thereby, we obtain from Theorem 3.5 that CSP($\Gamma$) has no generalized kernel of size $O(n^{2-\epsilon})$ for any $\epsilon > 0$, unless NP $\subseteq$ coNP/poly. ◀

# 6 Low-arity classification

In this section, we will give a full classification of the sparsifiability for constraint languages that consist only of low-arity relations. The next results will show that in this case, if the constraint language is not balanced, it can cone-define the 2-or relation.

* **Observation 6.1.** Each relation of arity 1 is balanced.

* **Theorem 6.2 (★)**. A relation of arity 2 is balanced if and only if it is not cone-interdefinable with the 2-or relation.

* **Theorem 6.3 (★)**. Suppose that $U \subseteq \{0,1\}^3$ is an arity 3 Boolean relation that is not balanced. Then, the 2-or relation is cone-definable from $U$.

Combining the results in this section with the results in previous sections, allows us to give a full classification of the sparsifiability of constraint languages that only contain relations of arity at most three. Observe that any $k$-ary relation $R$ such that $R \neq \emptyset$ and $\{0,1\}^k \setminus R \neq \emptyset$ cone-defines the 1-or relation. Since we assume that $\Gamma$ is intractable in the next theorem, it follows that $k$ is always defined and $k \in \{1,2,3\}$.

* **Theorem 6.4.** Let $\Gamma$ be an intractable Boolean constraint language such that each relation therein has arity $\le 3$. Let $k \in \mathbb{N}$ be the largest value for which $k$-or can be cone-defined from a relation in $\Gamma$. Then CSP($\Gamma$) has a kernel with $O(n^k)$ constraints that can be encoded in $O(n^k \log k)$ bits, but for any $\epsilon > 0$ there is no kernel of size $O(n^{k-\epsilon})$, unless NP $\subseteq$ coNP/poly.

*Proof.* To show that there is a kernel with $O(n^k)$ constraints, we do a case distinction on $k$.

- ($k=1$) If $k=1$, there is no relation in $\Gamma$ that cone-defines the 2-or relation. It follows from Observation 6.1 and Theorems 6.2 and 6.3 that thereby, $\Gamma$ is balanced. It now follows from Theorem 4.1 that CSP($\Gamma$) has a kernel with $O(n)$ constraints that can be stored in $O(n \log n)$ bits.

- ($k=2$) If $k=2$, there is no relation $R \in \Gamma$ with $|R| = 2^3 - 1 = 7$, as otherwise by Lemma 3.6 such a relation $R$ would cone-define 3-or which is a contradiction. Thereby, it follows from Theorem 3.1 that CSP($\Gamma$) has a sparsification with $O(n^{3-1}) = O(n^2)$ constraints that can be encoded in $O(n^2 \log n)$ bits.

- ($k=3$) Given an instance $(C, V)$, it is easy to obtain a kernel of with $O(n^3)$ constraints by simply removing duplicate constraints. This kernel can be stored in $O(n^3)$ bits, by storing for each relation $R \in \Gamma$ and for each tuple $(x_1, x_2, x_3) \in V^3$ whether $R(x_1, x_2, x_3) \in C$. Since $|\Gamma|$ is constant and there are $O(n^3)$ such tuples, this results in using $O(n^3)$ bits.

It remains to prove the lower bound. By definition, there exists $R \in \Gamma$ such that $R$ cone-defines the $k$-or relation. Thereby, the result follows immediately from Theorem 3.5. Thus, CSP($\Gamma$) has no kernel of size $O(n^{k-\epsilon})$ for any $\epsilon > 0$, unless NP $\subseteq$ coNP/poly. ◀
# 7 Conclusion

In this paper we analyzed the best-case and worst-case sparsifiability of CSP(Γ) for intractable finite Boolean constraint languages Γ. First of all, we characterized those Boolean CSPs for which a nontrivial sparsification is possible, based on the number of non-satisfying assignments. Then we presented our key structural contribution: the notion of balanced constraint languages. We have shown that CSP(Γ) allows a sparsification with $O(n)$ constraints whenever Γ is balanced. The constructive proof of this statement can be transformed into an effective algorithm to find a series of low-degree polynomials to capture the constraints, which earlier had to be done by hand. By combining the resulting upper and lower bound framework, we fully classified the symmetric constraint languages for which CSP(Γ) allows a linear sparsification. Furthermore, we fully classified the sparsifiability of CSP(Γ) when Γ contains relations of arity at most three, based on the arity of the largest OR that can be cone-defined from Γ. It follows from results of Lagerkvist and Wahlström [15] that for constraint languages of arbitrary arity, the exponent of the best sparsification size does not always match the arity of the largest OR cone-definable from Γ. (This will be described in more detail in the upcoming journal version of this work.) Hence the type of characterization we presented is inherently limited to low-arity constraint languages. It may be possible to extend our characterization to languages of arity at most four, however.

The ultimate goal of this line of research is to fully classify the sparsifiability of CSP(Γ), depending on Γ. In particular, we would like to classify those Γ for which $O(n)$ sparsifiability is possible. In this paper, we have shown that Γ being balanced is a sufficient condition to obtain a linear sparsification; it is tempting to conjecture that this condition is also necessary.

We conclude with a brief discussion on the relation between our polynomial-based framework for linear compression and the framework of Lagerkvist and Wahlström [15]. They used a different method for sparsification, based on embedding a Boolean constraint language Γ into a constraint language Γ' defined over a larger domain D, such that Γ' is preserved by a Maltsev operation. This latter condition ensures that CSP(Γ') is polynomial-time solvable, which allows CSP(Γ) to be sparsified to $O(n)$ constraints when D is finite. It turns out that the Maltsev-based linear sparsification is more general than the polynomial-based linear sparsification presented here: all finite Boolean constraint languages Γ that are balanced, admit a Maltsev embedding over a finite domain (the direct sum of the rings $Z/q_uZ$ over which the capturing polynomials are defined) and can therefore be linearly sparsified using the algorithm of Lagerkvist and Wahlström. Despite the fact that our polynomial-based framework is not more general than the Maltsev-based approach, it has two distinct advantages. First of all, there is a straight-forward decision procedure to determine whether a constraint can be captured by degree-1 polynomials, which follows from the proof of Theorem 4.1. To the best of our knowledge, no decision procedure is known to determine whether a Boolean constraint language admits a Maltsev embedding over a finite domain. The second advantage of our method is that when the polynomial framework for linear compression does not apply, this is witnessed by a relation in Γ that is violated by a balanced operation. As we have shown, in several scenarios this violation can be used to construct a sparsification lower bound to give provably optimal bounds.

It would be interesting to determine whether the Maltsev-based framework for sparsification is strictly more general than the polynomial-based framework. We are not aware of any concrete Boolean constraint language Γ for which CSP(Γ) admits a Maltsev embedding over a finite domain, yet is not balanced.
# 7 Conclusion

In this paper we analyzed the best-case and worst-case sparsifiability of CSP(Γ) for intractable finite Boolean constraint languages Γ. First of all, we characterized those Boolean CSPs for which a nontrivial sparsification is possible, based on the number of non-satisfying assignments. Then we presented our key structural contribution: the notion of balanced constraint languages. We have shown that CSP(Γ) allows a sparsification with $O(n)$ constraints whenever Γ is balanced. The constructive proof of this statement can be transformed into an effective algorithm to find a series of low-degree polynomials to capture the constraints, which earlier had to be done by hand. By combining the resulting upper and lower bound framework, we fully classified the symmetric constraint languages for which CSP(Γ) allows a linear sparsification. Furthermore, we fully classified the sparsifiability of CSP(Γ) when Γ contains relations of arity at most three, based on the arity of the largest OR that can be cone-defined from Γ. It follows from results of Lagerkvist and Wahlström [15] that for constraint languages of arbitrary arity, the exponent of the best sparsification size does not always match the arity of the largest OR cone-definable from Γ. (This will be described in more detail in the upcoming journal version of this work.) Hence the type of characterization we presented is inherently limited to low-arity constraint languages. It may be possible to extend our characterization to languages of arity at most four, however.

The ultimate goal of this line of research is to fully classify the sparsifiability of CSP(Γ), depending on Γ. In particular, we would like to classify those Γ for which $O(n)$ sparsifiability is possible. In this paper, we have shown that Γ being balanced is a sufficient condition to obtain a linear sparsification; it is tempting to conjecture that this condition is also necessary.

We conclude with a brief discussion on the relation between our polynomial-based framework for linear compression and the framework of Lagerkvist and Wahlström [15]. They used a different method for sparsification, based on embedding a Boolean constraint language Γ into a constraint language Γ' defined over a larger domain D, such that Γ' is preserved by a Maltsev operation. This latter condition ensures that CSP(Γ') is polynomial-time solvable, which allows CSP(Γ) to be sparsified to $O(n)$ constraints when D is finite. It turns out that the Maltsev-based linear sparsification is more general than the polynomial-based linear sparsification presented here: all finite Boolean constraint languages Γ that are balanced, admit a Maltsev embedding over a finite domain (the direct sum of the rings $Z/q_uZ$ over which the capturing polynomials are defined) and can therefore be linearly sparsified using the algorithm of Lagerkvist and Wahlström. Despite the fact that our polynomial-based framework is not more general than the Maltsev-based approach, it has two distinct advantages. First of all, there is a straight-forward decision procedure to determine whether a constraint can be captured by degree-1 polynomials, which follows from the proof of Theorem 4.1. To the best of our knowledge, no decision procedure is known to determine whether a Boolean constraint language admits a Maltsev embedding over a finite domain. The second advantage of our method is that when the polynomial framework for linear compression does not apply, this is witnessed by a relation in Γ that is violated by a balanced operation. As we have shown, in several scenarios this violation can be used to construct a sparsification lower bound to give provably optimal bounds.

It would be interesting to determine whether the Maltsev-based framework for sparsification is strictly more general than the polynomial-based framework. We are not aware of any concrete Boolean constraint language Γ for which CSP(Γ) admits a Maltsev embedding over a finite domain, yet is not balanced.
References

1. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernelization Lower Bounds by Cross-Composition. *SIAM J. Discrete Math.*, 28(1):277-305, 2014. doi: 10.1137/120880240.

2. Hans L. Bodlaender, Stéphan Thomassé, and Anders Yeo. Kernel bounds for disjoint cycles and disjoint paths. *Theor. Comput. Sci.*, 412(35):4570-4578, 2011. doi:10.1016/j.tcs.2011.04.039.

3. Hubie Chen. A Rendezvous of Logic, Complexity, and Algebra. *ACM Computing Surveys*, 42(1), 2009. doi:10.1145/1189056.1189076.

4. Hubie Chen, Bart M. P. Jansen, and Astrid Pieterse. Best-case and Worst-case Sparsifiability of Boolean CSPs. *CoRR*, abs/1809.06171v1, 2018. arXiv:1809.06171v1.

5. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. *Parameterized Algorithms*. Springer, 2015. doi:10.1007/978-3-319-21275-3.

6. Holger Dell and Dániel Marx. Kernelization of packing problems. In *Proc. 23rd SODA*, pages 68-81, 2012. doi:10.1137/1.9781611973099.6.

7. Holger Dell and Dieter van Melkebeek. Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses. *J. ACM*, 61(4):23:1-23:27, 2014. doi: 10.1145/2629620.

8. Rodney G. Downey and Michael R. Fellows. *Fundamentals of Parameterized Complexity*. Texts in Computer Science. Springer, 2013. doi:10.1007/978-1-4471-5559-1.

9. Bart M. P. Jansen. On Sparsification for Computing Treewidth. *Algorithmica*, 71(3):605-635, 2015. doi:10.1007/s00453-014-9924-2.

10. Bart M. P. Jansen and Astrid Pieterse. Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials. In *Proc. 41st MFCS*, pages 71:1-71:14, 2016. doi:10.4230/LIPIcs.MFCS.2016.71.

11. Bart M. P. Jansen and Astrid Pieterse. Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials. In *Proc. 12th IPEC*, pages 22:1-22:12, 2017. doi:10.4230/LIPIcs.IPEC.2017.22.

12. Bart M. P. Jansen and Astrid Pieterse. Sparsification Upper and Lower Bounds for Graph Problems and Not-All-Equal SAT. *Algorithmica*, 79(1):3-28, 2017. doi:10.1007/s00453-016-0189-9.

13. Bart M. P. Jansen and Astrid Pieterse. Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials. *CoRR*, abs/1606.03233v2, 2018. arXiv:1606.03233v2.

14. Stefan Kratsch, Geevarghese Philip, and Saurabh Ray. Point Line Cover: The Easy Kernel is Essentially Tight. *ACM Trans. Algorithms*, 12(3):40:1-40:16, 2016. doi: 10.1145/2832912.

15. Victor Lagerkvist and Magnus Wahlström. Kernelization of Constraint Satisfaction Problems: A Study Through Universal Algebra. In *Proc. 23rd CP*, pages 157-171, 2017. doi:10.1007/978-3-319-66158-2_11.

16. Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Kernelization - Preprocessing with a Guarantee. In *The Multivariate Algorithmic Revolution and Beyond*, pages 129-161, 2012. doi:10.1007/978-3-642-30891-8_10.

17. Lásló Lovász. Chromatic number of hypergraphs and linear algebra. In *Studia Scientiarum Mathematicarum Hungarica* 11, pages 113-114, 1976.

18. Thomas J. Schaefer. The Complexity of Satisfiability Problems. In *Proc. 10th STOC*, pages 216-226, 1978. doi:10.1145/800133.804350.
References

1. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernelization Lower Bounds by Cross-Composition. *SIAM J. Discrete Math.*, 28(1):277–305, 2014. doi: 10.1137/120880240.

2. Hans L. Bodlaender, Stéphan Thomassé, and Anders Yeo. Kernel bounds for disjoint cycles and disjoint paths. *Theor. Comput. Sci.*, 412(35):4570–4578, 2011. doi:10.1016/j.tcs.2011.04.039.

3. Hubie Chen. A Rendezvous of Logic, Complexity, and Algebra. *ACM Computing Surveys*, 42(1), 2009. doi:10.1145/1189056.1189076.

4. Hubie Chen, Bart M. P. Jansen, and Astrid Pieterse. Best-case and Worst-case Sparsifiability of Boolean CSPs. *CoRR*, abs/1809.06171v1, 2018. arXiv:1809.06171v1.

5. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. *Parameterized Algorithms*. Springer, 2015. doi:10.1007/978-3-319-21275-3.

6. Holger Dell and Dániel Marx. Kernelization of packing problems. In *Proc. 23rd SODA*, pages 68–81, 2012. doi:10.1137/1.9781611973099.6.

7. Holger Dell and Dieter van Melkebeek. Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses. *J. ACM*, 61(4):23:1–23:27, 2014. doi: 10.1145/2629620.

8. Rodney G. Downey and Michael R. Fellows. *Fundamentals of Parameterized Complexity*. Texts in Computer Science. Springer, 2013. doi:10.1007/978-1-4471-5559-1.

9. Bart M. P. Jansen. On Sparsification for Computing Treewidth. *Algorithmica*, 71(3):605–635, 2015. doi:10.1007/s00453-014-9924-2.

10. Bart M. P. Jansen and Astrid Pieterse. Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials. In *Proc. 41st MFCS*, pages 71:1–71:14, 2016. doi:10.4230/LIPIcs.MFCS.2016.71.

11. Bart M. P. Jansen and Astrid Pieterse. Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials. In *Proc. 12th IPEC*, pages 22:1–22:12, 2017. doi:10.4230/LIPIcs.IPEC.2017.22.

12. Bart M. P. Jansen and Astrid Pieterse. Sparsification Upper and Lower Bounds for Graph Problems and Not-All-Equal SAT. *Algorithmica*, 79(1):3–28, 2017. doi:10.1007/s00453-016-0189-9.

13. Bart M. P. Jansen and Astrid Pieterse. Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials. *CoRR*, abs/1606.03233v2, 2018. arXiv:1606.03233v2.

14. Stefan Kratsch, Geevarghese Philip, and Saurabh Ray. Point Line Cover: The Easy Kernel is Essentially Tight. *ACM Trans. Algorithms*, 12(3):40:1–40:16, 2016. doi: 10.1145/2832912.

15. Victor Lagerkvist and Magnus Wahlström. Kernelization of Constraint Satisfaction Problems: A Study Through Universal Algebra. In *Proc. 23rd CP*, pages 157–171, 2017. doi:10.1007/978-3-319-66158-2_11.

16. Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Kernelization - Preprocessing with a Guarantee. In *The Multivariate Algorithmic Revolution and Beyond*, pages 129–161, 2012. doi:10.1007/978-3-642-30891-8_10.

17. László Lovász. Chromatic number of hypergraphs and linear algebra. In *Studia Scientiarum Mathematicarum Hungarica* 11, pages 113–114, 1976.

18. Thomas J. Schaefer. The Complexity of Satisfiability Problems. In *Proc. 10th STOC*, pages 216–226, 1978. doi:10.1145/800133.804350.
<figure><img src="image_84.png" /></figure>
<figure><img src="image_87.png" /></figure>
# Parameterized Leaf Power Recognition via Embedding into Graph Products

David Eppstein<fnref n="1" />

Computer Science Department, University of California, Irvine, USA
eppstein@uci.edu

Elham Havvaei

Computer Science Department, University of California, Irvine, USA
ehavvaei@uci.edu

## Abstract

The *k*-leaf power graph *G* of a tree *T* is a graph whose vertices are the leaves of *T* and whose edges connect pairs of leaves at unweighted distance at most *k* in *T*. Recognition of the *k*-leaf power graphs for *k* ≥ 6 is still an open problem. In this paper, we provide an algorithm for this problem for sparse leaf power graphs. Our result shows that the problem of recognizing these graphs is fixed-parameter tractable when parameterized both by *k* and by the degeneracy of the given graph. To prove this, we describe how to embed the leaf root of a leaf power graph into a product of the graph with a cycle graph. We bound the treewidth of the resulting product in terms of *k* and the degeneracy of *G*. As a result, we can use methods based on monadic second-order logic (MSO₂) to recognize the existence of a leaf power as a subgraph of the product graph.

**2012 ACM Subject Classification** Theory of computation → Design and analysis of algorithms, Theory of computation → Fixed parameter tractability

**Keywords and phrases** leaf power, phylogenetic tree, monadic second-order logic, Courcelle's theorem, strong product of graphs, fixed-parameter tractability

**Digital Object Identifier** 10.4230/LIPIcs.IPEC.2018.16

## 1 Introduction

Leaf powers are a class of graphs that were introduced in 2002 by Nishimura, Ragde and Thilikos [29], extending the notion of graph powers. For a graph *G*, the *k*-th power graph $G^k$ has the same set of vertices as *G* but a different notion of adjacency: two vertices are adjacent in $G^k$ if there is a path of at most *k* edges between them in *G*. The leaf powers are defined in the same way from trees, but only including the leaves of the trees as vertices. The *k*-th leaf power of a tree *T* has the leaves of *T* as its vertices, with two vertices adjacent in the leaf power if there is a path of at most *k* edges between them in *T*. A given graph *G* is a *k*-leaf-power graph when there exists a tree *T* for which *G* is the *k*-th leaf power. In this case, *T* is called the *k*-leaf root of *G*. For example, Figure 1 shows a 3-leaf power alongside its 3-leaf root. Nishimura et al., further, derived the first polynomial-time algorithms to recognize *k*-leaf powers for *k* = 3 and *k* = 4 [29].

The problem of recognizing leaf powers arises as a formalization of a problem in computational biology, the reconstruction of evolutionary history and evolutionary trees from information about the similarity between species [12, 21]. In this problem, the common ancestry of different species can be represented by an evolutionary or phylogenetic tree, in

<figure><img src="image_85.png" /></figure>

<footnote n="1">¹ Supported in part by NSF grants CCF-1618301 and CCF-1616248.</footnote>
# Parameterized Leaf Power Recognition via Embedding into Graph Products

David Eppstein<fnref n="1" />

Computer Science Department, University of California, Irvine, USA
eppstein@uci.edu

Elham Havvaei

Computer Science Department, University of California, Irvine, USA
ehavvaei@uci.edu

**Abstract**

The *k*-leaf power graph *G* of a tree *T* is a graph whose vertices are the leaves of *T* and whose edges connect pairs of leaves at unweighted distance at most *k* in *T*. Recognition of the *k*-leaf power graphs for *k* ≥ 6 is still an open problem. In this paper, we provide an algorithm for this problem for sparse leaf power graphs. Our result shows that the problem of recognizing these graphs is fixed-parameter tractable when parameterized both by *k* and by the degeneracy of the given graph. To prove this, we describe how to embed the leaf root of a leaf power graph into a product of the graph with a cycle graph. We bound the treewidth of the resulting product in terms of *k* and the degeneracy of *G*. As a result, we can use methods based on monadic second-order logic (MSO₂) to recognize the existence of a leaf power as a subgraph of the product graph.

**2012 ACM Subject Classification** Theory of computation → Design and analysis of algorithms, Theory of computation → Fixed parameter tractability

**Keywords and phrases** leaf power, phylogenetic tree, monadic second-order logic, Courcelle's theorem, strong product of graphs, fixed-parameter tractability

**Digital Object Identifier** 10.4230/LIPIcs.IPEC.2018.16

# 1 Introduction

Leaf powers are a class of graphs that were introduced in 2002 by Nishimura, Ragde and Thilikos [29], extending the notion of graph powers. For a graph $G$, the $k$th power graph $G^k$ has the same set of vertices as $G$ but a different notion of adjacency: two vertices are adjacent in $G^k$ if there is a path of at most $k$ edges between them in $G$. The leaf powers are defined in the same way from trees, but only including the leaves of the trees as vertices. The $k$th leaf power of a tree $T$ has the leaves of $T$ as its vertices, with two vertices adjacent in the leaf power if there is a path of at most $k$ edges between them in $T$. A given graph $G$ is a $k$-leaf-power graph when there exists a tree $T$ for which $G$ is the $k$th leaf power. In this case, $T$ is called the *$k$-leaf root* of $G$. For example, Figure 1 shows a 3-leaf power alongside its 3-leaf root. Nishimura et al., further, derived the first polynomial-time algorithms to recognize $k$-leaf powers for $k = 3$ and $k = 4$ [29].

The problem of recognizing leaf powers arises as a formalization of a problem in computational biology, the reconstruction of evolutionary history and evolutionary trees from information about the similarity between species [12, 21]. In this problem, the common ancestry of different species can be represented by an evolutionary or phylogenetic tree, in

<figure><img src="image_88.png" /></figure>

<footnote n="1">¹ Supported in part by NSF grants CCF-1618301 and CCF-1616248.</footnote>
16:2 Parameterized Leaf Power Recognition

<figure><img src="image_86.png" /><figcaption>Figure 1 A 3-leaf power graph $G$ and its 3-leaf root $T$.</figcaption></figure>

which each vertex represents a species and each edge represents a direct ancestry relation
between two species. We only have full access to living species, the species at the leaves of
the tree; the other species in the tree are typically long-extinct, and may be represented
physically only through fossils or not at all. If we suppose that we can infer, from observations
of living species, which ones are close together (within some number *k* of steps in this tree)
and which others are not, then we could use an algorithm for leaf power recognition to infer
a phylogenetic tree consistent with this data.

1.1 New Results

In this paper, we prove that the *k*-leaf powers of degeneracy *d* can be recognized in time
that is fixed-parameter tractable when parameterized by *k* and *d*. Here, the degeneracy of a
graph is the maximum, over its subgraphs, of the minimum degree of any subgraph. Our
result provides an algorithm whose running time is polynomial (in fact linear) in the size of
its input graph, multiplied by a factor that depends non-polynomially on *k* and *d*.

It is known that the *k*-leaf powers have bounded clique-width for bounded *k* [24]. A
wide class of graph problems (those expressible in a version of monadic second order logic
quantifying over only vertex sets, MSO<sub>1</sub>) can be solved in fixed-parameter time for graphs of
bounded clique-width, via Courcelle's theorem [16]. However we have been unable to express
the recognition of leaf powers in MSO<sub>1</sub>. Instead, our algorithm uses a more powerful version
of monadic second order logic allowing quantification over edge sets, MSO<sub>2</sub>. The graphs of
bounded clique-width and bounded degeneracy have bounded treewidth, allowing us to apply
a form of Courcelle's theorem for MSO<sub>2</sub> and for graphs of bounded treewidth.

However, there is an additional complication that makes it tricky to apply these methods
to leaf power recognition. The tree that we wish to find, for which our given input graph is
a leaf power, will in general include vertices and edges that are not part of the input, but
MSO₂ can only quantify over subsets of the existing vertices and edges of a graph, not over
sets of vertices and edges that are not subsets of the input. To work around this problem,
we apply Courcelle's theorem not to the given graph *G* itself, but to a *product graph* G ⊠ Cₖ
where Cₖ is a *k*-vertex cycle graph. We prove that the leaf root (the tree for which *G* is a leaf
power, if it is one) can be embedded as a subgraph of this product, that it can be recognized
by an MSO₂ formula applied to this product, and that this product has bounded treewidth
whenever *G* is a *k*-leaf power of bounded degeneracy. In this way we can recognize *G* as
a leaf power, not by applying Courcelle's theorem to *G*, but by applying it to the product
graph.
16:2 Parameterized Leaf Power Recognition

<figure><img src="image_89.png" /><figcaption>Figure 1 A 3-leaf power graph $G$ and its 3-leaf root $T$.</figcaption></figure>

which each vertex represents a species and each edge represents a direct ancestry relation
between two species. We only have full access to living species, the species at the leaves of
the tree; the other species in the tree are typically long-extinct, and may be represented
physically only through fossils or not at all. If we suppose that we can infer, from observations
of living species, which ones are close together (within some number *k* of steps in this tree)
and which others are not, then we could use an algorithm for leaf power recognition to infer
a phylogenetic tree consistent with this data.

1.1 New Results

In this paper, we prove that the *k*-leaf powers of degeneracy *d* can be recognized in time
that is fixed-parameter tractable when parameterized by *k* and *d*. Here, the degeneracy of a
graph is the maximum, over its subgraphs, of the minimum degree of any subgraph. Our
result provides an algorithm whose running time is polynomial (in fact linear) in the size of
its input graph, multiplied by a factor that depends non-polynomially on *k* and *d*.

It is known that the *k*-leaf powers have bounded clique-width for bounded *k* [24]. A
wide class of graph problems (those expressible in a version of monadic second order logic
quantifying over only vertex sets, MSO<sub>1</sub>) can be solved in fixed-parameter time for graphs of
bounded clique-width, via Courcelle's theorem [16]. However we have been unable to express
the recognition of leaf powers in MSO<sub>1</sub>. Instead, our algorithm uses a more powerful version
of monadic second order logic allowing quantification over edge sets, MSO<sub>2</sub>. The graphs of
bounded clique-width and bounded degeneracy have bounded treewidth, allowing us to apply
a form of Courcelle's theorem for MSO<sub>2</sub> and for graphs of bounded treewidth.

However, there is an additional complication that makes it tricky to apply these methods
to leaf power recognition. The tree that we wish to find, for which our given input graph is
a leaf power, will in general include vertices and edges that are not part of the input, but
MSO₂ can only quantify over subsets of the existing vertices and edges of a graph, not over
sets of vertices and edges that are not subsets of the input. To work around this problem,
we apply Courcelle's theorem not to the given graph *G* itself, but to a *product graph* G ⊠ Cₖ
where Cₖ is a *k*-vertex cycle graph. We prove that the leaf root (the tree for which *G* is a leaf
power, if it is one) can be embedded as a subgraph of this product, that it can be recognized
by an MSO₂ formula applied to this product, and that this product has bounded treewidth
whenever *G* is a *k*-leaf power of bounded degeneracy. In this way we can recognize *G* as
a leaf power, not by applying Courcelle's theorem to *G*, but by applying it to the product
graph.
<figure><img src="image_87.png" /><figcaption>■ **Figure 2** A graph is a 4-leaf power if and only if it is chordal and does not contain any of the graphs above as a subgraph.</figcaption></figure>

Thus, our algorithm combines the following ingredients:

- Our embedding of the *k*-leaf root as a subgraph of the product graph $G \boxtimes C_k$.

- Our logical representation of *k*-leaf roots as subgraphs of product graphs.

- Courcelle's theorem, which provides general-purpose algorithms for testing $MSO_2$ formulas on graphs of bounded treewidth.

- The fact that the *k*-leaf powers, for bounded values of *k*, have bounded clique-width.

- The fact that graphs of bounded clique-width and bounded degeneracy also have bounded treewidth.

- The fact that, by taking a product with a graph of bounded size, we preserve the bounded treewidth of the product.

Our algorithm runs in fixed-parameter tractable time when parameterized by *k* and the degeneracy *d* of the given input graph. In particular, it runs in linear-time when *k* and *d* are both constant.

Our result provides the first known efficient algorithm for recognizing *k*-leaf powers for $k \ge 6$, for graphs of bounded degeneracy. More generally, our method of embedding into graph products appears likely to apply to other graph problems involving network design (the addition of edges to an existing graph, rather than the identification of a special subgraph of the input). In the case we apply this method to leaf power recognition, we expect that it should be possible to translate our $MSO_2$ formula over the product graph into a significantly more complicated $MSO_2$ formula over the input graph, but the method of embedding into graph products considerably simplifies our task of designing a logical formula for our problem.

## 1.2 Related Work

Polynomial-time algorithms are known for recognizing *k*-leaf powers for $k \ge 5$.

- A graph is a 2-leaf power if it is a disjoint union of cliques, so this class of graphs is trivial to recognize.

- There exist various ways to characterize 3-leaf powers [29, 7, 18, 30], some of which lead to efficient algorithms. For instance, one way to determine if a graph is a 3-leaf power is to check whether it is bull-, dart- and gem-free and chordal [18]. The chordal graphs have a known recognition algorithm, and testing for the existence of any of the other forbidden induced subgraphs is polynomial, because they all have bounded size.

- Similarly, there are various known ways to characterize 4-leaf powers [29, 30, 19, 9]. One is that graph is a 4-leaf power if and only if it is chordal and does not contain any
<figure><img src="image_90.png" /><figcaption>■ **Figure 2** A graph is a 4-leaf power if and only if it is chordal and does not contain any of the graphs above as a subgraph.</figcaption></figure>

Thus, our algorithm combines the following ingredients:

- Our embedding of the *k*-leaf root as a subgraph of the product graph $G \boxtimes C_k$.

- Our logical representation of *k*-leaf roots as subgraphs of product graphs.

- Courcelle's theorem, which provides general-purpose algorithms for testing $MSO_2$ formulas on graphs of bounded treewidth.

- The fact that the *k*-leaf powers, for bounded values of *k*, have bounded clique-width.

- The fact that graphs of bounded clique-width and bounded degeneracy also have bounded treewidth.

- The fact that, by taking a product with a graph of bounded size, we preserve the bounded treewidth of the product.

Our algorithm runs in fixed-parameter tractable time when parameterized by *k* and the degeneracy *d* of the given input graph. In particular, it runs in linear-time when *k* and *d* are both constant.

Our result provides the first known efficient algorithm for recognizing *k*-leaf powers for $k \ge 6$, for graphs of bounded degeneracy. More generally, our method of embedding into graph products appears likely to apply to other graph problems involving network design (the addition of edges to an existing graph, rather than the identification of a special subgraph of the input). In the case we apply this method to leaf power recognition, we expect that it should be possible to translate our $MSO_2$ formula over the product graph into a significantly more complicated $MSO_2$ formula over the input graph, but the method of embedding into graph products considerably simplifies our task of designing a logical formula for our problem.

## 1.2 Related Work

Polynomial-time algorithms are known for recognizing *k*-leaf powers for $k \ge 5$.

- A graph is a 2-leaf power if it is a disjoint union of cliques, so this class of graphs is trivial to recognize.

- There exist various ways to characterize 3-leaf powers [29, 7, 18, 30], some of which lead to efficient algorithms. For instance, one way to determine if a graph is a 3-leaf power is to check whether it is bull-, dart- and gem-free and chordal [18]. The chordal graphs have a known recognition algorithm, and testing for the existence of any of the other forbidden induced subgraphs is polynomial, because they all have bounded size.

- Similarly, there are various known ways to characterize 4-leaf powers [29, 30, 19, 9]. One is that graph is a 4-leaf power if and only if it is chordal and does not contain any
16:4 Parameterized Leaf Power Recognition

<figure><img src="image_88.png" /><figcaption>■ **Figure 3** The graph on the right is the strong product of a four-vertex path graph (top left) and a four-vertex cycle graph (bottom left). The colors indicate the partition of the edges into vertical, horizontal, and diagonal subsets.</figcaption></figure>

of the graphs depicted in Figure 2 as induced subgraphs [30]. Again, this leads to a polynomial-time recognition algorithm, because all of these graphs have bounded size.

k-leaf powers can be recognized in polynomial time if the (k-2)-Steiner root problem can be solved in polynomial time. Chang and Ko in 2007, provided a linear-time algorithm recognition for 3-Steiner root problem [11]. This implies that 5-leaf powers can be recognized in linear time.

Polynomial-time structural characterization of *k*-leaf powers for *k* ≥ 6 is still an open problem. Nonetheless, Brandstädt et al. provided a characterization for the distance-hereditary 5-leaf powers [8].

Throughout the literature, there exist many structural characterizations of leaf powers which provide potentially useful insight into this class of graphs. It is known, for instance, that all leaf powers are strongly chordal, but the converse is not always true. Further, Kennedy et al. showed that strictly chordal graphs are always *k*-leaf powers for *k* ≥ 4; these are the chordal graphs that are also, dart- and gem-free. They provided a linear-time algorithm to construct *k*-leaf roots of strictly chordal graphs [27].

For all $k \ge 2$, every $k$-leaf power is also a $(k+2)$-leaf power. A $(k+2)$-leaf root of any $k$-leaf-power can be obtained from its $k$-leaf root, by subdividing all edges incident to leaves. However, the problems of recognizing $k$-leaf powers for different values of $k$ do not collapse: for all $k \ge 4$, there exists a $k$-leaf power which is not a $(k+1)$-leaf power [10].

2 Preliminaries

2.1 Definitions

Throughout this paper, we let $G(V, E)$ denote a simple undirected graph (typically, the input to the leaf power recognition problem). If $u$ and $v$ are two vertices in $V$ that are adjacent in $G$, we let $e(u, v)$ denote the edge connecting them.

The strong product of graphs $G_1$ and $G_2$, denoted as $G_1 \boxtimes G_2$, is a graph whose vertices are ordered pairs of a vertex from $G_1$ and a vertex from $G_2$. In it, two distinct vertices $(u_1, u_2)$ and $(v_1, v_2)$ are adjacent if and only if for all $i \in \{1, 2\}$, $u_i = v_i$ or $u_i$ and $v_i$ are adjacent in $G_i$. Figure 3 shows an example, the strong product of a four-vertex path graph
16:4 Parameterized Leaf Power Recognition

<figure><img src="image_91.png" /><figcaption>■ **Figure 3** The graph on the right is the strong product of a four-vertex path graph (top left) and a four-vertex cycle graph (bottom left). The colors indicate the partition of the edges into vertical, horizontal, and diagonal subsets.</figcaption></figure>

of the graphs depicted in Figure 2 as induced subgraphs [30]. Again, this leads to a
polynomial-time recognition algorithm, because all of these graphs have bounded size.

k-leaf powers can be recognized in polynomial time if the (k-2)- Steiner root problem can be solved in polynomial time. Chang and Ko in 2007, provided a linear-time algorithm recognition for 3-Steiner root problem [11]. This implies that 5-leaf powers can be recognized in linear time.

Polynomial-time structural characterization of *k*-leaf powers for *k* ≥ 6 is still an open problem.
Nonetheless, Brandstädt et al. provided a characterization for the distance-hereditary 5-leaf
powers [8].

Throughout the literature, there exist many structural characterizations of leaf powers which provide potentially useful insight into this class of graphs. It is known, for instance, that all leaf powers are strongly chordal, but the converse is not always true. Further, Kennedy et al. showed that strictly chordal graphs are always *k*-leaf powers for *k* ≥ 4; these are the chordal graphs that are also, dart- and gem-free. They provided a linear-time algorithm to construct *k*-leaf roots of strictly chordal graphs [27].

For all $k \ge 2$, every $k$-leaf power is also a $(k+2)$-leaf power. A $(k+2)$-leaf root of any $k$-leaf-power can be obtained from its $k$-leaf root, by subdividing all edges incident to leaves. However, the problems of recognizing $k$-leaf powers for different values of $k$ do not collapse: for all $k \ge 4$, there exists a $k$-leaf power which is not a $(k+1)$-leaf power [10].

2 Preliminaries

**2.1 Definitions**

Throughout this paper, we let $G(V, E)$ denote a simple undirected graph (typically, the input to the leaf power recognition problem). If $u$ and $v$ are two vertices in $V$ that are adjacent in $G$, we let $e(u, v)$ denote the edge connecting them.

The strong product of graphs $G_1$ and $G_2$, denoted as $G_1 \boxtimes G_2$, is a graph whose vertices are ordered pairs of a vertex from $G_1$ and a vertex from $G_2$. In it, two distinct vertices $(u_1, u_2)$ and $(v_1, v_2)$ are adjacent if and only if for all $i \in \{1, 2\}$, $u_i = v_i$ or $u_i$ and $v_i$ are adjacent in $G_i$. Figure 3 shows an example, the strong product of a four-vertex path graph
with a four-vertex cycle graph. When we construct a strong product, we will classify the edges of the product into three subsets:

- We call an edge from $(u_1, u_2)$ to $(v_1, v_2)$ a *vertical edge* if $u_2 = v_2$. The edges of this type form $|V(G_2)|$ disjoint copies of $G_1$ as subgraphs of the product.

- We call an edge from $(u_1, u_2)$ to $(v_1, v_2)$ a *horizontal edge* if $u_1 = v_1$. The edges of this type form $|V(G_1)|$ disjoint copies of $G_2$ as subgraphs of the product.

- We call the remaining edges, for which $u_1 \neq v_1$ and $u_2 \neq v_2$, *diagonal edges*. The subgraph composed of the diagonal edges forms a different kind of graph product, the *tensor product* $G_1 \times G_2$.

We may think of these three edge sets as forming an (improper) edge coloring of the product graph. In Figure 3 these edge sets are colored blue, red and green, respectively.

## 2.2 Graph Parameters

One of the simplest ways of parameterizing sparse graphs is by their *degeneracy*. The degeneracy $d(G)$ of a graph $G$ is the smallest number such that every nonempty subgraph of $G$ contains at least one vertex of degree at most $d(G)$. It may be computed in linear-time by a greedy algorithm that repeatedly removes the minimum-degree vertex and records the largest degree seen among the vertices at the time they are removed [28].

The notion of *treewidth*, a more complicated graph sparsity parameter, was first introduced by Bertelé and Brioschi [3] and Halin [25] and later rediscovered by Robertson and Seymour [31]. One way to define treewidth is to use the concept of tree decomposition. A tree decomposition of graph $G$ consists of a tree $T$ where each vertex $X_i \in T$ (called a bag) is a subset of vertices of $G$. This tree and its bags are required to satisfy the following properties:

- For each edge $e(u, v)$ in $G$, there exists a bag in $T$ containing both $u$ and $v$; and

- For each vertex $v$ in $G$, the bags containing $v$ form a nonempty connected subtree of $T$. The width of a tree decomposition is the size of its largest bag, minus one. The treewidth of a graph is defined as the minimum width achieved over all tree decompositions of the graph. Bounded treewidth graphs are especially interesting from an algorithmic point of view. Many well-known NP-complete problems have linear-time algorithms on graphs of bounded treewidth [4].

Another related graph parameter, *clique-width*, was introduced by Courcelle et al. to characterize the structural complexity of graphs [16]. The clique-width of a graph $G$ is the minimum number of labels necessary to construct $G$ by means of four graph operations: creation of a new vertex with a label, vertex disjoint union of labeled graphs, insertion of an edge between two vertices with specified labels and relabeling of vertices. Relevantly for us, Courcelle et al. showed that unit interval graphs are of unbounded clique-width. A graph is an interval graph if and only if all its vertices can be mapped into intervals on a straight line such that two vertices are adjacent when the corresponding intervals intersect each other. In the unit interval graphs, each interval has a unit length. As shown by Brandstädt et al., unit interval graphs belong to the class of leaf powers, which implies that leaf powers also have unbounded clique-width [5, 6]. However, Gurski and Wanke proved that for a fixed $k$, $k$-leaf powers have a clique-width of at most $k + \max(\lfloor \frac{k}{2} \rfloor - 2, 0)$ [24]. Therefore, when seeking the complexity of recognizing leaf powers, parameterized by $k$, we may restrict our attention to graphs of bounded clique-width.

These three properties are defined differently to each other, and may have significantly different values. For instance, the complete bipartite graph $K_{n,n}$ has clique-width two but treewidth and degeneracy $n$, and the $n \times n$ grid graph has degeneracy two but clique-width and treewidth $\Omega(n)$. Nevertheless, there is an important relation between them: in the
with a four-vertex cycle graph. When we construct a strong product, we will classify the edges of the product into three subsets:

- We call an edge from $(u_1, u_2)$ to $(v_1, v_2)$ a *vertical edge* if $u_2 = v_2$. The edges of this type form $|V(G_2)|$ disjoint copies of $G_1$ as subgraphs of the product.

- We call an edge from $(u_1, u_2)$ to $(v_1, v_2)$ a *horizontal edge* if $u_1 = v_1$. The edges of this type form $|V(G_1)|$ disjoint copies of $G_2$ as subgraphs of the product.

- We call the remaining edges, for which $u_1 \neq v_1$ and $u_2 \neq v_2$, *diagonal edges*. The subgraph composed of the diagonal edges forms a different kind of graph product, the *tensor product* $G_1 \times G_2$.

We may think of these three edge sets as forming an (improper) edge coloring of the product graph. In Figure 3 these edge sets are colored blue, red and green, respectively.

## 2.2 Graph Parameters

One of the simplest ways of parameterizing sparse graphs is by their *degeneracy*. The degeneracy $d(G)$ of a graph $G$ is the smallest number such that every nonempty subgraph of $G$ contains at least one vertex of degree at most $d(G)$. It may be computed in linear-time by a greedy algorithm that repeatedly removes the minimum-degree vertex and records the largest degree seen among the vertices at the time they are removed [28].

The notion of *treewidth*, a more complicated graph sparsity parameter, was first introduced by Bertelé and Brioschi [3] and Halin [25] and later rediscovered by Robertson and Seymour [31]. One way to define treewidth is to use the concept of tree decomposition. A tree decomposition of graph $G$ consists of a tree $T$ where each vertex $X_i \in T$ (called a bag) is a subset of vertices of $G$. This tree and its bags are required to satisfy the following properties:

- For each edge $e(u, v)$ in $G$, there exists a bag in $T$ containing both $u$ and $v$; and

- For each vertex $v$ in $G$, the bags containing $v$ form a nonempty connected subtree of $T$. The width of a tree decomposition is the size of its largest bag, minus one. The treewidth of a graph is defined as the minimum width achieved over all tree decompositions of the graph. Bounded treewidth graphs are especially interesting from an algorithmic point of view. Many well-known NP-complete problems have linear-time algorithms on graphs of bounded treewidth [4].

Another related graph parameter, *clique-width*, was introduced by Courcelle et al. to characterize the structural complexity of graphs [16]. The clique-width of a graph $G$ is the minimum number of labels necessary to construct $G$ by means of four graph operations: creation of a new vertex with a label, vertex disjoint union of labeled graphs, insertion of an edge between two vertices with specified labels and relabeling of vertices. Relevantly for us, Courcelle et al. showed that unit interval graphs are of unbounded clique-width. A graph is an interval graph if and only if all its vertices can be mapped into intervals on a straight line such that two vertices are adjacent when the corresponding intervals intersect each other. In the unit interval graphs, each interval has a unit length. As shown by Brandstädt et al., unit interval graphs belong to the class of leaf powers, which implies that leaf powers also have unbounded clique-width [5, 6]. However, Gurski and Wanke proved that for a fixed $k$, $k$-leaf powers have a clique-width of at most $k + \max(\lfloor \frac{k}{2} \rfloor - 2, 0)$ [24]. Therefore, when seeking the complexity of recognizing leaf powers, parameterized by $k$, we may restrict our attention to graphs of bounded clique-width.

These three properties are defined differently to each other, and may have significantly different values. For instance, the complete bipartite graph $K_{n,n}$ has clique-width two but treewidth and degeneracy $n$, and the $n \times n$ grid graph has degeneracy two but clique-width and treewidth $\Omega(n)$. Nevertheless, there is an important relation between them: in the
16:6 Parameterized Leaf Power Recognition

graphs of bounded degeneracy and bounded clique-width, the treewidth is also bounded.
More specifically, if a graph has clique-width *k* and contains no complete bipartite subgraph
*K*<sub>*t*,*t*</sub>, then it has treewidth at most 3*K*(*t* − 1) − 1. Since such a subgraph would force the
degeneracy to be at least *t*, it follows that the graphs of degeneracy *d* and clique-width *k*
have treewidth at most 3*d* − 1 [23].

2.3 Courcelle's Theorem

By considering graphs as logical structures, their properties can be expressed in first-order
and second-order logic. In first-order logic, graph properties are expressed as logical formulas
wherein the variables range over vertices and the predicates include equality and adjacency
relations. Second-order logic is an extension of first-order logic with the power to quantify
over relations. Particularly, many natural graph properties can be described in monadic
second-order logic, which is a restriction of second-order logic in which only unary relations
(sets of vertices or edges) are allowed [15].

There exist two variations of monadic second-order logic: MSO<sub>1</sub> and MSO<sub>2</sub>. In MSO<sub>1</sub>, quantification is allowed only over sets of vertices, while MSO<sub>2</sub> allows quantification over both sets of vertices and sets of edges. MSO<sub>2</sub> is strictly more expressive; there are some properties, such as Hamiltonicity [14], which are expressible in MSO<sub>2</sub> but not in MSO<sub>1</sub>. A graph property is MSO<sub>2</sub>-expressible if there exists an MSO<sub>2</sub> formula to express it, in which case the corresponding class of graphs becomes MSO<sub>2</sub>-definable.

The connection between treewidth and monadic second-order logic is given by Courcelle's theorem, according to which every property definable in monadic second-order logic can be tested in linear time on graphs of bounded treewidth [13]. Later, Courcelle et al. extended this theorem to the class of graphs with bounded clique-width when the underlying property is MSO₁-definable [17]. In our application of Courcelle's theorem, we will use an MSO₂ formula with a free variable HORIZONTAL, an edge set, which we will use to pass to the formula certain information about the structural decomposition of the graph it is operating on. This extension of Courcelle's theorem to formulas with a constant number of additional free variables, whose values are assigned through some extra-logical process prior to applying the theorem, is non-problematic and standard.

However, even in MSO₂, it is only possible to quantify over subsets of vertices and edges that belong to the graph to which the logical formula is applied. Much of the difficulty of the leaf power problem rests in this restriction. If we could quantify over edges and vertices that were not already present, we could construct a formula that asserts the existence of sets of vertices and edges forming a leaf root of a given graph, and then add clauses to the formula that ensure that the quantified sets describe a valid leaf root. However, we are not allowed such quantification, because in general the leaf root has vertices and edges that do not belong to our input graph. To apply Courcelle's theorem to leaf power recognition, we must instead find a way to express the property of being a leaf power using only quantification over subsets of vertices and edges of the graph to which we apply the theorem. For this reason, the problem of leaf power recognition forms an important test case for the ability to express graph problems in MSO logic.

A problem is *fixed-parameter tractable* with respect to a parameter *x* of the input if the problem can be solved in time *f(x)n<sup>O(1)</sup>* where *n* is the size of the input, *f* is a computable function of *x* (independent of *n*), and the exponent of *n* in the *O(1)* term is independent of *x*. Courcelle's theorem is the foundation of many fixed-parameter tractable algorithms [2, 22, 20, 26], as it proves that properties expressible in MSO<sub>1</sub> or MSO<sub>2</sub> are fixed-parameter tractable with respect to the clique-width or treewidth (respectively) of the input graph.
16:6 Parameterized Leaf Power Recognition

graphs of bounded degeneracy and bounded clique-width, the treewidth is also bounded.
More specifically, if a graph has clique-width *k* and contains no complete bipartite subgraph
*K*<sub>*t*,*t*</sub>, then it has treewidth at most 3*K*(*t* − 1) − 1. Since such a subgraph would force the
degeneracy to be at least *t*, it follows that the graphs of degeneracy *d* and clique-width *k*
have treewidth at most 3*d* − 1 [23].

2.3 Courcelle's Theorem

By considering graphs as logical structures, their properties can be expressed in first-order
and second-order logic. In first-order logic, graph properties are expressed as logical formulas
wherein the variables range over vertices and the predicates include equality and adjacency
relations. Second-order logic is an extension of first-order logic with the power to quantify
over relations. Particularly, many natural graph properties can be described in monadic
second-order logic, which is a restriction of second-order logic in which only unary relations
(sets of vertices or edges) are allowed [15].

There exist two variations of monadic second-order logic: MSO₁ and MSO₂. In MSO₁,
quantification is allowed only over sets of vertices, while MSO₂ allows quantification over
both sets of vertices and sets of edges. MSO₂ is strictly more expressive; there are some
properties, such as Hamiltonicity [14], which are expressible in MSO₂ but not in MSO₁. A
graph property is MSO₂-*expressible* if there exists an MSO₂ formula to express it, in which
case the corresponding class of graphs becomes MSO₂-*definable*.

The connection between treewidth and monadic second-order logic is given by Courcelle's theorem, according to which every property definable in monadic second-order logic can be tested in linear time on graphs of bounded treewidth [13]. Later, Courcelle et al. extended this theorem to the class of graphs with bounded clique-width when the underlying property is MSO₁-definable [17]. In our application of Courcelle's theorem, we will use an MSO₂ formula with a free variable HORIZONTAL, an edge set, which we will use to pass to the formula certain information about the structural decomposition of the graph it is operating on. This extension of Courcelle's theorem to formulas with a constant number of additional free variables, whose values are assigned through some extra-logical process prior to applying the theorem, is non-problematic and standard.

However, even in MSO₂, it is only possible to quantify over subsets of vertices and edges
that belong to the graph to which the logical formula is applied. Much of the difficulty of the
leaf power problem rests in this restriction. If we could quantify over edges and vertices that
were not already present, we could construct a formula that asserts the existence of sets of
vertices and edges forming a leaf root of a given graph, and then add clauses to the formula
that ensure that the quantified sets describe a valid leaf root. However, we are not allowed
such quantification, because in general the leaf root has vertices and edges that do not belong
to our input graph. To apply Courcelle's theorem to leaf power recognition, we must instead
find a way to express the property of being a leaf power using only quantification over subsets
of vertices and edges of the graph to which we apply the theorem. For this reason, the
problem of leaf power recognition forms an important test case for the ability to express
graph problems in MSO logic.

A problem is *fixed-parameter tractable* with respect to a parameter *x* of the input if the problem can be solved in time *f(x)n<sup>O(1)</sup>* where *n* is the size of the input, *f* is a computable function of *x* (independent of *n*), and the exponent of *n* in the *O(1)* term is independent of *x*. Courcelle's theorem is the foundation of many fixed-parameter tractable algorithms [2, 22, 20, 26], as it proves that properties expressible in MSO<sub>1</sub> or MSO<sub>2</sub> are fixed-parameter tractable with respect to the clique-width or treewidth (respectively) of the input graph.
<figure><img src="image_89.png" /><figcaption>Figure 4 A 4-leaf power graph $G$ (left), and its leaf root $T$ (right). Each leaf of $T$ is labeled by the vertex of $G$ that it represents, and each internal node of $T$ is labeled by its closest leaf node. When there are ties at a node (as for instance at the root of $T$) the choice of label is made arbitrarily among the closest leaf nodes whose labels appear among the children of the node.</figcaption></figure>

3 Embedding Leaf Roots Into Graph Products

Let $G$ be a $k$-leaf power graph, and $T$ be a $k$-leaf root of $G$. If $G$ is not connected, we can handle each of its connected components independently; in this way, we can assume from now on, without loss of generality that $G$ is a connected graph with at least three vertices, and that $T$ is a leaf root chosen arbitrarily among the possible $k$-leaf roots of $T$. It follows from these assumptions that $T$ is a tree, because every edge in $G$ must be represented by a path in $T$. Because $T$ has at least three leaves, it has at least one interior node; we choose one of these nodes arbitrarily to be the root of $T$. Additionally, every vertex or edge of $T$ participates in a path of length at most $k$ between two leaves, representing an edge of $G$. For, if some vertices and edge do not participate in these paths, removing all non-participating vertices and edges from $T$ would produce a smaller leaf root, without creating any new leaves. But this removal would disconnect pairs of leaves on the opposite sides of any removed edge, contradicting the assumption that $G$ is connected.

As the first step of the embedding, we label the vertices of $T$ with the names of vertices in $G$. Each vertex of $T$ will get a label in this way; some labels will be used more than once. In particular, we label each leaf of $T$ by the vertex of $G$ represented by that leaf. Then, as shown in Figure 4, we give each non-leaf node of $T$ the same label as its closest leaf. If there are two or more closest leaves, we choose which one to use as the label arbitrarily among the labels already applied to the child of the given interior node. In this way, when the same label appears more than once, the tree nodes having that label form a connected path in $T$.

As we now show, these labels, together with the depths of the nodes modulo $k$, can be used to embed the $k$-leaf root $T$ into the strong product $G \boxtimes C_k$, where $C_k$ denotes a $k$-vertex cycle graph.

**Lemma 1.** If $G$ is a connected $k$-leaf power graph on three or more vertices, and $T$ is any $k$-leaf root of $G$, then $T$ can be embedded as a subgraph of the strong product $G \boxtimes C_k$. Additionally, the embedding can be chosen in such a way that each horizontal cycle in the strong product (the product of a vertex $v$ of $G$ with $C_k$) contains exactly one leaf of the embedded copy of $T$, the leaf representing $v$.

**Proof.** We map a vertex $u$ of $T$ to the pair $(v, i)$ where $v$ is the label assigned to $u$ (the name of a vertex in $G$) and $i$ is the depth of $u$ (its distance from the root of $T$), taken modulo $k$. This pair is one of the vertices of the strong product, so we have mapped vertices of $T$ into vertices of the strong product. An example of such embedding can be seen in Figure
<figure><img src="image_92.png" /><figcaption>Figure 4 A 4-leaf power graph $G$ (left), and its leaf root $T$ (right). Each leaf of $T$ is labeled by the vertex of $G$ that it represents, and each internal node of $T$ is labeled by its closest leaf node. When there are ties at a node (as for instance at the root of $T$) the choice of label is made arbitrarily among the closest leaf nodes whose labels appear among the children of the node.</figcaption></figure>

### 3 Embedding Leaf Roots Into Graph Products

Let $G$ be a $k$-leaf power graph, and $T$ be a $k$-leaf root of $G$. If $G$ is not connected, we can handle each of its connected components independently; in this way, we can assume from now on, without loss of generality that $G$ is a connected graph with at least three vertices, and that $T$ is a leaf root chosen arbitrarily among the possible $k$-leaf roots of $T$. It follows from these assumptions that $T$ is a tree, because every edge in $G$ must be represented by a path in $T$. Because $T$ has at least three leaves, it has at least one interior node; we choose one of these nodes arbitrarily to be the root of $T$. Additionally, every vertex or edge of $T$ participates in a path of length at most $k$ between two leaves, representing an edge of $G$. For, if some vertices and edge do not participate in these paths, removing all non-participating vertices and edges from $T$ would produce a smaller leaf root, without creating any new leaves. But this removal would disconnect pairs of leaves on the opposite sides of any removed edge, contradicting the assumption that $G$ is connected.

As the first step of the embedding, we label the vertices of $T$ with the names of vertices in $G$. Each vertex of $T$ will get a label in this way; some labels will be used more than once. In particular, we label each leaf of $T$ by the vertex of $G$ represented by that leaf. Then, as shown in Figure 4, we give each non-leaf node of $T$ the same label as its closest leaf. If there are two or more closest leaves, we choose which one to use as the label arbitrarily among the labels already applied to the child of the given interior node. In this way, when the same label appears more than once, the tree nodes having that label form a connected path in $T$.

As we now show, these labels, together with the depths of the nodes modulo $k$, can be used to embed the $k$-leaf root $T$ into the strong product $G \boxtimes C_k$, where $C_k$ denotes a $k$-vertex cycle graph.

**Lemma 1.** If $G$ is a connected $k$-leaf power graph on three or more vertices, and $T$ is any $k$-leaf root of $G$, then $T$ can be embedded as a subgraph of the strong product $G \boxtimes C_k$. Additionally, the embedding can be chosen in such a way that each horizontal cycle in the strong product (the product of a vertex $v$ of $G$ with $C_k$) contains exactly one leaf of the embedded copy of $T$, the leaf representing $v$.

**Proof.** We map a vertex $u$ of $T$ to the pair $(v, i)$ where $v$ is the label assigned to $u$ (the name of a vertex in $G$) and $i$ is the depth of $u$ (its distance from the root of $T$), taken modulo $k$. This pair is one of the vertices of the strong product, so we have mapped vertices of $T$ into vertices of the strong product. An example of such embedding can be seen in Figure
<figure><img src="image_90.png" /><figcaption>■ **Figure 5** The graph on the bottom left is a 4-leaf root $T$ of graph $G$ (top left). $T$ can be embedded in the strong product $G \boxtimes C_4$ (right), by mapping each vertex $u$ of $T$ to the pair $(v, i)$ where $v$ is the label of $u$ and $i$ is the depth of $u$ (modulo $k$).</figcaption></figure>

Figure 5. Because $G$ is assumed to be connected, each node of $T$ participates in at least one path of length at most $k$ between two leaves of $T$, representing an adjacency of $G$; it follows that the label for each node of $T$ is at most $k-1$ steps away from the node, and that each path of same-labeled nodes in $T$ has length at most $k-1$. As a consequence, when we take depths modulo $k$, none of these paths can wrap around the cycle and cover the same vertex of the product graph more than once. That is, our mapping from $T$ to $G \boxtimes C_k$ is one-to-one. Because each leaf of $T$ is labeled with the vertex of $G$ that it represents, this mapping has the property described in the lemma, that each horizontal cycle in the strong product contains exactly one leaf of the embedded copy of $T$, the leaf representing the vertex whose product with $C_k$ forms that particular horizontal cycle.

We must also show that this mapping from $T$ to $G \boxtimes C_k$ maps each pair of vertices that are adjacent in $T$ into a pair of vertices that are adjacent in $G \boxtimes C_k$. Recall that adjacency in $G \boxtimes C_k$ is the conjunction of two conditions: two vertices in the product are adjacent if their first coordinates are equal or adjacent in $G$ and their second coordinates are equal or adjacent in $C_k$. Because every two adjacent vertices in $T$ have depths that differ by one, the second coordinates of their images in the product will always be adjacent in $C_k$. It remains to show that, when two vertices are adjacent in $T$, their images in the product have first coordinates that are equal or adjacent in $G$. That is, the labels of the two adjacent vertices in $T$ should be equal or adjacent.

Rephrasing what we still need to show, it is the following: whenever two adjacent vertices in $T$ have different labels, those labels represent adjacent vertices in $G$.

To see that this is true, consider two adjacent vertices $u_1$ and its parent $u_2$ in $T$, labeled by two different vertices $v_1$ and $v_2$ in $G$. As we already stated at the start of this section, the assumption of the lemma that $G$ is connected implies that edge $u_1u_2$ in $T$ participates in at least one path $P$ of length at most $k$ between two leaves, corresponding to an adjacency in $G$. But because $v_1$ and $v_2$ are represented by the closest leaves to $u_1$ and $u_2$ (respectively) the length of the path in $T$ between the leaves representing $v_1$ and $v_2$ must be at most equal to the length of $P$. Therefore, there is a path of length at most $k$ between the leaves representing $v_1$ and $v_2$, so $v_1$ and $v_2$ are adjacent in the $k$-leaf power $G$, as required. ◀
<figure><img src="image_93.png" /><figcaption>■ **Figure 5** The graph on the bottom left is a 4-leaf root $T$ of graph $G$ (top left). $T$ can be embedded in the strong product $G \boxtimes C_4$ (right), by mapping each vertex $u$ of $T$ to the pair $(v, i)$ where $v$ is the label of $u$ and $i$ is the depth of $u$ (modulo $k$).</figcaption></figure>

Figure 5. Because $G$ is assumed to be connected, each node of $T$ participates in at least one path of length at most $k$ between two leaves of $T$, representing an adjacency of $G$; it follows that the label for each node of $T$ is at most $k-1$ steps away from the node, and that each path of same-labeled nodes in $T$ has length at most $k-1$. As a consequence, when we take depths modulo $k$, none of these paths can wrap around the cycle and cover the same vertex of the product graph more than once. That is, our mapping from $T$ to $G \boxtimes C_k$ is one-to-one. Because each leaf of $T$ is labeled with the vertex of $G$ that it represents, this mapping has the property described in the lemma, that each horizontal cycle in the strong product contains exactly one leaf of the embedded copy of $T$, the leaf representing the vertex whose product with $C_k$ forms that particular horizontal cycle.

We must also show that this mapping from $T$ to $G \boxtimes C_k$ maps each pair of vertices that are adjacent in $T$ into a pair of vertices that are adjacent in $G \boxtimes C_k$. Recall that adjacency in $G \boxtimes C_k$ is the conjunction of two conditions: two vertices in the product are adjacent if their first coordinates are equal or adjacent in $G$ and their second coordinates are equal or adjacent in $C_k$. Because every two adjacent vertices in $T$ have depths that differ by one, the second coordinates of their images in the product will always be adjacent in $C_k$. It remains to show that, when two vertices are adjacent in $T$, their images in the product have first coordinates that are equal or adjacent in $G$. That is, the labels of the two adjacent vertices in $T$ should be equal or adjacent.

Rephrasing what we still need to show, it is the following: whenever two adjacent vertices in $T$ have different labels, those labels represent adjacent vertices in $G$.

To see that this is true, consider two adjacent vertices $u_1$ and its parent $u_2$ in $T$, labeled by two different vertices $v_1$ and $v_2$ in $G$. As we already stated at the start of this section, the assumption of the lemma that $G$ is connected implies that edge $u_1u_2$ in $T$ participates in at least one path $P$ of length at most $k$ between two leaves, corresponding to an adjacency in $G$. But because $v_1$ and $v_2$ are represented by the closest leaves to $u_1$ and $u_2$ (respectively) the length of the path in $T$ between the leaves representing $v_1$ and $v_2$ must be at most equal to the length of $P$. Therefore, there is a path of length at most $k$ between the leaves representing $v_1$ and $v_2$, so $v_1$ and $v_2$ are adjacent in the $k$-leaf power $G$, as required. ◄
Based on this embedding, we can prove the following characterization of leaf powers, which we will use in our application of Courcelle's theorem to the problem. It is important, for this characterization, that we express everything intrinsically in terms of the properties of the product graph $G \boxtimes C_k$, its edge coloring, and its subgraphs, without reference to the given graph $G$.

**Lemma 2.** A given connected graph $G$ on three or more vertices is a $k$-leaf power if and only if the product $G \boxtimes C_k$ has a subgraph $T$ with the following properties:

1. $T$ is 1-degenerate (i.e., a forest).

2. Every vertex of $G \boxtimes C_k$ is connected by horizontal edges of the product to exactly one leaf of $T$.

3. Two vertices of $G \boxtimes C_k$ are the endpoints of a non-horizontal edge of the product if and only if the corresponding leaves of $T$ (given according to Property 2) are the distinct endpoints of a path of length at most $k$ in $T$.

**Proof.** A subgraph obeying these properties is a forest (Property 1), whose leaves can be placed into one-to-one correspondence with the vertices of $G$ (Property 2, using the fact that the horizontal cycles of the product correspond one-for-one with vertices of $G$). It has a path of length at most $k$ between two leaves if and only if the corresponding vertices of $G$ are adjacent (Property 3). So if it exists, it is a $k$-leaf root of $G$ and $G$ is a $k$-leaf power.

In the other direction, if $G$ is a connected $k$-leaf power, let $T$ be a $k$-leaf root of $G$, embedded according to Lemma 1. Then $T$ is a subtree of the product graph (Property 1), with exactly one leaf for each horizontal cycle (Property 2), that forms a $k$-leaf root of $G$ (Property 3). So when $G$ is a $k$-leaf power, a subgraph $T$ obeying the properties of the lemma exists. ◀

## 4 Logical Expression

In this section, we describe how to express the components of Lemma 2, our characterization of the products $G \boxtimes C_k$ that contain a $k$-leaf root of $G$, in monadic second-order logic. Our logical formula will involve a free variable `HORIZONTAL`, the subset of edges of the given graph (assumed to be of the form $G \boxtimes C_k$) that are horizontal in the product (that is, edges that connect two copies of the same vertex in $G$). We will also assume that $V$ and $E$ refer to the vertices and edges of the graph $G \boxtimes C_k$. In our logical formulas, we will express the type of each quantified variable (whether it is a vertex, edge, set of vertices, or set of edges) by annotating its quantifier with a membership or subset relation. For instance, "$\forall x \in V : ...$" quantifies $x$ as a vertex variable. We will express the incidence predicate between an edge $e$ and a vertex $v$ (true if $v$ is an endpoint of $e$, false otherwise) by $e \to v$. Because our formulas will also use equality as a predicate, we will express the equality between names of formulas and their explicit logical formulation using a different symbol, $\equiv$. In our formulas, predicates (equality, incidence, and adjacency) will be considered to bind more tightly than logical connectives, allowing us to omit parentheses in many cases.

A subgraph of the given graph may be represented by its set $S$ of edges. In this representation, adjacency between two vertices $a$ and $b$ may be expressed by the formula

$$ \mathrm{ADJACENT}(a, b, S) \equiv \exists e \in S : (e \to a \land e \to b). $$

The following formula expresses the property that the neighbors of vertex $\ell$ in subgraph $S$ include at most one vertex from a set $X$:

$$ \mathrm{LEAF}(\ell, X, S) \equiv \forall c, d \in X : ((\mathrm{ADJACENT}(\ell, c, S) \land \mathrm{ADJACENT}(\ell, d, S)) \to c = d). $$
Based on this embedding, we can prove the following characterization of leaf powers, which we will use in our application of Courcelle's theorem to the problem. It is important, for this characterization, that we express everything intrinsically in terms of the properties of the product graph $G \boxtimes C_k$, its edge coloring, and its subgraphs, without reference to the given graph $G$.

**Lemma 2.** A given connected graph $G$ on three or more vertices is a $k$-leaf power if and only if the product $G \boxtimes C_k$ has a subgraph $T$ with the following properties:

1. $T$ is 1-degenerate (i.e., a forest).

2. Every vertex of $G \boxtimes C_k$ is connected by horizontal edges of the product to exactly one leaf of $T$.

3. Two vertices of $G \boxtimes C_k$ are the endpoints of a non-horizontal edge of the product if and only if the corresponding leaves of $T$ (given according to Property 2) are the distinct endpoints of a path of length at most $k$ in $T$.

**Proof.** A subgraph obeying these properties is a forest (Property 1), whose leaves can be placed into one-to-one correspondence with the vertices of $G$ (Property 2, using the fact that the horizontal cycles of the product correspond one-for-one with vertices of $G$). It has a path of length at most $k$ between two leaves if and only if the corresponding vertices of $G$ are adjacent (Property 3). So if it exists, it is a $k$-leaf root of $G$ and $G$ is a $k$-leaf power.

In the other direction, if $G$ is a connected $k$-leaf power, let $T$ be a $k$-leaf root of $G$, embedded according to Lemma 1. Then $T$ is a subtree of the product graph (Property 1), with exactly one leaf for each horizontal cycle (Property 2), that forms a $k$-leaf root of $G$ (Property 3). So when $G$ is a $k$-leaf power, a subgraph $T$ obeying the properties of the lemma exists. ◀

## 4 Logical Expression

In this section, we describe how to express the components of Lemma 2, our characterization of the products $G \boxtimes C_k$ that contain a $k$-leaf root of $G$, in monadic second-order logic. Our logical formula will involve a free variable `HORIZONTAL`, the subset of edges of the given graph (assumed to be of the form $G \boxtimes C_k$) that are horizontal in the product (that is, edges that connect two copies of the same vertex in $G$). We will also assume that $V$ and $E$ refer to the vertices and edges of the graph $G \boxtimes C_k$. In our logical formulas, we will express the type of each quantified variable (whether it is a vertex, edge, set of vertices, or set of edges) by annotating its quantifier with a membership or subset relation. For instance, "$\forall x \in V : ...$" quantifies $x$ as a vertex variable. We will express the incidence predicate between an edge $e$ and a vertex $v$ (true if $v$ is an endpoint of $e$, false otherwise) by $e \to v$. Because our formulas will also use equality as a predicate, we will express the equality between names of formulas and their explicit logical formulation using a different symbol, $\equiv$. In our formulas, predicates (equality, incidence, and adjacency) will be considered to bind more tightly than logical connectives, allowing us to omit parentheses in many cases.

A subgraph of the given graph may be represented by its set $S$ of edges. In this representation, adjacency between two vertices $a$ and $b$ may be expressed by the formula

$$ \mathrm{ADJACENT}(a, b, S) \equiv \exists e \in S : (e \to a \land e \to b). $$

The following formula expresses the property that the neighbors of vertex $\ell$ in subgraph $S$ include at most one vertex from a set $X$:

$$ \mathrm{LEAF}(\ell, X, S) \equiv \forall c, d \in X : ((\mathrm{ADJACENT}(\ell, c, S) \land \mathrm{ADJACENT}(\ell, d, S)) \to c = d). $$
16:10 Parameterized Leaf Power Recognition

This allows us to express the acyclicity of a subgraph $S$ in terms of 1-degeneracy: every nonempty subset $Y$ of vertices contains a leaf.

$$ \text{ACYCLIC}(S) \equiv \forall X \subset V : (\exists x \in X) \rightarrow \exists \ell \in X : \text{LEAF}(\ell, X, S). $$

This already allows us to express the first condition of Lemma 2.

We will also use a predicate for whether two vertices $p$ and $q$ are connected by horizontal edges. This is true if there is no cut $(C, V \setminus C)$ that separates them.

$$ \begin{array}{l} \text{ALIGNED}(p, q) \equiv \forall C \subset V : (p \in C \land \neg(q \in C)) \rightarrow \\ \phantom{\text{ALIGNED}(p, q) \equiv \forall C \subset V : (p \in C \land \neg(q \in C)) \rightarrow} \exists h \in \text{HORIZONTAL} : \exists y, z \in V : (y \in C \land \neg(z \in C) \land h \to y \land h \to z). \end{array} $$

This allows us to express a predicate for the property that vertex $\ell$ is a leaf of subgraph $S$ on the same horizontal level as another vertex $v$ (that is, $\ell$ is the representative leaf for $v$'s level):

$$ \text{REPRESENTATIVE}(v, \ell, S) \equiv \text{LEAF}(\ell, V, S) \land \text{ALIGNED}(v, \ell). $$

The second part of Lemma 2 is that every level has exactly one representative leaf:

$$ \begin{array}{l} \text{REPRESENTED}(S) \equiv (\forall v \in V : \exists \ell \in V : \text{REPRESENTATIVE}(v, \ell, S)) \land \\ \phantom{\text{REPRESENTED}(S) \equiv (\forall v \in V : \exists \ell \in V : \text{REPRESENTATIVE}(v, \ell, S)) \land} (\forall v, \ell_1, \ell_2 \in V : (\text{REPRESENTATIVE}(v, \ell_1, S) \land \text{REPRESENTATIVE}(v, \ell_2, S)) \rightarrow \ell_1 = \ell_2) \end{array} $$

Unlike for the previous formulas, there is no way of expressing the existence of a path of length $k$ from $u$ to $v$ in subgraph $S$, for a variable $k$, in $\text{MSO}_2$. We need a different formula $\text{PATH}_k$ for each $k$. We do not require these paths to be simple, as this would only complicate the formula without simplifying our use of it. However it is essential for our application to the third condition of Lemma 2 that we require our paths to have distinct endpoints.

$$ \begin{array}{l} \text{PATH}_k(u, v, S) \equiv \exists w_1, w_2, \dots w_{k-1} \in V : \exists e_1, e_2, \dots e_k \in S : \\ \phantom{\text{PATH}_k(u, v, S) \equiv \exists w_1, w_2, \dots w_{k-1} \in V : \exists e_1, e_2, \dots e_k \in S :} \neg(u = v) \land e_1 \to u \land e_1 \to w_1 \land e_2 \to w_1 \land \dots \land e_k \to w_{k-1} \land e_k \to v. \end{array} $$

Other than the inequality of the two endpoints, this formula allows repetitions of vertices and edges within each path. In particular, it allows $w_i$ and $w_{i+1}$ to be equal to each other, repeating one endpoint of an edge twice and omitting the other endpoint. Because we allow repetitions in this way, this formulation of the PATH predicate has the following convenient property:

**Lemma 3.** For all $k \ge 1$ and all $u, v$, and $S$, we have that

$$ \text{PATH}_k(u, v, S) \rightarrow \text{PATH}_{k+1}(u, v, S). $$

**Proof.** Let $w_1, \dots, w_{k-1}$ and $e_1, \dots, e_k$ be the vertices and edges witnessing the truth of $\text{PATH}_k(u, v, S)$, let $w_k = v$, and let $e_{k+1} = e_k$. Then $w_1, \dots, w_k$ and $e_1, \dots, e_{k+1}$ witness the truth of $\text{PATH}_{k+1}(u, v, S)$. $\quad \blacksquare$

**Corollary 4.** Two vertices $u$ and $v$ of a subgraph $S$ of a given graph obey the predicate $\text{PATH}_k(u, v, S)$ if and only if they are distinct and their distance in $S$ is at most $k$.

This allows us to express the final part of Lemma 2, the requirement that each two vertices are connected by a non-horizontal edge if and only if their representatives are connected by a short path:

$$ \begin{array}{l} \text{ROOT}_k(S) \equiv \forall u, v \in V : ((\exists e \in E : e \to u \land e \to v \land \neg(e \in \text{HORIZONTAL})) \leftrightarrow \\ \phantom{\text{ROOT}_k(S) \equiv \forall u, v \in V : ((\exists e \in E : e \to u \land e \to v \land \neg(e \in \text{HORIZONTAL})) \leftrightarrow} \exists x, y \in V : (\text{REPRESENTATIVE}(u, x, S) \land \text{REPRESENTATIVE}(v, y, S) \land \text{PATH}_k(x, y, S)). \end{array} $$
16:10 Parameterized Leaf Power Recognition

This allows us to express the acyclicity of a subgraph $S$ in terms of 1-degeneracy: every nonempty subset $Y$ of vertices contains a leaf.

$$ \text{ACYCLIC}(S) \equiv \forall X \subset V : (\exists x \in X) \rightarrow \exists l \in X : \text{LEAF}(l, X, S). $$

This already allows us to express the first condition of Lemma 2.

We will also use a predicate for whether two vertices $p$ and $q$ are connected by horizontal edges. This is true if there is no cut $(C, V \setminus C)$ that separates them.

$$ \begin{gathered} \text{ALIGNED}(p, q) \equiv \forall C \subset V : (p \in C \land \neg(q \in C)) \rightarrow \\ \exists h \in \text{HORIZONTAL} : \exists y, z \in V : (y \in C \land \neg(z \in C) \land h \to y \land h \to z). \end{gathered} $$

This allows us to express a predicate for the property that vertex $l$ is a leaf of subgraph $S$ on the same horizontal level as another vertex $v$ (that is, $l$ is the representative leaf for $v$'s level):

$$ \text{REPRESENTATIVE}(v, l, S) \equiv \text{LEAF}(l, V, S) \land \text{ALIGNED}(v, l). $$

The second part of Lemma 2 is that every level has exactly one representative leaf:

$$ \begin{gathered} \text{REPRESENTED}(S) \equiv (\forall v \in V : \exists l \in V : \text{REPRESENTATIVE}(v, l, S)) \land \\ (\forall v, l_1, l_2 \in V : (\text{REPRESENTATIVE}(v, l_1, S) \land \text{REPRESENTATIVE}(v, l_2, S)) \rightarrow l_1 = l_2) \end{gathered} $$

Unlike for the previous formulas, there is no way of expressing the existence of a path of length $k$ from $u$ to $v$ in subgraph $S$, for a variable $k$, in $\text{MSO}_2$. We need a different formula $\text{PATH}_k$ for each $k$. We do not require these paths to be simple, as this would only complicate the formula without simplifying our use of it. However it is essential for our application to the third condition of Lemma 2 that we require our paths to have distinct endpoints.

$$ \begin{gathered} \text{PATH}_k(u, v, S) \equiv \exists w_1, w_2, \dots w_{k-1} \in V : \exists e_1, e_2, \dots e_k \in S : \\ \neg(u = v) \land e_1 \to u \land e_1 \to w_1 \land e_2 \to w_1 \land \dots \land e_k \to w_{k-1} \land e_k \to v. \end{gathered} $$

Other than the inequality of the two endpoints, this formula allows repetitions of vertices and edges within each path. In particular, it allows $w_i$ and $w_{i+1}$ to be equal to each other, repeating one endpoint of an edge twice and omitting the other endpoint. Because we allow repetitions in this way, this formulation of the PATH predicate has the following convenient property:

**Lemma 3.** For all $k \ge 1$ and all $u, v$, and $S$, we have that

$$ \text{PATH}_k(u, v, S) \rightarrow \text{PATH}_{k+1}(u, v, S). $$

*Proof.* Let $w_1, \dots, w_{k-1}$ and $e_1, \dots, e_k$ be the vertices and edges witnessing the truth of $\text{PATH}_k(u, v, S)$, let $w_k = v$, and let $e_{k+1} = e_k$. Then $w_1, \dots, w_k$ and $e_1, \dots, e_{k+1}$ witness the truth of $\text{PATH}_{k+1}(u, v, S)$. $\quad \blacksquare$

**Corollary 4.** Two vertices $u$ and $v$ of a subgraph $S$ of a given graph obey the predicate $\text{PATH}_k(u, v, S)$ if and only if they are distinct and their distance in $S$ is at most $k$.

This allows us to express the final part of Lemma 2, the requirement that each two vertices are connected by a non-horizontal edge if and only if their representatives are connected by a short path:

$$ \begin{gathered} \text{ROOT}_k(S) \equiv \forall u, v \in V : ((\exists e \in E : e \to u \land e \to v \land \neg(e \in \text{HORIZONTAL})) \leftrightarrow \\ \exists x, y \in V : (\text{REPRESENTATIVE}(u, x, S) \land \text{REPRESENTATIVE}(v, y, S) \land \text{PATH}_k(x, y, S)). \end{gathered} $$