Treedepth Inapproximability and
Exponential ETH Lower Bound

In this work, we design a simple linear reduction from Satisfiability to Treedepth. It draws inspiration from a recent similar result for Treewidth [4], and also relies on the hardness of Vertex Cover (i.e., the task of finding a smallest vertex subset hitting every edge) on tripartite graphs. Our reduction yields the following inapproximability results and computational lower bounds for Treedepth.

In particular, the theorem rules out a polynomial-time approximation scheme (PTAS) for Treedepth (assuming $\text{P}\ne \text{NP}$).

This also excludes $2^{o(k)}{n}^{O(1)}$-time parameterized exact algorithms for the problem under ETH.

In fact, we obtain that even approximating treedepth to a small constant factor requires almost exponential time.

All three results follow the same reduction chain. First, we transform a Satisfiability instance into an instance of Vertex Cover on tripartite graphs. Then, we reduce the Vertex Cover problem on tripartite graphs to Treedepth. We first describe the second step of the reduction chain in Section 3. In Section 4, we then describe the first step, and deduce Theorems 1, 2, and 3.

Let $S$ be the minimum vertex cover of $G$. Then $H-S$ has three connected components, namely, for each $X\in \{A,B,C\}$, the subgraph of $H$ induced by $K_X\cup \{z_X\}\cup (X\setminus S)$. Noting that $|K_X|=\mathrm{\ell }$ and $\{z_X\}\cup (X\setminus S)$ is an independent set in $H$, we have $\text{td}(H[K_X\cup \{z_X\}\cup (X\setminus S)])⩽|K_X|+1=\mathrm{\ell }+1$, and therefore

We now move to the lower bound on $\text{td}(H)$. Aiming for contradiction, suppose that $\text{td}(H)⩽\text{vc}(G)+\mathrm{\ell }$; then there exists an elimination forest $F$ of $H$ of depth at most $\text{vc}(G)+\mathrm{\ell }$.

By Observation 4, for each $X\in \{A,B,C\}$, all vertices of $K_X$ belong to a single root-to-leaf path (possibly different for different choices of $X$). We can thus choose three vertices ${\kappa }_A\in K_A$, ${\kappa }_B\in K_B$, ${\kappa }_C\in K_C$ as the deepest vertices of the respective cliques in $F$.

All vertices of $K_X$ are ancestors of ${\kappa }_X$, and $z_X$ is either an ancestor or a descendant of ${\kappa }_X$. In either case, vertices of $R\cup K_X\cup \{z_X\}$ lie on a single root-to-leaf path in $F$, implying that the depth of $F$ is at least $|R|+\mathrm{\ell }+1$. $\mathrm{⊲}$

Suppose without loss of generality that ${\kappa }_A$ is an ancestor of ${\kappa }_B$. Then all vertices of $K_A$ are ancestors of ${\kappa }_B$, so from Claim 7 we infer that the depth of $F$ is at least $|K_A|+\mathrm{\ell }+1=2\mathrm{\ell }+1>\text{vc}(G)+\mathrm{\ell }$; a contradiction. $\mathrm{⊲}$

Let $R=\{v_X,v_Y,{\kappa }_X,{\kappa }_Y\}$. Noting that ${\kappa }_X{v}_X{v}_Y{\kappa }_Y$ is a path in $H$, we have by Observation 5 that some vertex of $R$ is an ancestor of all vertices in $R$. Since ${\kappa }_X$ and ${\kappa }_Y$ are not in the ancestor–descendant relationship (Claim 8), the claim follows. $\mathrm{⊲}$

Let us now resolve a degenerate case where at least one of the sides of $G$ (say, $C$) is not incident to any edge in $G$. Define $Q$ to be the set of vertices of $A\cup B$ that are ancestors of both ${\kappa }_A$ and ${\kappa }_B$; by Claim 9, $Q$ is a vertex cover of $G$. Hence by Claim 7 for $X=A$, the depth of $F$ is at least $|Q|+\mathrm{\ell }+1>\text{vc}(G)+\mathrm{\ell }$; a contradiction.

Thus each side of $G$ is incident to an edge of $G$. Therefore, we can easily verify that $H$ is connected and so $F$ is a single rooted tree. Let then $u_{AB}$ be the lowest common ancestor of ${\kappa }_A$ and ${\kappa }_B$ in $F$; analogously define $u_{BC}$ and $u_{CA}$. The three newly defined vertices pairwise remain in the ancestor–descendant relationship: for instance, $u_{AB}$ and $u_{BC}$ are both ancestors of ${\kappa }_B$, so one of them is an ancestor of the other. In particular, $u_{AB}$, $u_{BC}$ and $u_{CA}$ lie on a single root-to-leaf path, and (at least) one of these vertices – say, $u_{AB}$ – is a descendant of all three. Let $Q\subseteq V$ be the set of vertices of $G$ that are ancestors of ${\kappa }_A$. Applying Claim 9 multiple times, we observe that:

• $\mathrm{■}$

  for each $v_A{v}_B\in E(G)$ with $v_A\in A$, $v_B\in B$, we get $v_A\in Q$ or $v_B\in Q$;

• $\mathrm{■}$

  for each $v_A{v}_C\in E(G)$ with $v_A\in A$, $v_C\in C$, we get $v_A\in Q$ or $v_C\in Q$;

• $\mathrm{■}$

  for each $v_B{v}_C\in E(G)$ with $v_B\in B$, $v_C\in C$, we get that $v_B$ or $v_C$ is an ancestor of both ${\kappa }_B$ and ${\kappa }_C$ in $F$; hence it is also an ancestor of $u_{BC}$, so also an ancestor of $u_{AB}$ and thus also ${\kappa }_A$. Consequently $v_B\in Q$ or $v_C\in Q$.

We conclude that $Q$ is a vertex cover of $G$; and so by Claim 7, the depth of $F$ is at least $|Q|+\mathrm{\ell }+1>\text{vc}(G)+\mathrm{\ell }$; a contradiction. $◀$

First, suppose that $F$ is a valuation of variables of $\phi$ that satisfies $m^{\prime }$ clauses; we think of $F$ as a set of literals that includes exactly one literal from $\{x_j,\neg x_j\}$ for each variable $x_j$. We define a set $S$ of vertices of $G(\phi ,p)$ by including:

• $\mathrm{■}$

  every vertex of the form $a_i(s_1,\mathrm{\dots },s_k)\in A$ such that $\{s_1,\mathrm{\dots },s_k\}⊈F$; and

• $\mathrm{■}$

  all vertices of $B({\mathrm{\ell }}_j)$ for every literal ${\mathrm{\ell }}_j\in F$.

Observe that $S$ is a vertex cover of $G(\phi ,p)$. Indeed, every edge between $B_{+}$ and $B_{-}$ is covered by $S$. Next, consider the edges between $A$ and $B:=B_{+}\cup B_{-}$. Pick a vertex $a_i(s_1,\mathrm{\dots },s_k)\in A\setminus S$. Every neighbor of this vertex belongs to $B(s_1)\cup \mathrm{\dots }\cup B(s_k)$. By construction of $S\cap A$, we have $\{s_1,\mathrm{\dots },s_k\}\subseteq F$, and so $B(s_1)\cup \mathrm{\dots }\cup B(s_k)\subseteq S$.

Now let us determine the size of $S$. Since $F$ satisfies $m^{\prime }$ clauses of $\phi$, there exist exactly $m^{\prime }$ vertices of the form $a_i(s_1,\mathrm{\dots },s_k)\in A$ such that $s_1,\mathrm{\dots },s_k\in F$. These are precisely the vertices of $A$ that do not belong to $S$. Therefore $|A\setminus S|=m^{\prime }$ and so $|S\cap A|=(2^k-1)m-m^{\prime }$. Also, $|S\cap B|=\gamma n=2^{k-1}pn$. Therefore, $|S|=(2^k-1)m-m^{\prime }+2^{k-1}pn$.

On the other hand, suppose that $S$ is a minimum-cardinality vertex cover of $G(\phi ,p)$; and out of those, $S$ contains the fewest number of vertices of $B$. Assume that $|S|⩽(2^k-1)m-m^{\prime \prime }+2^{k-1}pn$, aiming to show that at least $m^{\prime \prime }$ clauses of $\phi$ can be satisfied.

For every variable $x_j$ of $\phi$, each of the sets $B_{+}(x_j)$ and $B_{-}(x_j)$ is a set of twins in $G(\phi ,p)$, so $S$ either contains it fully or is disjoint from it; and moreover, $S$ must contain at least one of the sets $B_{+}(x_j)$ and $B_{-}(x_j)$ since the vertices of both sets are connected by a complete bipartite graph. Suppose now that $S$ contains both sets $B_{+}(x_j)$ and $B_{-}(x_j)$. Since the variable $x_j$ appears at most $2p+1$ times in $\phi$, we can pick a literal ${\mathrm{\ell }}_j\in \{x_j,\neg x_j\}$ that appears at most $p$ times in $\phi$. Consider now the following set $S^{\star }$:

Observing that $S^{\star }$ is formed from $S$ by removing $B({\mathrm{\ell }}_j)$ and introducing all neighbors of $B({\mathrm{\ell }}_j)$ in $G(\phi ,p)$, we conclude that $S^{\star }$ is also a vertex cover of $G(\phi ,p)$. Since $|B({\mathrm{\ell }}_j)|=\gamma$, $B({\mathrm{\ell }}_j)\subseteq S$ and ${\mathrm{\ell }}_j$ appears at most $p$ times in $\phi$, the cardinality of $S^{\star }$ is at most $|S^{\star }|⩽|S|-\gamma +2^{k-1}p=|S|$. This contradicts the minimality of $S$. Therefore, for every variable $x_j$, $S$ contains fully one of the sets $B_{+}(x_j)$, $B_{-}(x_j)$ and is disjoint from the other. We obtain a valuation $F$ of $\phi$ by including in $F$, for every variable $x_j$, the literal ${\mathrm{\ell }}_j\in \{x_j,\neg x_j\}$ such that $B({\mathrm{\ell }}_j)\subseteq S$. We aim to show that $F$ satisfies at least $m^{\prime \prime }$ clauses of $\phi$.

Note that $|S\cap B|=\gamma n$ and $|A|=(2^k-1)m$ and so $|A\setminus S|⩾m^{\prime \prime }$. Moreover, $|A(C_i)\setminus S|⩽1$ for each clause $C_i$ of $\phi$; otherwise, we would have $a_i(s_1,\mathrm{\dots },s_k),a_i(s_1^{\prime },\mathrm{\dots },s_k^{\prime })\in A(C_i)\setminus S$, where $s_j^{\prime }=\neg s_j$ for some $j\in [k]$. But then $a_i(s_1,\mathrm{\dots },s_k)$ is connected to the vertices of $B(s_j)$ and $a_i(s_1^{\prime },\mathrm{\dots },s_k^{\prime })$ is connected to the vertices of $B(s_j^{\prime })$, and by the minimality of $S$, either of the sets $B(s_j)$, $B(s_j^{\prime })$ is disjoint from $S$; a contradiction with the assumption that $S$ is a vertex cover. Therefore, there exist at least $m^{\prime \prime }$ clauses $C_i$ of $\phi$ such that $|A(C_i)\setminus S|=1$. Observe that each such clause $C_i$ is satisfied by $F$. Indeed, suppose $C_i={\mathrm{\ell }}_1\vee \mathrm{\dots }\vee {\mathrm{\ell }}_k$ and let $a_i(s_1,\mathrm{\dots },s_k)$ be the only element of $A(C_i)\setminus S$. Then $s_j\in \{{\mathrm{\ell }}_j,\neg {\mathrm{\ell }}_j\}$ for each $j\in [k]$ and $(s_1,\mathrm{\dots },s_k)\ne (\neg {\mathrm{\ell }}_1,\mathrm{\dots },\neg {\mathrm{\ell }}_k)$ by the construction of $G(\phi ,p)$, and $B(s_1)\cup \mathrm{\dots }\cup B(s_k)\subseteq S$ by the fact that $S$ is a vertex cover. Thus $s_1,\mathrm{\dots },s_k\in F$ by the construction of $F$ and so $F$ satisfies $\phi$ (i.e., there is a literal $s_j\in \{s_1,\mathrm{\dots },s_k\}$ such that $s_j={\mathrm{\ell }}_j$). $◀$

Overall, we obtain the following reduction from Satisfiability to Vertex Cover that we record here for future reference:

As an immediate corollary, we get that:

Apply Lemma 6 to the graph $G(\phi ,p)$ with vertex set $A\cup B_{+}\cup B_{-}$ and the parameter $\mathrm{\ell }=|A\cup B_{+}|=(2^k-1)m+2^{k-1}pn$ (the choice of $\mathrm{\ell }$ comes from the fact that $A\cup B_{+}$ is a vertex cover of $G(\phi ,p)$). The value of $\text{td}(H(\phi ,p))$ follows from Lemmas 6 and 10. $◀$

We are now almost ready to show the approximation hardness of Treedepth (Theorem 1). We start from the following approximation hardness of the maximization variant of 2-SAT:

Consider the family of $2$-CNF formulas where each variable appears $3$ or $4$ times. In this family, every $n$-variable, $m$-clause formula satisfies $2m⩾3n$, or equivalently $n⩽\frac{2}{3}m$. By Corollary 12, every such formula $\phi$ can be translated – in polynomial time – to a graph $H(\phi )$ with the property that if $m^{\prime }$ is the maximum number of clauses satisfiable in $\phi$, then $\text{td}(H(\phi ))=6m-m^{\prime }+8n+1$.

Now let be fixed. Then there is some $\epsilon >0$ such that, for large enough $m$ and $n⩽\frac{2}{3}m$,

So, letting $k=6m-(1-\epsilon )m+8n$, distinguishing between formulas $\phi$ where at least $(1-\epsilon )m$ clauses are satisfiable and formulas where at most $\left(\frac{251}{252}+\epsilon \right)m$ clauses are satisfiable reduces to distinguishing between graphs of treedepth at most $k$ and those of treedepth at least $(1+\delta )k$. Hence, we obtain hardness by Theorem 13. $◀$

We move to the hardness results under the Exponential Time Hypothesis (ETH); both presented proofs invoke the Sparsification Lemma of Impagliazzo, Paturi, and Zane [15]. We use this lemma in the following form:

The Sparsification Lemma, when combined with ETH and Corollary 12, yields a straightforward proof of Theorem 2:

Lemma 14 together with ETH implies that, for some absolute constants ${\epsilon }^{\prime },B>0$, no algorithm solves $3$-CNF instances of the satisfiability problem on $n^{\prime }$ variables, with each variable appearing at most $B$ times, in time $O(2^{{\epsilon }^{\prime }{n}^{\prime }})$. Given such an instance $\phi$ with $n^{\prime }$ variables and $m^{\prime }$ clauses, we use Corollary 12 with $k=3$, $p=\lfloor \frac{B}{2}\rfloor$ to transform it, in polynomial time, into a graph $H(\phi )$ with $|V(H(\phi ))|⩽c\cdot n^{\prime }$ for some fixed constant $c$ (where $n^{\prime }$ is sufficiently large). Then $\phi$ is satisfiable if and only if $\text{td}(H(\phi ))=(2^{k+1}-3)m^{\prime }+2^{k}p{n}^{\prime }+1$. Therefore, under ETH, the treedepth of an $n$-vertex graph cannot be computed in time $O(2^{\epsilon n})$ where $\epsilon ≔{\epsilon }^{\prime }/(2c)$. $◀$

The approximation time complexity lower bound (Theorem 3) requires a bit more work:

Assuming ETH, there is some $\lambda >0$ such that $n^{\prime }$-variable $3$-SAT cannot be solved in time $O(2^{\lambda n^{\prime }})$. Pick and invoke the Sparsification Lemma (Lemma 14). Let the $3$-CNF formulas $\phi$ and ${\phi }_1,\mathrm{\dots },{\phi }_s$ be as in the statement of the lemma. Combining the Sparsification Lemma with a polynomial-time Satisfiability inapproximability framework of Håstad [13] and a quasi-linear-size construction of polynomially-checkable proofs (PCP) by Bafna, Minzer, Vyas, and Yun [1], we find absolute constants and $B^{\star },c>0$ such that we can translate each formula ${\phi }_i$ in polynomial time to a $3$-CNF formula ${\phi }_i^{\star }$ with $n^{\star }⩽n^{\prime }{\log }^c{n}^{\prime }$ variables, each appearing at most $B^{\star }$ times, with the following property: If ${\phi }_i^{\star }$ has $m^{\star }$ clauses, then:

• $\mathrm{■}$

  If ${\phi }_i$ is satisfiable, then at least ${\alpha }_2{m}^{\star }$ clauses of ${\phi }_i^{\star }$ can be satisfied.

• $\mathrm{■}$

  If ${\phi }_i$ is not satisfiable, then at most ${\alpha }_1{m}^{\star }$ clauses of ${\phi }_i^{\star }$ can be satisfied.

(This reduction is standard; see [5, Lemma 2] for the proof of an analogous result under the assumption of the existence of a linear-size PCP construction.) Chaining this result with Corollary 12, we find absolute constants and a polynomial-time algorithm that transforms each ${\phi }_i^{\star }$ into a graph $H_i$ with at most $d{n}^{\star }$ vertices, where $d$ is a fixed constant, such that:

• $\mathrm{■}$

  If ${\phi }_i$ is satisfiable, then $\text{td}(H_i)⩽{\beta }_1|V(H_i)|$.

• $\mathrm{■}$

  If ${\phi }_i$ is not satisfiable, then $\text{td}(H_i)>{\beta }_2|V(H_i)|$.

Now, let $\epsilon ≔{\epsilon }^{\prime }/d$ and $\delta ={\beta }_2/{\beta }_1-1$. Then, supposing that a $O(2^{\epsilon n/{\log }^{c}n})$-time $(1+\delta )$-approximation algorithm for treedepth existed, the satisfiability of $\phi$ could be decided in time

thus refuting the ETH. $◀$