On Deleting Vertices to Reduce Density in Graphs and Supermodular Functions

Chandrasekaran, Karthekeyan; Chekuri, Chandra; Kulkarni, Shubhang

doi:10.4230/LIPIcs.ICALP.2025.43

On Deleting Vertices to Reduce Density in Graphs and Supermodular Functions

Karthekeyan Chandrasekaran

Grainger College of Engineering, University of Illinois, Urbana-Champaign, IL, USA Chandra Chekuri Grainger College of Engineering, University of Illinois, Urbana-Champaign, IL, USA Shubhang Kulkarni

Grainger College of Engineering, University of Illinois, Urbana-Champaign, IL, USA

Abstract

We consider deletion problems in graphs and supermodular functions where the goal is to reduce density. In Graph Density Deletion (GraphDD), we are given a graph $G=(V,E)$ with non-negative vertex costs and a non-negative parameter $\rho\geq 0$ and the goal is to remove a minimum cost subset $S$ of vertices such that the densest subgraph in $G-S$ has density at most $\rho$ . This problem has an underlying matroidal structure and generalizes several classical problems such as vertex cover, feedback vertex set, and pseudoforest deletion set for appropriately chosen $\rho\leq 1$ and all of these classical problems admit a $2$ -approximation. In sharp contrast, we prove that for every fixed integer $\rho>1$ , GraphDD is hard to approximate to within a logarithmic factor via a reduction from SetCover, thus showing a phase transition phenomenon. Next, we investigate a generalization of GraphDD to monotone supermodular functions, termed Supermodular Density Deletion (SupmodDD). In SupmodDD, we are given a monotone supermodular function $f\mathrel{\mathop{\ordinarycolon}}2^{V}\rightarrow\mathbb{Z}_{\geq 0}$ via an evaluation oracle with element costs and a non-negative integer $\rho\geq 0$ and the goal is remove a minimum cost subset $S\subseteq V$ such that the densest subset according to $f$ in $V-S$ has density at most $\rho$ . We show that SupmodDD is approximation equivalent to the well-known Submodular Cover problem; this implies a tight logarithmic approximation and hardness for SupmodDD; it also implies a logarithmic approximation for GraphDD, thus matching our inapproximability bound. Motivated by these hardness results, we design bicriteria approximation algorithms for both GraphDD and SupmodDD.

Keywords and phrases:

Combinatorial Optimization, Approximation Algorithms, Randomized Algorithms, Hardness of Approximation, Densest Subgraph, Supermodular Functions, Submodular Set Cover

Category:

Track A: Algorithms, Complexity and Games

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Graph algorithms analysis ; Theory of computation

\rightarrow

Approximation algorithms analysis

Related Version:

Full version of this work is available at: https://arxiv.org/abs/2503.08828 [6]

Acknowledgements:

Shubhang Kulkarni thanks Kishen Gowda for engaging in preliminary discussions about approximations for feedback vertex set and pseudoforest deletion set. We thank anonymous reviewers for pointing out an error, and for suggesting improvements to a previous version of this work.

Funding:

This work was supported in part by NSF grant CCF-2402667.

DOI:

10.4230/LIPIcs.ICALP.2025.43

Event:

52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Editors:

Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The densest subgraph problem in graphs (DSG) is a core primitive in graph and network mining applications. In DSG, we are given a graph $G=(V,E)$ and the goal is to find $\lambda_{G}^{*}\mathrel{\mathop{\ordinarycolon}}=\max_{S\subseteq V}|E(S)|/|S|$ , where $E(S)$ is the set of edges with both end vertices in $S$ . DSG is not only interesting for its applications but is a fundamental problem in algorithms and combinatorial optimization with several connections to graph theory, matroids, and submodularity. Many recent works have explored various aspects of DSG and related problems from both theoretical and practical perspectives [23, 4, 28, 30, 9, 20, 12, 13, 8, 26]. A useful feature of DSG is its polynomial-time solvability. This was first seen via a reduction to network flow [19, 27] but another way to see it is by considering a more general problem, namely the densest supermodular subset problem (DSS): Given a supermodular function $f\mathrel{\mathop{\ordinarycolon}}2^{V}\rightarrow\mathbb{R}_{\geq 0}$ via evaluation oracle, the goal is to find $\lambda^{*}_{f}\mathrel{\mathop{\ordinarycolon}}=\max_{S\subseteq V}{f(S)}/{|S|}$ . One can easily see that DSG is a special case of DSS by noting that for any graph $G$ , the function $f\mathrel{\mathop{\ordinarycolon}}2^{V}\rightarrow\mathbb{Z}$ defined by $f(S)=|E(S)|$ for every $S\subseteq V$ is a supermodular function. It is well-known and easy to see that DSS and DSG can be solved in polynomial-time by a simple reduction to submodular function minimization. Several other problems that are studied in graph and network mining can be seen as special cases of DSS. Recent work has demonstrated the utility of the supermodularity lens in understanding greedy heuristics and approximation algorithms for DSG and these problems [9, 30, 20, 21].

Density Deletion Problems.

In this work we consider several interrelated vertex deletion problems that aim to reduce the density. We start with the graph density deletion problem.

Definition 1 ( $\rho\text{-}\textsc{GraphDD}$ ).

For a fixed constant $\rho$ , the $\rho$ -graph density deletion problem, denoted $\rho\text{-}\textsc{GraphDD}$ , is defined as follows:

Input:	Graph $G=(V,E)$ and vertex costs $c\mathrel{\mathop{\ordinarycolon}}V\rightarrow\mathbb{R}_{\geq 0}$
Goal:	$\arg\min\{\sum_{u\in S}c_{S}\mathrel{\mathop{\ordinarycolon}}S\subseteq V\text% { and }\lambda^{*}_{G-S}\leq\rho\}$ .

This deletion problem naturally generalizes to supermodular functions as defined below. We recall that a set function $f\mathrel{\mathop{\ordinarycolon}}2^{V}\rightarrow\mathbb{R}$ is (i) submodular if $f(A)+f(B)\geq f(A\cap B)+f(A\cup B)$ for every $A,B\subseteq V$ , (ii) supermodular if $-f$ is submodular, (iii) non-decreasing if $f(A)\leq f(B)$ for every $A\subseteq B\subseteq V$ , and (iv) normalized if $f(\emptyset)=0$ . We observe that non-negative normalized supermodular functions are non-decreasing. For a function $f\mathrel{\mathop{\ordinarycolon}}2^{V}\rightarrow\mathbb{R}$ and $S\subseteq V$ , we define $f_{V-S}$ as the function $f$ restricted to the ground set $V-S$ . The evaluation oracle for the function takes a subset $S\subseteq V$ as input and returns the function value of the set $S$ .

Definition 2 ( $\rho\text{-}\textsc{SupmodDD}$ ).

For a fixed constant $\rho$ , the $\rho$ -supermodular density deletion problem, denoted $\rho\text{-}\textsc{SupmodDD}$ , is defined as follows:

Input:	Integer-valued normalized supermodular function $f\mathrel{\mathop{\ordinarycolon}}2^{V}\rightarrow\mathbb{Z}_{\geq 0}$ via an
	evaluation oracle and element costs $c\mathrel{\mathop{\ordinarycolon}}V\rightarrow\mathbb{R}_{\geq 0}$
Goal:	$\arg\min\{\sum_{u\in S}c_{u}\mathrel{\mathop{\ordinarycolon}}S\subseteq V\text% { and }\lambda^{*}_{f_{V-S}}\leq\rho\}$ .

When the density threshold $\rho$ is part of input, we use GraphDD and SupmodDD to refer to these problems. It is easy to see that GraphDD (and hence SupmodDD) is NP-Hard from a general result on vertex deletion problems [25]. Our goal is to understand the approximability of these problems.

Motivations and Connections.

While the deletion problems are natural in their formulation, to the best of our knowledge, GraphDD has only recently been explicitly defined and explored. Bazgan, Nichterlein and Vazquez Alferez [2] defined and studied this problem from an FPT perspective. As pointed out in their work, given the importance of DSG and DSS in various applications to detect communities and sub-groups of interest, it is useful to consider the robustness (or sensitivity) of the densest subgraph to the removal of vertices. In this context, we mention the classical work of Cunningham on the attack problem [11] which can be seen as the problem of deleting edges to reduce density; this edge deletion problem can be solved in polynomial time for integer parameters $\rho$ via matroidal and network flow techniques. In addition to their naturalness and the recent work, we are motivated to consider GraphDD and SupmodDD owing to their connections to several classical vertex deletion problems as well as a matroidal structure underlying GraphDD that we articulate next.

We observe that $0\text{-}\textsc{GraphDD}$ is equivalent to the vertex cover problem: requiring density of $0$ after deleting $S$ is equivalent to $S$ being a vertex cover of $G$ . One can also see, in a similar fashion, that $1\text{-}\textsc{GraphDD}$ is equivalent to the pseudoforest deletion set problem, denoted PFDS– where the goal is to delete vertices so that every connected component in the remaining graph has at most one cycle, and $(1-1/|V|)\text{-}\textsc{GraphDD}$ is equivalent to the feedback vertex set problem, denoted FVS– where the goal is to delete vertices so that the remaining graph is acyclic (see [5] for formal definitions of both problems). Vertex cover, PFDS, and FVS admit $2$ -approximations, and moreover this bound cannot be improved under the Unique Games Conjecture (UGC) [22]. We note that while $2$ -approximations for vertex cover are relatively easy, $2$ -approximations for FVS and PFDS are non-obvious [1, 3, 10]. Until very recently there was no polynomial-time solvable linear program (LP) that yielded a $2$ -approximation for FVS and PFDS. In fact, the new and recent LP formulations [5] for FVS and PFDS are obtained via connections to Charikar’s LP-relaxation for DSG [7]. Fujito [18] unified the $2$ -approximations for vertex cover, FVS, and PFDS via primal-dual algorithms by considering a more general class of matroidal vertex deletion problem on graphs that is relevant to our work. This abstract problem, denoted MatroidFVS ¹¹1We use the feedback vertex set terminology in our naming of the MatroidFVS problem since the goal is to pick a min-cost subset of vertices to cover all circuits of the matroid defined on the edges of a graph. This generalizes FVS which is MatroidFVS where the matroid of interest is the graphic matroid on the input graph., is defined below.

Definition 3 (MatroidFVS).

The Matroid Feedback Vertex Set problem, denoted MatroidFVS, is defined as follows:

Input:	Graph $G=(V,E)$ , vertex costs $c\mathrel{\mathop{\ordinarycolon}}V\rightarrow\mathbb{R}_{\geq 0}$ , and
	Matroid ${\mathcal{M}}=(E,{\mathcal{I}})$ with ${\mathcal{I}}$ being the collection of independent sets
	(via an independence testing oracle)
Goal:	$\arg\min\{\sum_{u\in S}c_{u}\mathrel{\mathop{\ordinarycolon}}S\subseteq V\text% { and }E[V-S]\in{\mathcal{I}}\}$ .

Fujito [18] obtained a $2$ -approximation for MatroidFVS for the class of “uniformly sparse” matroids [24]. It is not difficult to show that vertex cover, FVS, and PFDS can be cast as special cases of MatroidFVS where the associated matroids are “uniformly sparse”. Consequently, Fujito’s result unifies the $2$ -approximations for these three fundamental problems.

We now observe some non-trivial connections between $\rho$ -GraphDD, MatroidFVS and $\rho\text{-}\textsc{SupmodDD}$ . We can show that $\rho$ -GraphDD is a special case of MatroidFVS for every integer $\rho$ : indeed, $\rho$ -GraphDD corresponds to MatroidFVS where the matroid ${\mathcal{M}}_{\rho}$ is the $\rho$ -fold union of the $1$ -cycle matroid defined on the edge set of the input graph. Although it is not obvious, we can show that MatroidFVS is a special case of $1\text{-}\textsc{SupmodDD}$ . We refer the reader to Appendix A of the full version [6] of this work for details regarding these connections, and the problems in the right column in Figure 1(b) for a pictorial representation of the reductions discussed so far. Given these connections and the existence of a $2$ -approximation for vertex cover, FVS, and PFDS, we are led to the following questions.

Question 1.

What is the approximability of $\rho$ -GraphDD, MatroidFVS, and $\rho$ -SupmodDD? Do these admit constant factor approximations?

1.1 Results

In this section, we give an overview of our technical results that resolve Question 1 up to a constant factor gap.

1.1.1 Connections between SubmodCover and SupmodDD

We obtain a logarithmic approximation for $\rho\text{-}\textsc{GraphDD}$ , MatroidFVS, and $\rho\text{-}\textsc{SupmodDD}$ via a reduction to the submodular cover problem and using the Greedy algorithm for it due to Wolsey [31]. First, we recall the submodular cover problem.

Definition 4 (SubmodCover).

The submodular cover problem, denoted SubmodCover, is defined as follows:

Input:	Integer-valued normalized non-decreasing submodular function $h\mathrel{\mathop{\ordinarycolon}}2^{V}\rightarrow\mathbb{Z}_{\geq 0}$
	via evaluation oracle and element costs $c\mathrel{\mathop{\ordinarycolon}}V\rightarrow\mathbb{R}_{\geq 0}$
Goal:	$\arg\min\{\sum_{e\in F}c_{e}\mathrel{\mathop{\ordinarycolon}}F\subseteq V\text% { and }h(F)\geq h(V)\}$ .

For a function $f\mathrel{\mathop{\ordinarycolon}}2^{V}\rightarrow\mathbb{R}$ , we define the marginal $f(v|S)\mathrel{\mathop{\ordinarycolon}}=f(S+v)-f(S)$ for every $v\in V$ and $S\subseteq V$ . We show the following result.

Theorem 5.

Let $f\mathrel{\mathop{\ordinarycolon}}2^{V}\rightarrow\mathbb{Z}_{\geq 0}$ be an integer-valued normalized supermodular function and $\rho$ be a rational number. Then, there exists a normalized non-decreasing submodular function $h\mathrel{\mathop{\ordinarycolon}}2^{V}\rightarrow\mathbb{R}_{\geq 0}$ such that for $F\subseteq V$ , we have that $\lambda^{*}_{f|_{V-F}}\leq\rho$ if and only if $h(F)\geq h(V)$ . Moreover,

1.

if $\rho$ is an integer, then $h$ is integer-valued,
2.

$h(v)\leq\max\{0,f(v|V-v)-\rho\}$ for all $v\in V$ , and
3.

evaluation queries for the function $h$ can be answered in polynomial time by making polynomial number of evaluation queries to the function $f$ .

We discuss the consequences of Theorem 5 for $\rho\text{-}\textsc{SupmodDD}$ . We recall that SubmodCover admits a $(1+\ln{(\max_{v}h(v))})$ -approximation for input function $h$ via the Greedy algorithm of Wolsey [31]. Consider $\rho\text{-}\textsc{SupmodDD}$ for integer-valued $\rho$ . By Theorem 5, we have a reduction to SubmodCover and consequently, we have a $(1+\ln(\max_{v\in V}f(v|V-v)))$ -approximation. In particular, we note that $\rho\text{-}\textsc{GraphDD}$ for integer-valued $\rho$ and MatroidFVS admit $O(\log{n})$ -approximation, where $n$ is the number of vertices in the input graph.

Corollary 6.

$\rho\text{-}\textsc{SupmodDD}$ for integer-valued $\rho$ admits an $(1+\ln{(\max_{v\in V}f(v|V-v))})$ -approximation, where $f\mathrel{\mathop{\ordinarycolon}}V\rightarrow\mathbb{Z}_{\geq 0}$ is the input integer-valued, normalized supermodular function. Consequently, $\rho\text{-}\textsc{GraphDD}$ for integer valued $\rho$ and MatroidFVS admit $O(\log{n})$ -approximations, where $n$ is the number of vertices in the input graph.

$\blacktriangleright$ Remark 7.

The reduction from SupmodDD to SubmodCover is in some sense implicit in prior literature (see [29, 18] for certain special cases of supermodular functions). We note that the reduction from FVS to SubmodCover which follows from this connection does not seem to be well-known in the literature, and the authors of this paper were not aware of it until recently.

From a structural point of view we also prove that SubmodCover reduces to $1\text{-}\textsc{SupmodDD}$ , thus essentially showing the equivalence of SubmodCover and SupmodDD. We believe that it is useful to have this equivalence explicitly known given that vertex deletion problems arise naturally but seem different from covering problems on first glance.

Theorem 8.

Let $h\mathrel{\mathop{\ordinarycolon}}2^{V}\rightarrow\mathbb{Z}_{\geq 0}$ be an integer-valued normalized non-decreasing submodular function. Then, there exists a normalized supermodular function $f\mathrel{\mathop{\ordinarycolon}}2^{V}\rightarrow\mathbb{Z}_{\geq 0}$ such that for $F\subseteq V$ , we have that $h(F)\geq h(V)$ if and only if $\lambda^{*}_{f|_{V-F}}\leq 1$ . Moreover,

1.

$f(v|V-v)=h(v)+1$ for all $v\in V$ , and
2.

evaluation queries for the function $f$ can be answered in polynomial time by making a constant number of evaluation queries to the function $h$ .

1.1.2 Hardness of Approximation

A starting point for our attempt to answer Question 1 was our belief that $\rho$ -GraphDD for integer $\rho$ admits a $(\rho+1)$ -approximation via the primal-dual approach suggested by Fujito for MatroidFVS [18]. This belief stems from Fujito’s work which showed a $2$ -approximation for vertex cover, FVS, PFDS, and MatroidFVS for “uniformly sparse” matroids and our reduction showing that $\rho$ -GraphDD for integral $\rho$ is a special case of MatroidFVS (see Appendix A of the full version of this work [6]). We note that the matroid that arises in the reduction is not a “uniformly sparse” matroid but has lot of similarities with it, so our initial belief was that a more careful analysis would lead to a constant factor approximation. However, to our surprise, after several unsuccessful attempts to prove a constant factor upper bound, we were able to show that for every integer $\rho\geq 2$ , $\rho$ -GraphDD is $\Omega(\log n)$ -hard to approximate via a reduction from Set Cover.

Theorem 9.

For every integer $\rho\geq 2$ , there is no $o(\log n)$ approximation for $\rho\text{-}\textsc{GraphDD}$ assuming $P\neq NP$ , where $n$ is the number of vertices in the input instance.

Thus, $\rho$ -GraphDD exhibits a phase transition: it admits a $2$ -approximation for $\rho\leq 1$ (via Fujito’s results [18]) and becomes $\Omega(\log{n})$ -hard for every integer $\rho\geq 2$ . To conclude our hardness results, we note that since GraphDD is a special case of MatroidFVS, which itself is a special case of SupmodDD, both MatroidFVS and SupmodDD are $\Omega(\log n)$ -inapproximable. However, both these problems are also $O(\log{n})$ -approximable via Corollary 6. Thus, we resolve the approximability of all these problems to within a small constant factor. We refer the reader to Figure 1 for an illustration of problems considered in this work and approximation-factor preserving reductions between them.

Figure 1: Reductions between problems of interest to this work. Arrow from Problem A to Problem B implies that Problem A has an approximation-preserving reduction to Problem B. Figure (a) consists of the connections between problems known prior to our work. Figure (b) showcases our results.

1.1.3 Bicriteria Approximations

The hardness result for $2$ -GraphDD (and $\rho$ -GraphDD) motivates us to consider bicriteria approximation algorithms. Can we obtain constant factor approximation by relaxing the requirement of meeting the density target $\rho$ exactly? We show that this is indeed possible. We consider an orientation based LP that was used recently to obtain a polynomial-time solvable LP to approximate FVS and PFDS [5]. We observed that this LP has an $\Omega(n)$ integrality gap when considering $2$ -GraphDD. Nevertheless, the LP is useful in obtaining the following bicriteria approximation.

Theorem 10.

There exists a polynomial time algorithm which takes as input a graph $G=(V,E)$ , vertex deletion costs $c\mathrel{\mathop{\ordinarycolon}}V\rightarrow\mathbb{R}_{\geq 0}$ , a target density $\rho\in\mathbb{R}$ , and an error parameter $\epsilon\in(0,1/2)$ , and returns a set $S\subseteq V$ such that:

1.

$\lambda^{*}_{G-S}\leq\left(\frac{1}{1-2\epsilon}\right)\cdot\rho$ ,
2.

$\sum_{u\in S}c_{u}\leq\left(\frac{1}{\epsilon}\right)\cdot\mathtt{OPT}$ ,

where OPT denotes the cost of an optimum solution to $\rho\text{-}$ GraphDD on the instance $(G,c)$ .

Next, we consider $\rho$ -SupmodDD. Unlike the case of graphs, it is not clear how to write an integer programming formulation for SupmodDD whose LP-relaxation is polynomial-time solvable. Instead, we take inspiration from the very recent work of [32] on vertex deletion to reduce treewidth. We design a combinatorial randomized algorithm that yields a bicriteria approximation for SupmodDD, where the bicriteria approximation bounds are based on a parameter $c_{f}$ that depends on the input supermodular function $f$ . For a normalized supermodular function $f\mathrel{\mathop{\ordinarycolon}}2^{V}\rightarrow\mathbb{R}_{\geq 0}$ , we define

c_{f}\mathrel{\mathop{\ordinarycolon}}=\max\left\{\frac{\sum_{u\in S}f(u|S-u)}% {f(S)}\mathrel{\mathop{\ordinarycolon}}S\subseteq V\right\}.

This parameter $c_{f}$ was defined in a recent work on DSS to unify the analysis of the greedy peeling algorithm for DSG [9]. We note that $1\leq c_{f}\leq|V|$ and moreover, $c_{f}=1$ if and only if the function $f$ is modular. If $f$ is the induced edge function of a graph (i.e., $f(S)$ is the number of edges with all its end-vertices in $S$ for every subset $S$ of vertices), then $c_{f}\leq 2$ . This follows from the observation that the sum of degrees is at most twice the number of edges in a graph. Similarly, if $f$ is the induced edge function of a hypergraph with rank $r$ (i.e., all hyperedges have size at most $r$ ), then $c_{f}\leq r$ . We show the following bicriteria approximation for SupmodDD.

Theorem 11.

There exists a randomized polynomial time algorithm which takes as input a normalized monotone supermodular function $f\mathrel{\mathop{\ordinarycolon}}2^{V}\rightarrow\mathbb{Z}$ (given by oracle access), element deletion costs $c\mathrel{\mathop{\ordinarycolon}}V\rightarrow\mathbb{R}_{\geq 0}$ , a target density $\rho\in\mathbb{R}$ , and an error parameter $\epsilon\in(0,1)$ , and returns a set $S\subseteq V$ such that:

1.

$\lambda^{*}_{f|_{V-S}}\leq c_{f}(1+\epsilon)\cdot\rho$ , and
2.

$\mathbb{E}\left[\sum_{u\in S}c_{u}\right]\leq c_{f}\left(1+\frac{1}{\epsilon}% \right)\cdot\mathtt{OPT}$ ,

where OPT denotes the cost of an optimum solution to $\rho\text{-}\textsc{SupmodDD}$ on the instance $(f,c)$ .

As a consequence of Theorem 11, we obtain a bicriteria approximation for density deletion problems in graphs and $r$ -rank hypergraphs. We note that the bicriteria guarantee that we get from this theorem for graphs is weaker than the guarantee stated in Theorem 10. We discuss another special case of SupmodDD where the supermodular function of interest has bounded $c_{f}$ to illustrate the significance of Theorem 11. Given a graph $G=(V,E)$ and a parameter $p\geq 1$ , the $p$ -mean density of $G$ is defined as $\max\{\sum_{u\in S}d_{S}(u)^{p}/|S|\mathrel{\mathop{\ordinarycolon}}S\subseteq V\}$ , where $d_{S}(u)$ is the number of edges in $E[S]$ incident to the vertex $u$ . The $p$ -mean density of graphs was introduced and studied by Veldt, Benson, and Kleinberg [30]. Subsequent work by Chekuri, Quanrud, and Torres [9] showed that $p$ -mean density is a special case of the densest supermodular set problem (i.e., DSS) where the supermodular function $f\mathrel{\mathop{\ordinarycolon}}2^{V}\rightarrow\mathbb{R}_{\geq 0}$ of interest is given by $f(S)\mathrel{\mathop{\ordinarycolon}}=\sum_{u\in S}d_{S}(u)^{p}$ for every $S\subseteq V$ and moreover $c_{f}\leq(p+1)^{p}$ . We note that the natural vertex deletion problem is the $p$ -mean density deletion problem: given a graph $G=(V,E)$ with vertex deletion costs, find a min-cost subset of vertices to delete so that the $p$ -mean density of the remaining graph is at most a given threshold. Since $c_{f}\leq(p+1)^{p}$ for the function $f$ of interest here, Theorem 11 implies a bicriteria approximation for $p$ -mean density deletion for integer-valued $p$ . An interesting open question is to obtain better bicriteria approximation for $\rho\text{-}\textsc{SupmodDD}$ – in particular, can we remove the dependence on $c_{f}$ ?

Organization.

In Section 2, we show an approximation-preserving reduction from SetCover to $\rho\text{-}\textsc{GraphDD}$ and prove Theorem 9. In Section 3, we give a bicriteria approximation for $\rho\text{-}\textsc{SupmodDD}$ and prove Theorem 11. Finally, in Section 4 we show the connections between SupmodDD and Submodular Cover by proving Theorems 5 and 8. We defer the proof of Theorem 10 to the full version of this work [6].

2 Hardness of Approximation

In this section, we show Theorem 9, i.e., we show an approximation preserving reduction from SetCover to $\rho\text{-}\textsc{GraphDD}$ . We recall the set cover problem and its inapproximability.

Definition 12 (SetCover).

The set cover problem, denoted SetCover, is defined as follows:

Input:	Finite Universe ${\mathcal{U}}$ , Family ${\mathcal{S}}\subseteq 2^{\mathcal{U}}$ with costs $c\mathrel{\mathop{\ordinarycolon}}{\mathcal{S}}\rightarrow\mathbb{R}_{\geq 0}$
Goal:	$\arg\min\{\sum_{S\in\mathcal{F}}c_{S}\mathrel{\mathop{\ordinarycolon}}\mathcal% {F}\subseteq{\mathcal{S}}\text{ with }\cup_{S\in\mathcal{F}}S={\mathcal{U}}\}$ .

Theorem 13 ([15, 14]).

For every $\epsilon>0$ , there does not exist a $(1-\epsilon)\ln{n}$ -approximation for SetCover assuming P $\neq$ NP, where $n$ is the size of the input instance.

We will also need the following characterization of density via orientations. We recall that an orientation of a graph $G=(V,E)$ assigns each edge $\{u,v\}$ to either $u$ or $v$ . For notational convenience, we use $\vec{G}=(V,\vec{E})$ to denote an orientation of the graph $G$ and $d^{\text{in}}_{\vec{G}}(u)$ to denote the indegree of a vertex $u\in V$ (i.e., the number of edges assigned to $u$ ) in the oriented graph $\vec{G}$ . The following connection between density and orientations will be used in our hardness reduction. This characterization is implied by a result of Hakimi [16] and also by the dual of Charikar’s LP to solve DSG [7].

Proposition 14.

Let $G=(V,E)$ be a graph and let $\rho\in\mathbb{Z}_{\geq 0}$ be an integer value. Then, we have that $\lambda^{*}_{G}\leq\rho$ if and only if there exists an orientation $\vec{G}=(V,\vec{E})$ of the graph $G$ such that $d^{\text{in}}_{\vec{G}}(u)\leq\rho$ for every $u\in V$ .

We now restate and prove Theorem 9.

See 9

Proof.

We show the theorem when the target density $\rho=2$ via a reduction from SetCover. At the end of the proof, we remark on how to modify the reduction to obtain hardness for all integers $\rho\geq 2$ as claimed in the theorem. Let $({\mathcal{S}},{\mathcal{U}},c\mathrel{\mathop{\ordinarycolon}}{\mathcal{S}}% \rightarrow\mathbb{R})$ be a SetCover instance. We will assume (without loss of generality) that all elements in ${\mathcal{U}}$ have the same frequency $f\geq 4$ which is a power of $2$ – we note that this assumption is not a technical requirement and is only for ease of exposition. For this instance, we construct an instance $(G=(V,E),c_{G}\mathrel{\mathop{\ordinarycolon}}V\rightarrow\mathbb{R})$ of $2$ -GraphDD as follows:

1.

Add vertices representing sets: For each set $S\in{\mathcal{S}}$ , add a set-vertex $v_{S}$ to $V$ .
2.

Add binary trees representing elements: For each element $e\in{\mathcal{U}}$ , add a complete binary tree with the $f$ leaves as the set-vertices corresponding to the sets containing $e$ . We denote this tree as ${\mathcal{T}}_{e}$ and its root as $r_{e}$ .
3.

Add self-loops: For each element $e\in{\mathcal{U}}$ , add a self-loop to the root vertex $r_{e}$ of the tree ${\mathcal{T}}_{e}$ . For each set $S\in{\mathcal{S}}$ , add $\rho=2$ self-loops to the vertex $v_{S}$ .
4.

Define cost function: We define the cost function $c_{G}\mathrel{\mathop{\ordinarycolon}}V\rightarrow\mathbb{R}$ as follows: $c_{G}(v_{S})=c(S)$ for all $S\in{\mathcal{S}}$ and $c_{G}(u)=\infty$ for all $u\in V-\{v_{S}\mathrel{\mathop{\ordinarycolon}}S\in{\mathcal{S}}\}$ .

Figure 2: The figure in (a) depicts the subgraph of the construction corresponding to element

e\in{\mathcal{U}}

. Here,

f=8

. The figure in (b) depicts the intermediate orientation

\vec{H}

for the subgraph of

H

corresponding to an element

e\in{\mathcal{U}}

. The greyed-out set-vertex at the bottom represents that this vertex is in

X_{F}

. The figure in (c) depicts the final orientation for the subgraph from the figure in (b) after reorientation. The highlighted edges are those that have been reoriented.

We refer the reader to Figure 2(a) for pictorial depictions of the instance constructed via the reduction above. The next claim shows the correctness of our reduction and also implies that our reduction is approximation-preserving. The approximation hardness guarantee of the theorem when the target density $\rho=2$ then follows by Theorem 13 and the observation that the number of vertices $|V|$ is a constant factor of the size of the input set cover instance.

Claim 15.

The instance $(G,c_{G})$ has a feasible solution to $2$ -GraphDD of finite cost $T$ if and only if $({\mathcal{S}},{\mathcal{U}},c)$ has a SetCover of cost $T$ .

Proof.

We first show the forward direction of the claim. Let $X\subseteq V$ be a feasible solution to $2$ -GraphDD of finite cost $T$ . By construction, we have that $X\subseteq\{v_{S}\mathrel{\mathop{\ordinarycolon}}S\in{\mathcal{S}}\}$ . Let $F\mathrel{\mathop{\ordinarycolon}}=\{S\mathrel{\mathop{\ordinarycolon}}v_{S}% \in X\}$ denote the corresponding sets. By way of contradiction, suppose $F$ is not a set cover. Consequently, there exists an element $e\in{\mathcal{U}}$ not covered by $F$ . For convenience, we use ${\mathcal{S}}(e)\mathrel{\mathop{\ordinarycolon}}=\{S\in{\mathcal{S}}\mathrel{% \mathop{\ordinarycolon}}e\in S\}$ to denote the sets that contain the element $e$ . We note that since the element $e$ is not covered by $F$ , we have that $\{v_{S}\mathrel{\mathop{\ordinarycolon}}S\in{\mathcal{S}}(e)\}\cap X=\emptyset$ . Let $V_{e}$ denote the set of vertices obtained by including all vertices of the binary tree ${\mathcal{T}}_{e}$ . Then, the following gives us a contradiction:

2\geq\lambda_{G-X}^{*}\geq\frac{|E[V_{e}]|}{|V_{e}|}=\frac{(2f+1)+(2f-2)}{2f-1% }>2.

Here, the first inequality is because $X$ is a feasible solution to $2$ -GraphDD. The second inequality is by definition of graph density. The equality is because there are $(2f+1)$ self loop edges, $(2f-2)$ non-self loop edges, and $2f-1$ vertices in the tree ${\mathcal{T}}_{e}$ by construction.

We now show the reverse direction. Let $F\subseteq{\mathcal{S}}$ be a set cover. Let $X_{F}=\{v_{S}\mathrel{\mathop{\ordinarycolon}}S\in F\}$ . Then, we show that the graph $H\mathrel{\mathop{\ordinarycolon}}=G-X_{F}$ has density at most $2$ . By Proposition 14(2), it suffices to exhibit an orientation of the graph $H$ in which the indegree of every vertex is at most $2$ . We first consider the following intermediate orientation of $G$ . For each element $e\in{\mathcal{U}}$ , we do the following: for vertex $u\in{\mathcal{T}}_{e}-\{r_{e}\}$ , we denote $p(u)$ as the (unique) parent of $u$ in the (rooted) tree, and we orient the edge $(u,p(u))$ towards the parent $p(u)$ . All self-loops are assumed to be trivially oriented. Let $\vec{H}\mathrel{\mathop{\ordinarycolon}}=(V_{H},\vec{E}_{H})$ denote this intermediate orientation restricted to the graph $H$ , and ${\mathcal{R}}\mathrel{\mathop{\ordinarycolon}}=\{r_{e}\mathrel{\mathop{% \ordinarycolon}}e\in{\mathcal{U}}\}$ denote the set of all root vertices. Refer to Figure 2(b) for a pictorial depiction of orientation $\vec{H}$ . We now make three important observations regarding the indegrees in the orientation $\vec{H}$ .

Observation 16.

We have the following:

1.

for all $u\in V_{H}-{\mathcal{R}}$ , $d^{\text{in}}_{\vec{H}}(u)\leq 2$ ,
2.

for all $r\in{\mathcal{R}}$ , $d^{\text{in}}_{\vec{H}}(r)=3$ , and
3.

for each element $e\in{\mathcal{U}}$ , there exists a set $S_{e}\in{\mathcal{S}}(e)$ such that $d^{\text{in}}_{\vec{H}}(p(v_{S_{e}}))\leq 1$ .

Proof.

We show each statement separately below.

1.

We note that the statement easily follows by construction for the set vertices $v_{S}$ . Let $e\in{\mathcal{U}}$ be an arbitrary element and let $u\in{\mathcal{T}}_{e}-\left(\left\{v_{S}\mathrel{\mathop{\ordinarycolon}}S\in{% \mathcal{S}}(e)\right\}\cup\left\{r_{e}\right\}\right)$ be a non-root internal vertex of the binary tree. Since $u$ has exactly two child nodes and one parent node in ${\mathcal{T}}_{e}$ , we have that $d^{\text{in}}_{\vec{H}}(u)\leq 2$ . We note that the inequality may be strict if any children of $u$ belong to the set $X_{F}$ .
2.

Let $e\in{\mathcal{U}}$ . We note that $r_{e}$ has exactly $2$ children and $1$ self loop, and consequently $d^{\text{in}}_{\vec{H}}(r_{e})\leq 3$ as claimed. Here, we note that bo child of $r_{e}$ belongs to the set $X_{F}$ because of our simplifying assumption that $f\geq 4$ .
3.

Let $e\in{\mathcal{U}}$ . Since $F$ is a set cover, there exists a set $S\in S(e)$ such that $S\in F$ . Consequently, $v_{S}\in X_{F}$ , and so $d^{\text{in}}_{\vec{H}}(p(v_{S}))\leq 1$ by construction.

$\hfill\blacktriangleleft$ We now use the orientation $\vec{H}$ and Observation 16 to construct the orientation which certifies that the graph $H$ has density at most $2$ . We note that by Observation 16(1) and (2), it suffices to modify the orientation $\vec{H}$ to reduce the indegree of all root vertices in ${\mathcal{R}}$ to $2$ while keeping all other indegrees at most $2$ . Consider an arbitrary element $e\in{\mathcal{U}}$ . Let $u_{e}$ be an arbitrary vertex of ${\mathcal{T}}_{e}$ such that $d^{\text{in}}_{\vec{H}}(u_{e})\leq 1$ . We note that such a vertex exists by Observation 16(3). We consider the unique path $P_{e}$ from $u_{e}$ to $r_{e}$ in ${\mathcal{T}}_{e}$ . We note that by the construction of the orientation $\vec{H}$ , every edge along this path is oriented in the direction of the path. Consider the orientation obtained by reorienting these edges in the reverse direction of the path. Refer to Figure 2(c) for a pictorial depiction of the modified orientation. We note that only the indegrees of $r_{e}$ and $u_{e}$ change due to this reorientation. In particular, for all $e\in{\mathcal{U}}$ , we have that $d^{\text{in}}_{\vec{H}}(u_{e})\leq 2$ and $d^{\text{in}}_{\vec{H}}(r_{e})=2$ . This concludes the proof. $\hfill\vartriangleleft$ The preceding reduction can be modified to show approximation hardness for all integral $\rho\geq 2$ . Suppose that $\rho=2+\alpha$ , where $\alpha\in\mathbb{Z}_{\geq 0}$ . Then, we construct the same graph as above with $\alpha$ additional self-loops on each vertex. The proof generalizes. $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 17.

The addition of self-loops is not technically necessary for the construction; they simply make it more straightforward. Specifically, a vertex $u$ with $\gamma\in\mathbb{Q}_{\geq 1}$ self-loops can be replaced by a subgraph with density exactly $\gamma$ . In this subgraph, one vertex, say $h_{u}$ , is identified with $u$ and its cost is defined as $c(h_{u})\mathrel{\mathop{\ordinarycolon}}=c(u)$ . All other vertices have infinite cost. All edges incident to $u$ are then redirected to connect to $h_{u}$ instead.

3 Bicriteria Approximation for GraphDD

In this section, we describe a randomized combinatorial bicriteria approximation algorithm for $\rho$ -SupmodDD and prove Theorem 11. The algorithm is inspired by the ideas of the recent work of Włodarczyk [32]. Our algorithm is based on the following idea. Suppose that we had non-negative potentials $\pi\mathrel{\mathop{\ordinarycolon}}V\rightarrow\mathbb{R}_{\geq 0}$ for the elements of the ground set such that the potential value $\sum_{u\in X}\pi(u)$ of an optimal solution $X\subseteq V$ is large, say at least $\alpha\cdot\sum_{u\in V}\pi(u)$ . Then, a natural algorithm – at least when the vertex deletion costs are uniform – would be to compute the potentials, sample an element in proportion to the potentials and delete it, define a residual instance, and repeat. This would ensure an $\alpha$ -approximation for the problem in expectation via a martingale argument.

Unfortunately, our hardness result suggests that we are unlikely to obtain good potentials. In fact, the hard instances seem to be the functions that have density very close to the target density. However, we leverage supermodularity to show that if the density of the input function is at least $\beta$ times the target density, then we can indeed find such good vertex potentials. In order to ensure that the density of the input function is at least $\beta$ times the target density, we perform a preprocessing step to prune certain elements from the ground set without changing the cost of an optimal solution. Overall, this gives us an $(\alpha,\beta)$ -bicriteria guarantee, where the values $\alpha$ and $\beta$ are as given in Theorem 11. We also note that the cost function to delete vertices may be arbitrary – we overcome this by using the natural bang-per-buck sampling strategy, i.e. we sample a vertex $u$ in proportion to $\pi(u)/c(u)$ .

The rest of the section is organized as follows. In Section 3.1 we give our preprocessing step based on the dense decomposition of supermodular functions. In Section 3.2 we describe our element potentials based on marginal gains of supermodular functions. In Section 3.3 we present our algorithm and complete the proof of Theorem 11.

3.1 Preprocessing via Dense Decomposition

We discuss the dense decomposition of a normalized non-negative supermodular set function [20, 17] and prove a lemma that will enable us to use it as a preprocessing step.

Definition 18 ([20]).

Let $f\mathrel{\mathop{\ordinarycolon}}2^{V}\rightarrow\mathbb{R}_{+}$ be a non-negative normalized supermodular function. A sequence $(V_{1},\rho_{1}),(V_{2},\rho_{2}),\ldots,(V_{k},\rho_{k})$ is the dense decomposition of $f$ if

1.

$V_{1},\ldots,V_{k}$ is a partition of $V$ obtained iteratively as follows: for $i=1,2,\ldots,k$ , $V_{i}$ is the inclusion-wise maximal set $S\subseteq V-\cup_{j\in[i-1]}V_{j}$ that maximizes

$\frac{f\left(S\cup\bigcup_{j\in[i-1]}V_{j}\right)-f\left(\bigcup_{j\in[i-1]}V_% {j}\right)}{|S|}$
2.

the values $\rho_{1},\ldots,\rho_{k}$ are obtained as

$\rho_{i}\mathrel{\mathop{\ordinarycolon}}=\frac{f\left(\bigcup_{j\in[i]}V_{j}% \right)-f\left(\bigcup_{j\in[i-1]}V_{j}\right)}{|V_{i}|}\ \forall\ i\in[k].$

We note that the dense decomposition can also be viewed algorithmically as the output of a recursive process which computes the unique inclusion-wise maximal set $S$ that maximizes the ratio $f(S)/|S|$ and recurses on the contracted function $f_{/S}\mathrel{\mathop{\ordinarycolon}}2^{V-S}\rightarrow\mathbb{R}$ defined as $f_{/S}(X)\mathrel{\mathop{\ordinarycolon}}=f(S\cup X)$ for all $X\subseteq V-S$ . It can be shown that this decomposition is unique for a supermodular $f$ . The following lemma allows us to use the dense decomposition as an algorithmic preprocessing step in the next section. In particular, the lemma says that the dense decomposition can be used to find a set $R\subseteq V$ such that it suffices to focus on solving the $\rho\text{-}\textsc{SupmodDD}$ problem on the function restriction $f|_{R}$ ; and additionally, the ground set elements of the restricted function have large marginal gains.

Lemma 19.

Let $f\mathrel{\mathop{\ordinarycolon}}2^{V}\rightarrow\mathbb{R}_{\geq 0}$ be a normalized non-negative supermodular function, $c\mathrel{\mathop{\ordinarycolon}}V\rightarrow\mathbb{R}_{+}$ be a cost function, and $\rho\in\mathbb{R}_{+}$ be a positive real value. Moreover, let $(V_{1},\phi_{1}),(V_{2},\phi_{2}),\ldots,(V_{k},\phi_{k})$ be the dense decomposition of $(f,V)$ and for $\rho^{\prime}>\rho$ , let $R\mathrel{\mathop{\ordinarycolon}}=\bigcup_{i\in[k]\mathrel{\mathop{% \ordinarycolon}}\phi_{i}>\rho^{\prime}}V_{i}$ . Then, we have that

1.

every feasible solution to $\rho^{\prime}\text{-}\textsc{SupmodDD}$ for the function $f|_{R}$ is also a feasible solution to $\rho^{\prime}\text{-}\textsc{SupmodDD}$ for the function $f$ ,
2.

$\mathtt{OPT}(f)\geq\mathtt{OPT}(f|_{R})$ , where $\mathtt{OPT}(f)$ and $\mathtt{OPT}(f|_{R})$ denote the costs of optimal solutions to $\rho\text{-}\textsc{SupmodDD}$ for the functions $f$ and $f|_{R}$ respectively,
3.

$f(v|R-v)\geq\rho^{\prime}$ for all $v\in R$ , and
4.

the set $R$ can be computed in polynomial time given access to a function evaluation oracle for $f$ .

Proof.

We show all four properties separately below.

1.

Let $X\subseteq R$ be a feasible solution to $\rho^{\prime}\text{-}\textsc{SupmodDD}$ for the function $f|_{R}$ and by way of contradiction suppose that $X$ is not a feasible solution to $\rho^{\prime}\text{-}\textsc{SupmodDD}$ for the function $f$ . Thus, there exists a set $S\subseteq V-X$ such that $f(S)/|S|>\rho^{\prime}$ . We note that this set $S$ cannot be contained in $R-X$ since otherwise $X$ would not be a feasible solution to $\rho^{\prime}\text{-}\textsc{SupmodDD}$ for $f|_{R}$ . Then, the following gives us the required contradiction:

	$\displaystyle\rho^{\prime}<\frac{f(S)}{\|S\|}$	$\displaystyle\leq\frac{f(S\cup R)-f(R)+f(S\cap R)}{\|S-R\|+\|S\cap R\|}$
		$\displaystyle\leq\max\left\{\frac{f(S\cup R)-f(R)}{\|S-R\|},\frac{f(S\cap R)}{\|S% \cap R\|}\right\}$
		$\displaystyle\leq\max\left\{\max\left\{\frac{f(R\cup S^{\prime})-f(R)}{\|S^{% \prime}\|}\mathrel{\mathop{\ordinarycolon}}S^{\prime}\subseteq V-R\right\},% \lambda_{f\|_{R-X}}^{*})\right\}$
		$\displaystyle\leq\rho^{\prime}.$

Here, the second inequality is by supermodularity of the function $f$ . The third inequality is by the observation that $(a+b)/(c+d)\leq\max\{a/c,b/d\}$ for non-negative numbers $a, b, c, d$ . For the final inequality, observe that $\lambda_{f|_{R-X}}^{*}\leq\rho^{\prime}$ because $X$ is a feasible $\rho^{\prime}\text{-}\textsc{SupmodDD}$ for $f|_{R}$ . Furthermore, we have that $\max\left\{\frac{f(R\cup S^{\prime})-f(R)}{|S^{\prime}|}\mathrel{\mathop{% \ordinarycolon}}S^{\prime}\subseteq V-R\right\}\leq\rho^{\prime}$ by definition of the dense decomposition and $R$ .

2.

Let $X\subseteq V$ be an optimal $\rho\text{-}\textsc{SupmodDD}$ for $f$ w.r.t. cost function $c$ . Then, we note that $X\cap R$ is a feasible $\rho\text{-}\textsc{SupmodDD}$ for $f|_{R}$ . This can be easily observed as follows: by way of contradiction, suppose that $X\cap R$ is not a feasible $\rho\text{-}\textsc{SupmodDD}$ for $f|_{R}$ . Then, there exists a set $S\subseteq R-X$ such that $f|_{R}(S)/|S|>\rho$ . Consequently, we have that $\lambda^{*}_{f|_{V-X}}\geq f(S)/|S|=f|_{R}(S)/|S|>\rho$ , a contradiction to $X$ being a feasible $\rho\text{-}\textsc{SupmodDD}$ for $f$ . Then, $\mathtt{OPT}(f)\geq\mathtt{OPT}(f|_{R})$ follows by non-negativity of $c$ .

3.

By way of contradiction, suppose that there exists a vertex $v\in R$ such that $f(v|R-v)\leq\rho^{\prime}$ . We recall that $R=\bigcup_{i\in[k]\mathrel{\mathop{\ordinarycolon}}\phi_{i}>\rho^{\prime}}V_{i}$ . Let $j\in[k]$ be such that $v\in V_{j}$ . For convenience, we will let $U_{j-1}\mathrel{\mathop{\ordinarycolon}}=\bigcup_{i\in[j-1]}V_{i}$ and $U_{j}=\bigcup_{i\in[j]}V_{i}$ . We note that $U_{j-1}$ and $U_{j}$ are contained in $R$ and $\rho_{j}\mathrel{\mathop{\ordinarycolon}}=\frac{f(U_{j})-f(U_{j-1})}{|V_{j}|}$ by definition of the dense decomposition. Moreover, $\rho_{j}>\rho^{\prime}$ by the definition of the set $R$ , and so by supermodularity we have that $f(v|U_{j}-v)\leq f(v|R-v)\leq\rho^{\prime}<\rho_{j}$ . Then, the following sequence of inequalities gives us the required contradiction.

	$\displaystyle\rho_{j}$	$\displaystyle=\frac{f(U_{j})-f(U_{j-1})}{\|V_{j}\|}$
		$\displaystyle=\frac{f(U_{j})-f(U_{j}-v)+f(U_{j}-v)-f(U_{j-1})}{\|V_{j}\|}$
		$\displaystyle=\frac{f(v\|U_{j}-v)+f(U_{j}-v)-f(U_{j-1})}{1+(\|V_{j}\|-1)}$
		$\displaystyle<\frac{\rho_{j}+f(U_{j}-v)-f(U_{j-1})}{1+(\|V_{j}\|-1)}$
		$\displaystyle\leq\max\left\{\rho_{j},\frac{f(U_{j}-v)-f(U_{j-1})}{\|V_{j}\|-1}\right\}$
		$\displaystyle\leq\max\left\{\rho_{j},\max\left\{\frac{f(U_{j-1}\cup S)-f(U_{j-% 1})}{\|S\|}\mathrel{\mathop{\ordinarycolon}}S\subseteq V-U_{j-1}\right\}\right\}$
		$\displaystyle\leq\rho_{j},$

where the second inequality is by the observation that $(a+b)/(c+d)\leq\max\{a/c,b/d\}$ for non-negative numbers $a, b, c, d$ . Here, we note that $|V_{j}|\geq 2$ since otherwise, $V_{j}=\{v\}$ and so by supermodularity we have that $\rho_{j}=f(U_{j-1}+v)-f(U_{j-1})=f(v|U_{j-1})\leq f(v|R-v)<\rho_{j}$ , a contradiction.

4.

It is well-known that the dense decomposition (and consequently the set $R$ ) can be computed in polynomial time (given access to the function evaluation oracle for $f$ ) via supermodular maximization. This is implicit in Fujishige’s work on principle partitions [17], and is also explicitly considered in more recent works on dense decompositions for supermodular functions [20]. We omit the details of a formal proof here for brevity.

$\hfill\blacktriangleleft$

3.2 Element Potentials via Marginal Gains

We now show that the marginal gains of elements relative to the entire ground set are good potentials for a sampling-based algorithm for $\rho$ -SupmodDD when all the marginal gains of the input function are large enough, in particular, at least $c_{f}(1+\epsilon)\rho$ .

Lemma 20.

Let $\rho\in\mathbb{R}$ and $\epsilon\in(0,1)$ . Let $f\mathrel{\mathop{\ordinarycolon}}2^{V}\rightarrow\mathbb{Z}$ be a normalized monotone supermodular function such that $f(u|V-u)\geq c_{f}(1+\epsilon)\rho$ for all $u\in V$ , and let $X\subseteq V$ be a $\rho\text{-}\textsc{SupmodDD}$ for $f$ . Then, we have that

\sum_{u\in X}f(u|V-u)\geq\frac{1}{c_{f}(1+1/\epsilon)}\sum_{u\in V}f(u|V-u).

Proof.

By supermodularity of $f$ , we have that

	$\displaystyle\sum_{u\in X}f(V-u)$	$\displaystyle\leq(\|X\|-1)f(V)+f(V-X)\text{ and hence, }$
	$\displaystyle\sum_{u\in X}f(u\|V-u)$	$\displaystyle\geq f(V)-f(V-X).$		(1)

By way of contradiction, suppose that the lemma is false. Then, we have the following.

	$\displaystyle\sum_{u\in V}f(u\|V-u)$	$\displaystyle\leq c_{f}f(V)$
		$\displaystyle=c_{f}(f(V)-f(V-X)+f(V-X))$
		$\displaystyle\leq c_{f}\left(f(V)-f(V-X)\right)+c_{f}\rho\|V-X\|$
		$\displaystyle\leq c_{f}\sum_{u\in X}f(u\|V-u)+c_{f}\rho\|V-X\|$
		$\displaystyle<\frac{1}{1+1/\epsilon}\sum_{u\in V}f(u\|V-u)+c_{f}\rho\|V-X\|.$

Here, the first inequality is by definition of the parameter $c_{f}$ . The second inequality is because $X$ is a feasible $\rho\text{-}\textsc{SupmodDD}$ for the function $f$ . The third inequality is by (1). The final inequality is by our contradiction assumption. Then, on rearranging the terms, we obtain the following contradiction.

c_{f}\rho|V-X|>\left(1-\frac{1}{1+1/\epsilon}\right)\sum_{u\in V}f(u|V-u)=% \frac{1}{(1+\epsilon)}\sum_{u\in V}f(u|V-u)\geq c_{f}\rho|V|,

where the final inequality is because $f(u|V-u)\geq c_{f}(1+\epsilon)\rho$ for all $u\in V$ . $\hfill\blacktriangleleft$

3.3 Random Deletion Algorithm

We now describe our bicriteria algorithm for $\rho$ -SupmodDD and analyze its approximation factor. Algorithm 1, Lemma 23 and Lemma 24 together complete the proof of Theorem 11.

Algorithm.

Our algorithm takes as input (1) a normalized non-negative supermodular function $f\mathrel{\mathop{\ordinarycolon}}2^{V}\rightarrow\mathbb{R}_{+}$ , (2) element deletion costs $c\mathrel{\mathop{\ordinarycolon}}V\rightarrow\mathbb{R}_{+}$ , (3) target density $\rho\in\mathbb{R}_{+}$ , and (4) error parameter $\epsilon>0$ . The algorithm returns a set $S\subseteq V$ which starts off as the empty-set and is then constructed element-by-element. This is done iteratively as follows. Let $\beta\mathrel{\mathop{\ordinarycolon}}=c_{f}(1+\epsilon)$ . If the function $f$ has density at most $\beta\rho$ , then the algorithm breaks and returns the current set $S$ . Otherwise, the algorithm first computes the dense decomposition $(V_{1},\phi_{1}),(V_{2},\phi_{2}),\ldots,(V_{k},\phi_{k})$ of the function $f$ , defines the set $R\mathrel{\mathop{\ordinarycolon}}=\cup_{i\in[k]\mathrel{\mathop{% \ordinarycolon}}\phi_{i}>\beta\rho}V_{i}$ , and redefines the function $f$ to be the restricted function $f|_{R}\mathrel{\mathop{\ordinarycolon}}2^{R}\rightarrow\mathbb{R}_{\geq 0}$ – we use DenseDecompositionPreprocess $(f,\rho)$ to denote a subroutine that computes the set $R$ and returns the tuple $(f|_{R},R)$ . Next, the algorithms samples a random element $u$ from the (modified) set $V$ in proportion to the ratio $f(u|V-u)/c(u)$ . The algorithm then adds the vertex $u$ to the set $S$ , restricts $f$ to the ground set $V-u$ , and repeats the previous steps. We give a formal description of the algorithm in Algorithm 1.

Algorithm 1 Bicriteria approximation algorithm for

\rho

-SupmodDD.

Algorithm $\left(\left(f\mathrel{\mathop{\ordinarycolon}}2^{V}\rightarrow\mathbb{R},c% \right),\rho,\epsilon\right)$ :

1.

$S\mathrel{\mathop{\ordinarycolon}}=\emptyset$
2.
while $\lambda_{f}^{*}>c_{f}(1+\epsilon)\rho$ :
1. (a)
  
  Redefine $(f,V)\mathrel{\mathop{\ordinarycolon}}=$ DenseDecompositionPreprocess $(f,c_{f}(1+\epsilon)\rho)$
2. (b)
  
  $u\mathrel{\mathop{\ordinarycolon}}=$ vertex sampled from $V$ according to the following distribution:
  
  $\Pr(u=v)\mathrel{\mathop{\ordinarycolon}}=\frac{f(v|V-v)}{c(v)\cdot W}\ % \forall v\in V,\text{ where $W\mathrel{\mathop{\ordinarycolon}}=\sum_{v\in V}% \frac{f(v|V-v)}{c(v)}$ is a normalizing factor}$
3. (c)
  
  $S\mathrel{\mathop{\ordinarycolon}}=S+u$ and $f\mathrel{\mathop{\ordinarycolon}}=f|_{V-u}$
3.

return $S$ .

Martingales.

For the analysis of our randomized algorithm, we will require the following concepts from probability theory.

Definition 21.

1.

A sequence of random variables $P_{1},P_{2},...$ is called a supermartingale w.r.t. the sequence $X_{1},X_{2},\ldots$ of random variables if for each $i\in\mathbb{Z}_{+}$ it holds that (i) $P_{i}$ is a function of $X_{1},\ldots X_{i}$ , (ii) $\mathbb{E}[|P_{i}|]<\infty$ and (iii) $\mathbb{E}[P_{i+1}|X_{1},\ldots X_{i}]\leq P_{i}$ .
2.

A random variable $T$ is called a stopping time with respect to the sequence of random variables $P_{1},P_{2},...$ if for each $i\in\mathbb{Z}_{+}$ , the event $(T\leq i)$ depends only on $P_{1},\ldots,P_{i}$ .

The following result shows that the expected value of a random variable in the supermartingale process only decreases with time. This will be crucial in analyzing the performance of Algorithm 1.

Theorem 22 (Doob’s Optional-Stopping Theorem).

Let $P_{0},P_{1},\ldots$ be a supermartingale w.r.t. the sequence $X_{1},X_{2},\ldots$ of random variables and $\ell$ be a stopping time with respect to the process $P$ . Suppose that $\Pr(\ell\leq n)=1$ for some integer $n\in\mathbb{Z}_{+}$ . Then, we have that $\mathbb{E}[P_{\ell}]\leq\mathbb{E}[P_{0}]$ .

Algorithm Analysis.

Henceforth, we consider the execution of Algorithm 1 on a fixed input instance $(f,c,\rho,\epsilon)$ . Let $\ell\in\mathbb{Z}_{+}$ be the number of iterations of the while-loop – we note that $\ell$ is a random variable with value at most $n$ since at every iteration of the while-loop, the size of the ground set decreases by at least $1$ . Throughout the analysis, we will index the (random) variables at the $i^{th}$ iteration of the algorithm with the subscript $i$ for all $i\in[\ell]$ . In particular, we let $S_{i}$ denote the set $S$ at the start of the $i^{th}$ iteration (so $S_{1}\mathrel{\mathop{\ordinarycolon}}=\emptyset$ , and $S_{i+1}$ is defined by Step 2(c)), $f_{i}\mathrel{\mathop{\ordinarycolon}}2^{V_{i}}\rightarrow\mathbb{R}_{\geq 0}$ denote the preprocessed function $f$ after step 2(a), and $u_{i}$ denote the sampled vertex $u$ after step 2(b) of the $i^{th}$ iteration of the algorithm. For simplicity, we define $S_{j}\mathrel{\mathop{\ordinarycolon}}=S$ , and $f_{j}$ to be the empty-function for all $j\geq\ell$ . The next lemma shows that the density of the function after deleting the set $S$ is at most $c_{f}(1+\epsilon)\rho$ , i.e. $S$ is a feasible solution to $(c_{f}(1+\epsilon)\rho)\text{-}\textsc{SupmodDD}$ for the function $f$ . The proof easily follows by considering any fixed execution of the algorithm and leveraging Lemma 19(1) while inducting on $\ell$ . We omit details of the proof here for brevity.

Lemma 23 (Approximate Feasibility).

$\lambda^{*}_{f|_{V-S}}\leq c_{f}(1+\epsilon)\rho$ .

The next lemma shows that the expected cost of the solution returned by the algorithm is at most $c_{f}(1+1/\epsilon)\rho$ times the cost of the optimal $\rho\text{-}\textsc{SupmodDD}$ of the function $f$ . For any restriction $g$ of the function $f$ , we use $\mathtt{OPT}(g)$ to denote the value of an optimal $\rho\text{-}\textsc{SupmodDD}$ for $g$ with respect to the cost function $c$ .

Lemma 24 (Approximate Cost).

$\mathbb{E}[c(S)]\leq c_{f}(1+1/\epsilon)\mathtt{OPT}(f)$ .

Proof.

For ease of exposition, we will use $\alpha\mathrel{\mathop{\ordinarycolon}}=c_{f}(1+1/\epsilon)$ . We consider the sequence of random variables $P_{1},P_{2},\ldots$ , where $P_{i}\mathrel{\mathop{\ordinarycolon}}=c(S_{i})+\alpha\mathtt{OPT}(f_{i})$ for all $i\in\mathbb{Z}_{+}$ . Our strategy will be to first show that this sequence of random variables is a supermartingale, and then apply Doob’s Optional-Stopping Theorem with stopping time $n$ to bound the expected cost of the set returned by the algorithm (note that $\ell\leq n$ since with each iteration of the while-loop, the size of the ground set decreases by at least $1$ ). Before showing that the sequence is a supermartingale, we first show that the expected cost of a vertex chosen in step 2(b) of an iteration of the algorithm is at most an $\alpha$ -fraction of the expected decrease in the optimum value during the iteration.

Claim 25.

$\mathbb{E}[c(u_{i})|u_{1},u_{2},\ldots,u_{i-1}]\leq\alpha\mathbb{E}\left[% \mathtt{OPT}(f_{i})-\mathtt{OPT}(f_{i+1})|u_{1},u_{2},\ldots,u_{i-1}\right]$ for all $i\in[\ell]$ .

Proof.

Let $X_{i}$ be an optimal $\rho\text{-}\textsc{SupmodDD}$ for $f_{i}$ . We have the following:

	$\displaystyle\mathbb{E}[c(u_{i})\|u_{1},u_{2},\ldots,u_{i-1}]$	$\displaystyle=\sum_{v\in V_{i}}\Pr(u_{i}=v)\cdot c(v)$
		$\displaystyle=\frac{1}{W}\sum_{v\in V_{i}}f_{i}(v\|V_{i})$
		$\displaystyle\leq\frac{\alpha}{W}\sum_{v\in X_{i}}f_{i}(v\|V_{i})$
		$\displaystyle=\alpha\sum_{v\in X_{i}}\Pr(u_{i}=v)\cdot c(v),$

where the first inequality is by Lemma 20 and the fact that $f(v|V_{i})\geq c_{f}(1+\epsilon)\rho$ by our preprocessing (Step 2(a)) and Lemma 19(3). We now show that because $X_{i}$ is an optimal solution for $f_{i}$ , the final expression in the above can be upper bounded by $\alpha\mathbb{E}[\mathtt{OPT}(f_{i})-\mathtt{OPT}(f_{i+1})]$ , thereby completing the proof of the claim. This can be seen as follows:

	$\displaystyle\mathbb{E}[\mathtt{OPT}(f_{i})-\mathtt{OPT}(f_{i+1})]$	$\displaystyle=\sum_{v\in V_{i}}\mathbb{E}[\mathtt{OPT}(f_{i})-\mathtt{OPT}(f_{% i+1})\|u_{i}=v]\cdot\Pr(u_{i}=v)$
		$\displaystyle\geq\sum_{v\in X_{i}}\mathbb{E}[\mathtt{OPT}(f_{i})-\mathtt{OPT}(% f_{i+1})\|u_{i}=v]\cdot\Pr(u_{i}=v)$
		$\displaystyle\geq\sum_{v\in X_{i}}\mathbb{E}[\mathtt{OPT}(f_{i})-\mathtt{OPT}(% f_{i}\|_{V_{i}-v})\|u_{i}=v]\cdot\Pr(u_{i}=v)$
		$\displaystyle\geq\sum_{v\in X_{i}}\mathbb{E}[c(X_{i})-c(X_{i}-v)\|u_{i}=v]\cdot% \Pr(u_{i}=v)$
		$\displaystyle=\sum_{v\in X_{i}}c(v)\cdot\Pr(u_{i}=v).$

Here, the second inequality is by Step 2(b) of Algorithm 1 which says that the function $f_{i+1}$ is defined to be $\textsc{DenseDecompositionPreprocess}(f_{i}|_{V_{i}-v},c_{f}(1+\epsilon)\rho)$ and Lemma 19(2). The third inequality is because $X_{i}$ is an optimal solution for $f_{i}$ and $X_{i}-v$ is a feasible solution for $f_{i}|_{V_{i}-v}$ . $\hfill\vartriangleleft$

We now show that the sequence $P_{1},P_{2},\ldots$ is a supermartingale w.r.t. the sequence of random variables $u_{1},u_{2},\ldots$ chosen by the algorithm.

Claim 26.

The sequence of random variables $P_{1},P_{2},\ldots$ is a supermartingale w.r.t. the sequence of random variables $u_{1},u_{2},\ldots$ .

Proof.

Let $i\in\mathbb{Z}_{+}$ be arbitrary. We note that $P_{i}$ has finite expectation and also is fully determined by the subsequence $u_{1},\ldots,u_{i}$ . Thus, our goal is to show that $\mathbb{E}[P_{i+1}|u_{1},\ldots,u_{i}]\leq P_{i}$ . This is equivalent to showing $\mathbb{E}[P_{i+1}-P_{i}|u_{1},\ldots,u_{i}]\leq 0$ . We note that this inequality indeed holds because

\mathbb{E}[P_{i+1}-P_{i}|u_{1},\ldots,u_{i}]=\mathbb{E}\left[c(u_{i+1})-\alpha% \left(\mathtt{OPT}(f_{i})-\mathtt{OPT}(f_{i+1})\right)|u_{1},\ldots,u_{i}% \right]\leq 0,

where the inequality is by Claim 25. $\hfill\vartriangleleft$

By Claim 26, the sequence $P_{1},P_{2},\ldots$ is a supermartingale w.r.t. the sequence $u_{1},u_{2},\ldots$ of random variables. Consider the stopping time $\ell$ . By Theorem 22, we have that $\mathbb{E}[P_{\ell}]\leq\mathbb{E}[P_{1}]$ . The following then completes the proof of the lemma:

\mathbb{E}[c(S)]=\mathbb{E}[c(S_{\ell})+\alpha\mathtt{OPT}(f_{\ell})]=\mathbb{% E}[P_{\ell}]\leq\mathbb{E}[P_{1}]=c(S_{1})+\alpha\mathtt{OPT}(f_{1})\leq\alpha% \mathtt{OPT}(f).

Here, the final inequality follows by observing that $f_{1}=\textsc{DenseDecompositionPreprocess}(f,c_{f}(1+\epsilon)\rho)$ and applying Lemma 19(2). $\hfill\blacktriangleleft$

4 SubmodCover and SupmodDD

In this section, we prove Theorems 5 and 8.

See 5

Proof.

For simplicity, we define an intermediate function $g\mathrel{\mathop{\ordinarycolon}}2^{V}\rightarrow\mathbb{R}_{\geq 0}$ , and use it to define the function $h\mathrel{\mathop{\ordinarycolon}}2^{V}\rightarrow\mathbb{R}_{\geq 0}$ of interest. The functions $g$ and $h$ are as follows: for every $X\subseteq V$ ,

	$\displaystyle g(X)$	$\displaystyle\mathrel{\mathop{\ordinarycolon}}=\max\{f(Z)-\rho\|Z\|\mathrel{% \mathop{\ordinarycolon}}Z\subseteq X\},\text{ and }$
	$\displaystyle h(X)$	$\displaystyle\mathrel{\mathop{\ordinarycolon}}=g(V)-g(V-X).$

The following claim shows that the function $h$ is normalized, non-decreasing, and submodular.

Claim 27.

The function $h$ is normalized, non-decreasing, and submodular.

Proof.

We note that $h$ is normalized by definition, and is non-decreasing because the $g$ is non-decreasing. To show that $h$ is submodular, it suffices to show that the $g$ is supermodular. Let $A,B\subseteq V$ be arbitrary. Let $Z_{A}\mathrel{\mathop{\ordinarycolon}}=\arg\max\{f(Z)-\rho|Z|\mathrel{\mathop{% \ordinarycolon}}Z\subseteq A\}$ and $Z_{B}\mathrel{\mathop{\ordinarycolon}}=\arg\max\{f(Z)-\rho|Z|\mathrel{\mathop{% \ordinarycolon}}Z\subseteq B\}$ . Then, we have the following:

	$\displaystyle g(A)+g(B)$	$\displaystyle=f(Z_{A})-\rho\|Z_{A}\|+f(Z_{B})-\rho\|Z_{B}\|$
		$\displaystyle\leq f(Z_{A}\cup Z_{B})+f(Z_{A}\cap Z_{B})-\rho\|Z_{A}\cup Z_{B}\|-% \rho\|Z_{A}\cap Z_{B}\|$
		$\displaystyle=(f(Z_{A}\cup Z_{B})-\rho\|Z_{A}\cup Z_{B}\|)+(f(Z_{A}\cap Z_{B})-% \rho\|Z_{A}\cap Z_{B}\|)$
		$\displaystyle\leq g(A\cup B)+g(A\cap B).$

Here, the first inequality follows from supermodularity of $f$ and the second inequality is by definition of $g$ . $\hfill\vartriangleleft$

Let $F\subseteq V$ . We now show that $\lambda^{*}_{F|_{V-F}}\leq\rho$ if and only if $h(F)\geq h(V)$ as claimed. We have the following sequence of equivalences.

$\displaystyle\lambda^{*}_{f_{V-F}}\leq\rho\Leftrightarrow\$	$\displaystyle\max_{S\subseteq V-F}\left\{\frac{f(S)}{\|S\|}\right\}\leq\rho$
$\displaystyle\Leftrightarrow\$	$\displaystyle g(V-F)\leq 0$	(2)
$\displaystyle\Leftrightarrow\$	$\displaystyle g(V)-g(V-F)-g(V)+g(\emptyset)\geq 0$
$\displaystyle\Leftrightarrow\$	$\displaystyle h(F)-h(V)\geq 0.$

Here, the second equivalence can be seen by the following. For the forward direction, we suppose that $\max\left\{\frac{f|_{V-F}(S)}{|S|}\mathrel{\mathop{\ordinarycolon}}S\subseteq V% -F\right\}\leq\rho$ . By way of contradiction, suppose that $g(V-F)>0$ . By definition of the function $g$ , there exists a set $Z^{*}\subseteq V-F$ such that $g(V-F)=f(Z^{*})-\rho|Z^{*}|$ . Thus, $f(Z^{*})-\rho|Z^{*}|>0$ . Equivalently, we have that $f(Z^{*})/|Z^{*}|>\rho$ , a contradiction to our hypothesis. Here we note that $Z^{*}\not=\emptyset$ as otherwise we would have that $f(Z^{*})-\rho|Z^{*}|=0$ since our function $f$ is normalized, contradicting our choice of $Z^{*}$ . For the reverse direction, suppose that $g(V-F)\leq 0$ . By way of contradiction, suppose that there exists a non-empty set $S^{*}\subseteq V-F$ such that $f(S^{*})/|S^{*}|>\rho$ . Then, we equivalently have that $f(S^{*})-\rho|S^{*}|>0$ , a contradiction.

We now show that the function $h$ satisfies properties (1)-(3) of the theorem. We note that if $\rho$ is an integer, then $h$ is integer-valued by definition. Moreover, we can answer evaluation queries for $h$ using polynomial many evaluation queries to $f$ (via supermodular maximization). Thus $h$ satisfies properties (1) and (3). We now show property (2).

Let $v\in V$ . We have the following:

	$\displaystyle h(v)$	$\displaystyle=g(V)-g(V-v)$
		$\displaystyle=\max\left\{f(Z)-\rho\|Z\|\mathrel{\mathop{\ordinarycolon}}Z% \subseteq V\right\}-\max\left\{f(Z^{\prime})-\rho\|Z^{\prime}\|\mathrel{\mathop{% \ordinarycolon}}Z^{\prime}\subseteq V-v\right\}$
		$\displaystyle=\max\left\{0,\max\left\{f(Z)-\rho\|Z\|\mathrel{\mathop{% \ordinarycolon}}v\in Z\subseteq V\right\}-\max\left\{f(Z^{\prime})-\rho\|Z^{% \prime}\|\mathrel{\mathop{\ordinarycolon}}Z^{\prime}\subseteq V-v\right\}\right\}$
		$\displaystyle\leq\max\left\{0,\max\left\{(f(Z)-\rho\|Z\|)-(f(Z^{\prime})-\rho\|Z^% {\prime}\|)\mathrel{\mathop{\ordinarycolon}}v\in Z\subseteq V\text{ and }Z^{% \prime}\subseteq V-v\right\}\right\}$
		$\displaystyle\leq\max\left\{0,\max\left\{(f(Z)-\rho\|Z\|)-(f(Z-v)-\rho\|Z-v\|)% \mathrel{\mathop{\ordinarycolon}}v\in Z\subseteq V\right\}\right\}$
		$\displaystyle=\max\left\{0,\max\left\{(f(Z)-f(Z-v)\mathrel{\mathop{% \ordinarycolon}}v\in Z\subseteq V\right\}-\rho\right\}$
		$\displaystyle\leq\max\left\{0,f(V)-f(V-v)-\rho\right\},$

where the final inequality is because $f(V-v)+f(Z)\leq f(V)+f(Z-v)$ for all $Z\subseteq V$ such that $v\in Z$ by supermodularity of the function $f$ . $\hfill\blacktriangleleft$

See 8

Proof.

We consider the function $f\mathrel{\mathop{\ordinarycolon}}2^{V}\rightarrow\mathbb{Z}_{\geq 0}$ defined as follows: for every $X\subseteq V$ ,

f(X)\mathrel{\mathop{\ordinarycolon}}=h(V)-h(V-X)+|X|.

We note that the function $f$ is normalized, non-decreasing, integer-valued and supermodular. Moreover, we can answer evaluation queries for the function $f$ using two queries to the evaluation oracle for $h$ . We note that for $F\subseteq V$ , $h(F)\geq h(V)$ if and only if $\lambda^{*}_{f|_{V-F}}\leq 1$ can be observed by following the steps of (2) in reverse order, and so we omit the formal details here for brevity. Property (1) of the theorem can be observed as follows: for $v\in V$ , we have the following:

	$\displaystyle f(v\|V-v)=f(V)-f(V-v)$	$\displaystyle=(h(V)-h(\emptyset)+\|V\|)-(h(V)-h(v)+\|V-v\|)$
		$\displaystyle=h(v)+1,$

where the final equality is because $h$ is normalized. $\hfill\blacktriangleleft$

5 Conclusion

We considered several interrelated density deletion problems motivated by the question of understanding the robustness of densest subgraph. We showed tight logarithmic approximations for these problems. We showed inapproximability of graph density deletion by reduction from set cover, and approximation algorithms by exhibiting the equivalence of supermodular density deletion and submodular cover. Motivated by the hardness results, we designed bicriteria approximations. Our bicriteria approximation for graph density deletion is LP-based, and that for supermodular density deletion is a randomized combinatorial one and relies on the notion of dense decomposition of supermodular functions. We mention two open questions. First, our bicriteria approximation for supermodular density deletion depends on the parameter $c_{f}$ related to the input supermodular function (see Theorem 11). Is it possible to design a bicriteria approximation without dependence on the parameter $c_{f}$ ? Second, our hardness reduction shows that $\rho$ -GraphDD is $\Omega(\log{n})$ -hard for every fixed constant integer $\rho\geq 2$ . We were able to adapt our reduction to conclude that it is $\Omega(\log{n})$ -hard for every fixed constant $\rho\geq 3$ (not necessarily integers). Is $\rho$ -GraphDD $\Omega(\log{n})$ -hard for every fixed constant $\rho>1$ ?

References

[1] Vineet Bafna, Piotr Berman, and Toshihiro Fujito. Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs. In Algorithms and Computations, pages 142–151, 1995. doi:10.1007/BFB0015417.
[2] Cristina Bazgan, André Nichterlein, and Sofia Vazquez Alferez. Destroying Densest Subgraphs Is Hard. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024), pages 6:1–6:17, 2024. doi:10.4230/LIPICS.SWAT.2024.6.
[3] Ann Becker and Dan Geiger. Optimization of Pearl’s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artificial Intelligence, 83:167–188, 1996. doi:10.1016/0004-3702(95)00004-6.
[4] Digvijay Boob, Yu Gao, Richard Peng, Saurabh Sawlani, Charalampos Tsourakakis, Di Wang, and Junxing Wang. Flowless: Extracting densest subgraphs without flow computations. In Proceedings of The Web Conference 2020, pages 573–583, 2020. doi:10.1145/3366423.3380140.
[5] Karthekeyan Chandrasekaran, Chandra Chekuri, Samuel Fiorini, Shubhang Kulkarni, and Stefan Weltge. Polyhedral aspects of feedback vertex set and pseudoforest deletion set. Mathematical Programming, pages 1–48, 2025.
[6] Karthekeyan Chandrasekaran, Chandra Chekuri, and Shubhang Kulkarni. On deleting vertices to reduce density in graphs and supermodular functions, 2025. doi:10.48550/arXiv.2503.08828.
[7] Moses Charikar. Greedy Approximation Algorithms for Finding Dense Components in a Graph. In Approximation Algorithms for Combinatorial Optimization, pages 84–95, 2000. doi:10.1007/3-540-44436-X_10.
[8] Chandra Chekuri, Aleksander Bjørn Christiansen, Jacob Holm, Ivor van der Hoog, Kent Quanrud, Eva Rotenberg, and Chris Schwiegelshohn. Adaptive out-orientations with applications. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3062–3088, 2024.
[9] Chandra Chekuri, Kent Quanrud, and Manuel R Torres. Densest subgraph: Supermodularity, iterative peeling, and flow. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1531–1555, 2022. doi:10.1137/1.9781611977073.64.
[10] Fabián A. Chudak, Michel X. Goemans, Dorit S. Hochbaum, and David P. Williamson. A primal–dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Operations Research Letters, 22(4):111–118, 1998. doi:10.1016/S0167-6377(98)00021-2.
[11] William H Cunningham. Optimal attack and reinforcement of a network. Journal of the ACM (JACM), 32(3):549–561, 1985. doi:10.1145/3828.3829.
[12] Laxman Dhulipala, Quanquan C Liu, Sofya Raskhodnikova, Jessica Shi, Julian Shun, and Shangdi Yu. Differential privacy from locally adjustable graph algorithms: k-core decomposition, low out-degree ordering, and densest subgraphs. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 754–765, 2022. doi:10.1109/FOCS54457.2022.00077.
[13] Michael Dinitz, Satyen Kale, Silvio Lattanzi, and Sergei Vassilvitskii. Almost tight bounds for differentially private densest subgraph. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2908–2950, 2025. doi:10.1137/1.9781611978322.94.
[14] Irit Dinur and David Steurer. Analytical approach to parallel repetition. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC, pages 624–633, 2014. doi:10.1145/2591796.2591884.
[15] Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM (JACM), 45(4):634–652, 1998. doi:10.1145/285055.285059.
[16] A. Frank. Connections in combinatorial optimization. Oxford University Press, Oxford, 2011.
[17] Satoru Fujishige. Lexicographically optimal base of a polymatroid with respect to a weight vector. Mathematics of Operations Research, 5(2):186–196, 1980. doi:10.1287/MOOR.5.2.186.
[18] Toshihiro Fujito. Approximating node-deletion problems for matroidal properties. Journal of Algorithms, 31(1):211–227, 1999. doi:10.1006/JAGM.1998.0995.
[19] A. V. Goldberg. Finding a maximum density subgraph. Technical report, University of California at Berkeley, USA, 1984.
[20] Elfarouk Harb, Kent Quanrud, and Chandra Chekuri. Faster and scalable algorithms for densest subgraph and decomposition. In Advances in Neural Information Processing Systems, 2022.
[21] Elfarouk Harb, Kent Quanrud, and Chandra Chekuri. Convergence to lexicographically optimal base in a (contra)polymatroid and applications to densest subgraph and tree packing. In 31st Annual European Symposium on Algorithms (ESA), pages 56:1–56:17, 2023. doi:10.4230/LIPICS.ESA.2023.56.
[22] Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2- $\varepsilon$ . Journal of Computer and System Sciences, 74(3):335–349, 2008.
[23] Tommaso Lanciano, Atsushi Miyauchi, Adriano Fazzone, and Francesco Bonchi. A survey on the densest subgraph problem and its variants. ACM Comput. Surv., 56(8), April 2024. doi:10.1145/3653298.
[24] Audrey Lee and Ileana Streinu. Pebble game algorithms and sparse graphs. Discrete Mathematics, 308(8):1425–1437, April 2008. doi:10.1016/J.DISC.2007.07.104.
[25] John M. Lewis and Mihalis Yannakakis. The node-deletion problem for hereditary properties is np-complete. Journal of Computer and System Sciences, 20(2):219–230, April 1980. doi:10.1016/0022-0000(80)90060-4.
[26] Ta Duy Nguyen and Alina Ene. Multiplicative weights update, area convexity and random coordinate descent for densest subgraph problems. In Proceedings of the 41st International Conference on Machine Learning (ICML), 2024.
[27] Jean-Claude Picard and Maurice Queyranne. A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory. Networks, 12(2):141–159, 1982. doi:10.1002/NET.3230120206.
[28] Saurabh Sawlani and Junxing Wang. Near-optimal fully dynamic densest subgraph. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 181–193, 2020. doi:10.1145/3357713.3384327.
[29] Shuichi Ueno, Yoji Kajitani, and Shin’ya Gotoh. On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three. Discrete Mathematics, 72(1):355–360, December 1988. doi:10.1016/0012-365X(88)90226-9.
[30] Nate Veldt, Austin R Benson, and Jon Kleinberg. The generalized mean densest subgraph problem. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 1604–1614, 2021. doi:10.1145/3447548.3467398.
[31] Laurence A Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, 2(4):385–393, 1982. doi:10.1007/BF02579435.
[32] Michał Włodarczyk. Losing treewidth in the presence of weights. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3743–3761, 2025.

[bib.bib1] [1] Vineet Bafna, Piotr Berman, and Toshihiro Fujito. Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs. In Algorithms and Computations, pages 142–151, 1995. doi:10.1007/BFB0015417.

[bib.bib2] [2] Cristina Bazgan, André Nichterlein, and Sofia Vazquez Alferez. Destroying Densest Subgraphs Is Hard. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024), pages 6:1–6:17, 2024. doi:10.4230/LIPICS.SWAT.2024.6.

[bib.bib3] [3] Ann Becker and Dan Geiger. Optimization of Pearl’s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artificial Intelligence, 83:167–188, 1996. doi:10.1016/0004-3702(95)00004-6.

[bib.bib4] [4] Digvijay Boob, Yu Gao, Richard Peng, Saurabh Sawlani, Charalampos Tsourakakis, Di Wang, and Junxing Wang. Flowless: Extracting densest subgraphs without flow computations. In Proceedings of The Web Conference 2020, pages 573–583, 2020. doi:10.1145/3366423.3380140.

[bib.bib5] [5] Karthekeyan Chandrasekaran, Chandra Chekuri, Samuel Fiorini, Shubhang Kulkarni, and Stefan Weltge. Polyhedral aspects of feedback vertex set and pseudoforest deletion set. Mathematical Programming, pages 1–48, 2025.

[bib.bib6] [6] Karthekeyan Chandrasekaran, Chandra Chekuri, and Shubhang Kulkarni. On deleting vertices to reduce density in graphs and supermodular functions, 2025. doi:10.48550/arXiv.2503.08828.

[bib.bib7] [7] Moses Charikar. Greedy Approximation Algorithms for Finding Dense Components in a Graph. In Approximation Algorithms for Combinatorial Optimization, pages 84–95, 2000. doi:10.1007/3-540-44436-X_10.

[bib.bib8] [8] Chandra Chekuri, Aleksander Bjørn Christiansen, Jacob Holm, Ivor van der Hoog, Kent Quanrud, Eva Rotenberg, and Chris Schwiegelshohn. Adaptive out-orientations with applications. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3062–3088, 2024.

[bib.bib9] [9] Chandra Chekuri, Kent Quanrud, and Manuel R Torres. Densest subgraph: Supermodularity, iterative peeling, and flow. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1531–1555, 2022. doi:10.1137/1.9781611977073.64.

[bib.bib10] [10] Fabián A. Chudak, Michel X. Goemans, Dorit S. Hochbaum, and David P. Williamson. A primal–dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Operations Research Letters, 22(4):111–118, 1998. doi:10.1016/S0167-6377(98)00021-2.

[bib.bib11] [11] William H Cunningham. Optimal attack and reinforcement of a network. Journal of the ACM (JACM), 32(3):549–561, 1985. doi:10.1145/3828.3829.

[bib.bib12] [12] Laxman Dhulipala, Quanquan C Liu, Sofya Raskhodnikova, Jessica Shi, Julian Shun, and Shangdi Yu. Differential privacy from locally adjustable graph algorithms: k-core decomposition, low out-degree ordering, and densest subgraphs. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 754–765, 2022. doi:10.1109/FOCS54457.2022.00077.

[bib.bib13] [13] Michael Dinitz, Satyen Kale, Silvio Lattanzi, and Sergei Vassilvitskii. Almost tight bounds for differentially private densest subgraph. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2908–2950, 2025. doi:10.1137/1.9781611978322.94.

[bib.bib14] [14] Irit Dinur and David Steurer. Analytical approach to parallel repetition. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC, pages 624–633, 2014. doi:10.1145/2591796.2591884.

[bib.bib15] [15] Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM (JACM), 45(4):634–652, 1998. doi:10.1145/285055.285059.

[bib.bib16] [16] A. Frank. Connections in combinatorial optimization. Oxford University Press, Oxford, 2011.

[bib.bib17] [17] Satoru Fujishige. Lexicographically optimal base of a polymatroid with respect to a weight vector. Mathematics of Operations Research, 5(2):186–196, 1980. doi:10.1287/MOOR.5.2.186.

[bib.bib18] [18] Toshihiro Fujito. Approximating node-deletion problems for matroidal properties. Journal of Algorithms, 31(1):211–227, 1999. doi:10.1006/JAGM.1998.0995.

[bib.bib19] [19] A. V. Goldberg. Finding a maximum density subgraph. Technical report, University of California at Berkeley, USA, 1984.

[bib.bib20] [20] Elfarouk Harb, Kent Quanrud, and Chandra Chekuri. Faster and scalable algorithms for densest subgraph and decomposition. In Advances in Neural Information Processing Systems, 2022.

[bib.bib21] [21] Elfarouk Harb, Kent Quanrud, and Chandra Chekuri. Convergence to lexicographically optimal base in a (contra)polymatroid and applications to densest subgraph and tree packing. In 31st Annual European Symposium on Algorithms (ESA), pages 56:1–56:17, 2023. doi:10.4230/LIPICS.ESA.2023.56.

[bib.bib22] [22] Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2- $\varepsilon$ . Journal of Computer and System Sciences, 74(3):335–349, 2008.

[bib.bib23] [23] Tommaso Lanciano, Atsushi Miyauchi, Adriano Fazzone, and Francesco Bonchi. A survey on the densest subgraph problem and its variants. ACM Comput. Surv., 56(8), April 2024. doi:10.1145/3653298.

[bib.bib24] [24] Audrey Lee and Ileana Streinu. Pebble game algorithms and sparse graphs. Discrete Mathematics, 308(8):1425–1437, April 2008. doi:10.1016/J.DISC.2007.07.104.

[bib.bib25] [25] John M. Lewis and Mihalis Yannakakis. The node-deletion problem for hereditary properties is np-complete. Journal of Computer and System Sciences, 20(2):219–230, April 1980. doi:10.1016/0022-0000(80)90060-4.

[bib.bib26] [26] Ta Duy Nguyen and Alina Ene. Multiplicative weights update, area convexity and random coordinate descent for densest subgraph problems. In Proceedings of the 41st International Conference on Machine Learning (ICML), 2024.

[bib.bib27] [27] Jean-Claude Picard and Maurice Queyranne. A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory. Networks, 12(2):141–159, 1982. doi:10.1002/NET.3230120206.

[bib.bib28] [28] Saurabh Sawlani and Junxing Wang. Near-optimal fully dynamic densest subgraph. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 181–193, 2020. doi:10.1145/3357713.3384327.

[bib.bib29] [29] Shuichi Ueno, Yoji Kajitani, and Shin’ya Gotoh. On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three. Discrete Mathematics, 72(1):355–360, December 1988. doi:10.1016/0012-365X(88)90226-9.

[bib.bib30] [30] Nate Veldt, Austin R Benson, and Jon Kleinberg. The generalized mean densest subgraph problem. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 1604–1614, 2021. doi:10.1145/3447548.3467398.

[bib.bib31] [31] Laurence A Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, 2(4):385–393, 1982. doi:10.1007/BF02579435.

[bib.bib32] [32] Michał Włodarczyk. Losing treewidth in the presence of weights. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3743–3761, 2025.

	$\displaystyle\rho^{\prime}<\frac{f(S)}{\|S\|}$	$\displaystyle\leq\frac{f(S\cup R)-f(R)+f(S\cap R)}{\|S-R\|+\|S\cap R\|}$
		$\displaystyle\leq\max\left\{\frac{f(S\cup R)-f(R)}{\|S-R\|},\frac{f(S\cap R)}{\|S% \cap R\|}\right\}$
		$\displaystyle\leq\max\left\{\max\left\{\frac{f(R\cup S^{\prime})-f(R)}{\|S^{% \prime}\|}\mathrel{\mathop{\ordinarycolon}}S^{\prime}\subseteq V-R\right\},% \lambda_{f\|_{R-X}}^{*})\right\}$
		$\displaystyle\leq\rho^{\prime}.$

	$\displaystyle\rho_{j}$	$\displaystyle=\frac{f(U_{j})-f(U_{j-1})}{\|V_{j}\|}$
		$\displaystyle=\frac{f(U_{j})-f(U_{j}-v)+f(U_{j}-v)-f(U_{j-1})}{\|V_{j}\|}$
		$\displaystyle=\frac{f(v\|U_{j}-v)+f(U_{j}-v)-f(U_{j-1})}{1+(\|V_{j}\|-1)}$
		$\displaystyle<\frac{\rho_{j}+f(U_{j}-v)-f(U_{j-1})}{1+(\|V_{j}\|-1)}$
		$\displaystyle\leq\max\left\{\rho_{j},\frac{f(U_{j}-v)-f(U_{j-1})}{\|V_{j}\|-1}\right\}$
		$\displaystyle\leq\max\left\{\rho_{j},\max\left\{\frac{f(U_{j-1}\cup S)-f(U_{j-% 1})}{\|S\|}\mathrel{\mathop{\ordinarycolon}}S\subseteq V-U_{j-1}\right\}\right\}$
		$\displaystyle\leq\rho_{j},$

	$\displaystyle\sum_{u\in V}f(u\|V-u)$	$\displaystyle\leq c_{f}f(V)$
		$\displaystyle=c_{f}(f(V)-f(V-X)+f(V-X))$
		$\displaystyle\leq c_{f}\left(f(V)-f(V-X)\right)+c_{f}\rho\|V-X\|$
		$\displaystyle\leq c_{f}\sum_{u\in X}f(u\|V-u)+c_{f}\rho\|V-X\|$
		$\displaystyle<\frac{1}{1+1/\epsilon}\sum_{u\in V}f(u\|V-u)+c_{f}\rho\|V-X\|.$

	$\displaystyle\mathbb{E}[c(u_{i})\|u_{1},u_{2},\ldots,u_{i-1}]$	$\displaystyle=\sum_{v\in V_{i}}\Pr(u_{i}=v)\cdot c(v)$
		$\displaystyle=\frac{1}{W}\sum_{v\in V_{i}}f_{i}(v\|V_{i})$
		$\displaystyle\leq\frac{\alpha}{W}\sum_{v\in X_{i}}f_{i}(v\|V_{i})$
		$\displaystyle=\alpha\sum_{v\in X_{i}}\Pr(u_{i}=v)\cdot c(v),$

	$\displaystyle\mathbb{E}[\mathtt{OPT}(f_{i})-\mathtt{OPT}(f_{i+1})]$	$\displaystyle=\sum_{v\in V_{i}}\mathbb{E}[\mathtt{OPT}(f_{i})-\mathtt{OPT}(f_{% i+1})\|u_{i}=v]\cdot\Pr(u_{i}=v)$
		$\displaystyle\geq\sum_{v\in X_{i}}\mathbb{E}[\mathtt{OPT}(f_{i})-\mathtt{OPT}(% f_{i+1})\|u_{i}=v]\cdot\Pr(u_{i}=v)$
		$\displaystyle\geq\sum_{v\in X_{i}}\mathbb{E}[\mathtt{OPT}(f_{i})-\mathtt{OPT}(% f_{i}\|_{V_{i}-v})\|u_{i}=v]\cdot\Pr(u_{i}=v)$
		$\displaystyle\geq\sum_{v\in X_{i}}\mathbb{E}[c(X_{i})-c(X_{i}-v)\|u_{i}=v]\cdot% \Pr(u_{i}=v)$
		$\displaystyle=\sum_{v\in X_{i}}c(v)\cdot\Pr(u_{i}=v).$

On Deleting Vertices to Reduce Density in Graphs and Supermodular Functions

Abstract

Keywords and phrases:

Category:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Density Deletion Problems.

Definition 1 (ρ⁢-GraphDD).

Definition 2 (ρ⁢-SupmodDD).

Motivations and Connections.

Definition 3 (MatroidFVS).

Question 1.

1.1 Results

1.1.1 Connections between SubmodCover and SupmodDD

Definition 4 (SubmodCover).

Theorem 5.

Corollary 6.

▶ Remark 7.

Theorem 8.

1.1.2 Hardness of Approximation

Theorem 9.

1.1.3 Bicriteria Approximations

Theorem 10.

Theorem 11.

Organization.

2 Hardness of Approximation

Definition 12 (SetCover).

Theorem 13 ([15, 14]).

Proposition 14.

Proof.

Claim 15.

Proof.

Observation 16.

Proof.

▶ Remark 17.

3 Bicriteria Approximation for GraphDD

3.1 Preprocessing via Dense Decomposition

Definition 18 ([20]).

Lemma 19.

Proof.

3.2 Element Potentials via Marginal Gains

Lemma 20.

Proof.

3.3 Random Deletion Algorithm

Algorithm.

Martingales.

Definition 21.

Theorem 22 (Doob’s Optional-Stopping Theorem).

Algorithm Analysis.

Lemma 23 (Approximate Feasibility).

Lemma 24 (Approximate Cost).

Proof.

Claim 25.

Proof.

Claim 26.

Proof.

4 SubmodCover and SupmodDD

Proof.

Claim 27.

Proof.

Proof.

5 Conclusion

References

Definition 1 ( $\rho\text{-}\textsc{GraphDD}$ ).

Definition 2 ( $\rho\text{-}\textsc{SupmodDD}$ ).

$\blacktriangleright$ Remark 7.

$\blacktriangleright$ Remark 17.