A Randomized Rounding Approach for DAG Edge Deletion

In 2012, Svensson [17] gave lower bounds for DAG Vertex Deletion. In particular, he showed that for any constant $k$, it is hard to approximate DVD($k$) with a ratio better than $k$ assuming the UGC. A $k$-approximation for this problem is easy to obtain, so the approximability of DVD($k$) is completely understood (assuming the UGC) for all constants $k$. When $k$ may depend on $n$, however, the problem is still not fully understood, even under the UGC, as the lower bound no longer holds. The vertex deletion version has also been studied on undirected graphs for small $k$ [3, 18]. As for NP-Hardness, there is an approximation preserving reduction from Vertex Cover to DVD(2) and to DED(4), so DVD($k$) is NP-Hard to approximate better than $\sqrt{2}$ for $k\ge 2$, as is DED($k$) for $k\ge 4$. NP-Hardness of $\sqrt{2}$ for Vertex Cover was shown by Khot, Minzer, and Safra [11] in 2017, improving upon the classical result of Dinur [8].

Notice that the NP-Hardness result works for any $k\ge 2$ for DVD($k$) and any $k\ge 4$ for DED($k$), where $k$ may depend on $n$, as given hardness for parameter $c$, one can add paths of length $k-c$ with infinite weight vertices or edges to every vertex. This reduction works for the UGC-Hardness results as well, meaning that for any constant $k$ and any $k^{\prime }\ge k$ (where $k^{\prime }$ may depend on $n$), DED($k^{\prime }$) is still UGC-Hard to approximate better than $\lfloor \frac{k}{2}\rfloor$ (or $k$ for DVD($k^{\prime }$)). In other words, both problems do not become easier as $k$ grows.

As noted in [9], DED($k$) is related to the well-studied Maximum Acyclic Subgraph Problem (MAS). Here we are given a directed graph (which is not a DAG) and asked to find an acyclic subgraph with as many edges as possible. Note that the maximization version of DED($k$), Max $k$-Ordering, is a generalization of MAS, recovering this problem when $k$ is set to $n$. Guruswami, Manokaran, and Raghavendra showed that MAS is UGC-Hard to approximate better than $2-ϵ$ for any $ϵ>0$ [7], and Kenkre et al. [9] note that this implies UGC-Hardness of $2-o_k(1)$ for Max $k$-Ordering. Also related is the Restricted Maximum Acyclic Subgraph (RMAS) problem, where each vertex has a finite set of possible integer labels, and the goal is to pick a valid labeling that maximizes the number of edges going from a smaller to a larger label in the assignment. This problem was introduced by Khandekar, Kimbrel, Makarychev, and Sviridenko [10] and its approximability was studied by Grandoni, Kociumaka, and Włodarczyk [6], who gave a $2\sqrt{2}$-approximation. RMAS clearly generalizes MAS. To the best our knowledge, a minimization version of RMAS on DAGs has not been studied.

A more general setting is the $k$-hypergraph vertex cover problem for which a simple rounding gives a $k$-approximation. For the setting where the underlying hypergraph is also $k$-partite, a theorem of Lovász (see [1]) gives a $0.5k$-approximation.

DED($k$) can easily be stated as a constraint satisfaction problem. In particular, one can create a variable $x_v$ for each vertex $v\in V$ and allow $x_v\in \{1,2,\mathrm{\dots },k\}$. Then, we have a set of constraints given by the edges: for each $e=(u,v)$ we create a constraint that . Max $k$-Ordering is then the problem of maximizing the number of satisfied constraints, and DED($k$) is the problem of minimizing the number of unsatisfied constraints. So, both problems fall under the purview of Raghavendra’s UGC-optimal algorithm for CSPs [16] whenever $k$ is an absolute constant. However, the approximation ratio of this algorithm for constant $k$ is not known, and the runtime of the rounding step depends exponentially on $k$. (In addition, for DED($k$), the objective function is negative, and there is an additive error in Raghavendra’s algorithm which could produce issues for this approach.) So, while this is an important view on the problem, it does not give satisfactory guarantees as $k\to \mathrm{\infty }$ or when $k$ depends on $n$.

In Section 2, we show our improved approximation algorithm. Our approach is to assign labels $\mathrm{\ell }(v)\in [0,1]$ to each vertex $v$ independently and cut edges $e=(u,v)$ for which $\mathrm{\ell }(v)-\mathrm{\ell }(u)$ is small compared to $x_e$. By choosing an appropriate definition of small, the feasibility of the LP solution then implies cutting these edges results in a feasible solution to DED($k$). We first show that drawing labels $\mathrm{\ell }(v)\sim \text{Uniform}(0,1)$ results in a $(2-\sqrt{2})(k+1)\approx 0.585(k+1)$-approximation, and then show a modified distribution that results in an algorithm with ratio slightly below $0.549(k+1)$.

In Section 3, we show that no independent labeling distribution can improve the approximation ratio of our algorithm to below $0.542(k+1)$, at least within our analysis framework, which bounds the probability each edge is cut by $\alpha x_e$ to obtain an approximation ratio of $\alpha$.

Finally, in Section 4, we give our two additional results showing $0.5(k+1)$-approximation algorithms for bipartite DAGs and instances with structured LP solutions.

Our algorithm is as follows, and depends on a label distribution $\mu :{[0,1]}^V\to {ℝ}_{\ge 0}$ over label sets $\mathrm{\ell }\in {[0,1]}^V$. We will use $\mathrm{\ell }(v)$ to denote the label of vertex $v$.

First we solve (1) to obtain an optimal solution $x$. Then we draw a label set $\mathrm{\ell }$ according to $\mu$, and delete all edges $e=(u,v)$ with $\mathrm{\ell }(v)-\mathrm{\ell }(u)\le (k+1)x_e-1$.

We will focus on upper and lower bounds for distributions in which the label of every vertex is drawn independently from the same fixed distribution over $[0,1]$. However, in Section 4 we will use a distribution that is not independent. Before analyzing the performance of two label distributions, we show now that it results in a feasible solution.

Here we consider the most natural label distribution: for every vertex, we simply assign it a label uniformly at random from the interval $[0,1]$, independent of all other vertices. First we show the following lemma:

While using the uniform distribution is a natural candidate, it is (perhaps somewhat surprisingly) not optimal. If we wanted to obtain an $0.5(k+1)$ approximation using our framework, it is not difficult to see that the CDF of $\mathrm{\ell }(v)-\mathrm{\ell }(u)$ must be equal to $\text{Uniform}(-1,1)$ for all $u,v$ with an edge between them with $x_e>0$. If this were obtainable, we would have:

for all values of $x_e\in [0,\frac{2}{k+1}]$. (Edges of value greater than $\frac{2}{k+1}$ are cut with probability 1 for any label distribution.)

So, in some sense, our goal is to design an independent distribution over labels so that the CDF of $\mathbf{\ell }\mathbf{(}v\mathbf{)}\mathbf{-}\mathbf{\ell }\mathbf{(}u\mathbf{)}$ is “closer” to $\text{Uniform}\mathbf{(}\mathbf{-}\mathrm{𝟏}\mathbf{,}\mathrm{𝟏}\mathbf{)}$. Using numerical verification and exhaustive search, we arrived at the probability distribution $𝒟$ over $[0,1]$ with density $p(x)=\frac{2}{3}+\frac{23}{3}{(1-2x)}^{22}$. If $X,Y$ are sampled independently from $𝒟$, we obtain a CDF for which $X-Y$ is closer to $\text{Uniform}(-1,1)$ in the relevant respect. We show that using this distribution yields a better approximation ratio than uniform labels. Due to the complexity of the resulting expressions, we use numerical verification. Figure 1 shows the comparison of the densities of $𝒟$ and $\text{Uniform}(-1,1)$.

Here we show that for any bipartite DAG there exists a distribution over labels so that the randomized algorithm from above achieves an approximation ratio of $0.5(k+1)$. Notably, the instances from Kenkre et al. used to obtain UGC hardness of $\lfloor 0.5k\rfloor$ are bipartite, so this is tight up to constants assuming the UGC.

Here we show that an independent distribution over labels exists when we have a structured LP solution. It implies, for example, that if our LP solution has the property that $x_e\in \{0,c\}$ for all $e\in E$ for some fixed value $c$, we can obtain a $0.5(k+1)$-approximation, but is slightly more general (for example, we can obtain the same ratio if all edges have value at least $\frac{1.5}{k+1}$).