On Deleting Vertices to Reduce Density in Graphs and Supermodular Functions
Karthekeyan Chandrasekaran, Chandra Chekuri, Shubhang Kulkarni · 2025
Read On Deleting Vertices to Reduce Density in Graphs and Supermodular Functions by Karthekeyan Chandrasekaran, Chandra Chekuri, Shubhang Kulkarni (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-08828.txt.
Introduction
Deleting a few well chosen vertices can thin out a dense graph. A 2025 arXiv paper by Karthekeyan Chandrasekaran, Chandra Chekuri, and Shubhang Kulkarni maps when that thinning is cheap to compute. For target density at most one, the problem covers classics like vertex cover and admits a two fold approximation.
Past that point the picture flips. For any fixed target above one, the problem resists approximation within a logarithmic factor. The authors then widen the question to supermodular functions. There it matches a known covering problem exactly, which pins down the best possible guarantee.
Catalog record
| CREATOR | Karthekeyan Chandrasekaran, Chandra Chekuri, Shubhang Kulkarni |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 76 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-08828
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On Deleting Vertices to Reduce Density in Graphs and Supermodular Functions Thanks: Grainger College of Engineering, University of Illinois, Urbana-Champaign, Urbana, IL 61801, Email: {karthe, chekuri, smkulka2}@illinois.edu. Supported in part by NSF grant CCF-2402667. Karthekeyan Chandrasekaran, Chandra Chekuri, Shubhang Kulkarni 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 ) G=(V,E) with non-negative vertex costs and a non-negative parameter ρ ≥ 0 \rho\geq 0 and the goal is to remove a minimum cost subset S S of vertices such that the densest subgraph in G − S 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 ρ ≤ 1 \rho\leq 1 and all of these classical problems admit a 2 2 -approximation. In sharp contrast, we prove that for every fixed integer ρ > 1 \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 : 2 V → ℤ ≥ 0 f\mathrel{\mathop{\mathchar 58\relax}}2^{V}\rightarrow\mathbb{Z}_{\geq 0} via an evaluation oracle with element costs and a non-negative integer ρ ≥ 0 \rho\geq 0 and the goal is remove a minimum cost subset S ⊆ V S\subseteq V such that the densest subset according to f f in V − S 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 . 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{\mathchar 58\relax}}=\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 [ 22 , 4 , 27 , 29 , 8 , 19 , 11 , 12 , 7 , 25 ] . A useful feature of DSG is its polynomial-time solvability. This was first seen via a reduction to network flow [ 18 , 26 ] 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{\mathchar 58\relax}}2^{V}\rightarrow\mathbb{R}_{\geq 0} via evaluation oracle, the goal is to find \lambda^{*}_{f}\mathrel{\mathop{\mathchar 58\relax}}=\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{\mathchar 58\relax}}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 [ 8 , 29 , 19 , 20 ] . 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.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{\mathchar 58\relax}}V\rightarrow\mathbb{R}_{\geq 0} Goal : \arg\min\{\sum_{u\in S}c_{S}\mathrel{\mathop{\mathchar 58\relax}}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{\mathchar 58\relax}}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{\mathchar 58\relax}}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 1.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{\mathchar 58\relax}}2^{V}\rightarrow\mathbb{Z}_{\geq 0} via evaluation oracle and element costs c\mathrel{\mathop{\mathchar 58\relax}}V\rightarrow\mathbb{R}_{\geq 0} Goal : \arg\min\{\sum_{u\in S}c_{u}\mathrel{\mathop{\mathchar 58\relax}}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 [ 24 ] . 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 [ 10 ] 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. Vertex cover,