More Like this

1. On Deleting Vertices to Reduce Density in Graphs and Supermodular Functions

   https://doi.org/10.4230/lipics.icalp.2025.43  

   Chandrasekaran, Karthekeyan; Chekuri, Chandra; Kulkarni, Shubhang (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Censor-Hillel, Keren; Grandoni, Fabrizio; Ouaknine, Joel; Puppis, Gabriele (Ed.)

   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 ρ ≥ 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 ρ. 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 and all of these classical problems admit a 2-approximation. In sharp contrast, we prove that for every fixed integer ρ > 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} via an evaluation oracle with element costs and a non-negative integer ρ ≥ 0 and the goal is remove a minimum cost subset S ⊆ V such that the densest subset according to f in V-S has density at most ρ. 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. 

   more » « less
2. Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems

   Harb, Elfarouk; Yassin, Yousef; Chekuri, Chandra (December 2025, Proceedings of NeurIPS, 2025)

   We consider the following question: given a submodular/supermodular set function f : 2V → R, how should one minimize/maximize its average value f (S)/|S|over non-empty subsets S ⊆ V ? This problem generalizes several well-known objectives, including Densest Subgraph (DSG), Densest Supermodular Set (DSS), and Submodular Function Minimization (SFM). Motivated by recent applications [42, 34], we formalize two new broad problems: the Unrestricted Sparsest Submodular Set (USSS) and Unrestricted Densest Supermodular Set (UDSS), both of which allow negative and non-monotone functions. Using classical results, we show that DSS, SFM, USSS, UDSS, and Minimum Norm Point (MNP) are all equivalent under strongly polynomial-time reductions. This equivalence enables algorithmic cross-over: methods designed for one problem can be repurposed to solve others efficiently. In particular, we use the perspective of the minimum norm point in the base polyhedron of a sub/supermodular function, which, via Fujishige’s results, yields the dense decomposition as a byproduct. Through this perspective, we show that a recent converging heuristic for DSS, SUPERGREEDY++ [17, 32], and Wolfe’s minimum norm point algorithm are both universal solvers for all of these problems. On the theoretical front, we explain the observation made in recent work [42, 34] that SUPERGREEDY++ appears to work well even in settings beyond DSS. Surprisingly, we also show that this simple algorithm can be used for Submodular Function Minimization, including acting as a practical minimum s-t cut algorithm. On the empirical front, we explore the utility of several algorithms for recent problems. We conduct over 400 experiments across seven problem types and largescale synthetic and real-world datasets (up to ≈ 100 million edges). Our results reveal that methods historically considered inefficient, such as convex-programming methods, flow-based solvers, and Fujishige-Wolfe’s algorithm, outperform stateof-the-art task-specific baselines by orders of magnitude on concrete problems like HNSN [42]. These findings challenge prevailing assumptions and demonstrate that with the proper framing, general optimization algorithms can be both scalable and state-of-the-art for supermodular and submodular ratio problems. 

   more » « less
3. Convergence to Lexicographically Optimal Base in a (Contra)Polymatroid and Applications to Densest Subgraph and Tree Packing

   https://doi.org/10.4230/LIPICS.ESA.2023.56  

   Harb, Elfarouk; Quanrud, Kent; Chekuri, Chandra (January 2023, 31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands)

   Gørtz, Inge Li; Farach-Colton, Martin; Puglisi, Simon J.; Herman, Grzegorz (Ed.)

   Boob et al. [Boob et al., 2020] described an iterative peeling algorithm called Greedy++ for the Densest Subgraph Problem (DSG) and conjectured that it converges to an optimum solution. Chekuri, Qaunrud and Torres [Chandra Chekuri et al., 2022] extended the algorithm to supermodular density problems (of which DSG is a special case) and proved that the resulting algorithm Super-Greedy++ (and hence also Greedy++) converges. In this paper we revisit the convergence proof and provide a different perspective. This is done via a connection to Fujishige’s quadratic program for finding a lexicographically optimal base in a (contra) polymatroid [Satoru Fujishige, 1980], and a noisy version of the Frank-Wolfe method from convex optimization [Frank and Wolfe, 1956; Jaggi, 2013]. This yields a simpler convergence proof, and also shows a stronger property that Super-Greedy++ converges to the optimal dense decomposition vector, answering a question raised in Harb et al. [Harb et al., 2022]. A second contribution of the paper is to understand Thorup’s work on ideal tree packing and greedy tree packing [Thorup, 2007; Thorup, 2008] via the Frank-Wolfe algorithm applied to find a lexicographically optimum base in the graphic matroid. This yields a simpler and transparent proof. The two results appear disparate but are unified via Fujishige’s result and convex optimization. 

   more » « less
4. On the Generalized Mean Densest Subgraph Problem: Complexity and Algorithms

   https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.9  

   Chandrasekaran, Karthekeyan; Chekuri, Chandra; Torres, Manuel R; Zhu, Weihao (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Kumar, Amit; Ron-Zewi, Noga (Ed.)

   Dense subgraph discovery is an important problem in graph mining and network analysis with several applications. Two canonical polynomial-time solvable problems here are to find a maxcore (subgraph of maximum min degree) and to find a densest subgraph (subgraph of maximum average degree). Both of these problems can be solved in polynomial time. Veldt, Benson, and Kleinberg [Veldt et al., 2021] introduced the generalized p-mean densest subgraph problem which captures the maxcore problem when p = -∞ and the densest subgraph problem when p = 1. They observed that for p ≥ 1, the objective function is supermodular and hence the problem can be solved in polynomial time. In this work, we focus on the p-mean densest subgraph problem for p ∈ (-∞, 1). We prove that for every p ∈ (-∞,1), the problem is NP-hard, thus resolving an open question from [Veldt et al., 2021]. We also show that for every p ∈ (0,1), the weighted version of the problem is APX-hard. On the algorithmic front, we describe two simple 1/2-approximation algorithms for every p ∈ (-∞, 1). We complement the approximation algorithms by exhibiting non-trivial instances on which the algorithms simultaneously achieve an approximation factor of at most 1/2. 

   more » « less
5. Improved Approximation Algorithms for Capacitated Network Design and Flexible Graph Connectivity

   https://doi.org/10.4230/lipics.icalp.2025.20  

   Bansal, Ishan; Cheriyan, Joe; Khanna, Sanjeev; Simmons, Miles (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Censor-Hillel, Keren; Grandoni, Fabrizio; Ouaknine, Joel; Puppis, Gabriele (Ed.)

   Abstract: We present improved approximation algorithms for some problems in the related areas of Capacitated Network Design and Flexible Graph Connectivity. In the Cap-k-ECSS problem, we are given a graph G = (V,E) whose edges have non-negative costs and positive integer capacities, and the goal is to find a minimum-cost edge-set F such that every non-trivial cut of the graph G' = (V,F) has capacity at least k. Let n = |V| and let u_{min} (respectively, u_{max}) denote the minimum (respectively, maximum) capacity of an edge; assume that u_{max} ≤ k. We present an O(log({k}/u_{min}))-approximation algorithm for the Cap-k-ECSS problem, asymptotically improving upon the previous best approximation ratio of min(O(log{n}), k, 2u_{max}, 6 ⋅ {⌈ k/u_{min} ⌉}) whenever log(k/u_{min}) = o(log{n}) and u_{max} is sufficiently large. In the (p,q)-Flexible Graph Connectivity problem, denoted (p,q)-FGC, the input is a graph G = (V, E) where E is partitioned into safe and unsafe edges, and the goal is to find a minimum-cost edge-set F such that the subgraph G' = (V, F) remains p-edge connected upon removal of any q unsafe edges from F. We present an 8-approximation algorithm for the (1,q)-FGC problem that improves upon the previous best approximation ratio of (q+1). Both of our results are obtained by using natural LP relaxations strengthened with the knapsack-cover inequalities, and then, during the rounding process, utilizing a recent O(1)-approximation algorithm for the Cover Small Cuts problem. In the latter problem, the goal is to find a minimum-cost set of links such that each non-trivial cut of capacity less than a specified value is covered by a link. We also show that the problem of covering small cuts inherently arises in another variant of (p,q)-FGC. Specifically, we give Cook reductions that preserve approximation ratios within O(1) factors between the (2,q)-FGC problem and the 2-Cover Small Cuts problem; in the latter problem, each small cut needs to be covered by two links. 

   more » « less