Cover Image

Destroying Densest Subgraphs is Hard

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bazgan, Cristina, Nichterlein, André, Alferez, Sofia Vazquez
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Scalable $k$-clique Densest Subgraph Search
by: Ye, Xiaowei, et al.
Published: (2024)

New Parallel and Streaming Algorithms for Directed Densest Subgraph
by: Mitrović, Slobodan, et al.
Published: (2025)

Almost Tight Bounds for Differentially Private Densest Subgraph
by: Dinitz, Michael, et al.
Published: (2023)

Fast and Simple Densest Subgraph with Predictions
by: Bui, Thai, et al.
Published: (2025)

An Efficient and Exact Algorithm for Locally h-Clique Densest Subgraph Discovery
by: Xu, Xiaojia, et al.
Published: (2024)

Fast and Optimal Incremental Parametric Procedure for the Densest Subgraph Problem: An Experimental Study
by: Hochbaum, Dorit S., et al.
Published: (2025)

In-depth Analysis of Densest Subgraph Discovery in a Unified Framework
by: Zhou, Yingli, et al.
Published: (2024)

Density Matters: A Complexity Dichotomy of Deleting Edges to Bound Subgraph Density
by: Bentert, Matthias, et al.
Published: (2026)

A Survey on the Densest Subgraph Problem and Its Variants
by: Lanciano, Tommaso, et al.
Published: (2023)

A Note on Approximability of Densest At-Least-k-Subgraph
by: Laekhanukit, Bundit, et al.
Published: (2026)

Multiplicative Weights Update, Area Convexity and Random Coordinate Descent for Densest Subgraph Problems
by: Nguyen, Ta Duy, et al.
Published: (2024)

Efficient Processing of Subsequent Densest Subgraph Query
by: Hung, Chia-Yang, et al.
Published: (2024)

The Vertex-Attribute-Constrained Densest $k$-Subgraph Problem
by: Lu, Qiheng, et al.
Published: (2025)

Tighter Bounds for Local Differentially Private Core Decomposition and Densest Subgraph
by: Henzinger, Monika, et al.
Published: (2024)

Designing Approximate Binary Trees for Trees
by: Kellerhals, Leon, et al.
Published: (2026)

When is local search both effective and efficient?
by: Kaznatcheev, Artem, et al.
Published: (2024)

Differentially Private Densest Subgraph Detection
by: Nguyen, Dung, et al.
Published: (2021)

Parameterized Algorithms for Computing MAD Trees
by: Breitkopf, Tom-Lukas, et al.
Published: (2026)

Continual Release of Densest Subgraphs: Privacy Amplification & Sublinear Space via Subsampling
by: Zhou, Felix
Published: (2025)

On Densest $k$-Subgraph Mining and Diagonal Loading: Optimization Landscape and Finite-Step Exact Convergence Analysis
by: Lu, Qiheng, et al.
Published: (2024)

OptiRefine: Densest subgraphs and maximum cuts with $k$ refinements
by: Tu, Sijing, et al.
Published: (2025)

The Densest SWAMP problem: subhypergraphs with arbitrary monotonic partial edge rewards
by: Bengali, Vedangi, et al.
Published: (2025)

Counting Small Induced Subgraphs: Hardness via Fourier Analysis
by: Curticapean, Radu, et al.
Published: (2024)

SpiderDAN: Matching Augmentation in Demand-Aware Networks
by: Figiel, Aleksander, et al.
Published: (2024)

Finding Order-Preserving Subgraphs
by: Imamura, Haruya, et al.
Published: (2025)

Forbidden Subgraph Problems with Predictions
by: Böckenhauer, Hans-Joachim, et al.
Published: (2025)

Scalable Temporal Motif Densest Subnetwork Discovery
by: Sarpe, Ilie, et al.
Published: (2024)

Counting Cohesive Subgraphs with Hereditary Properties
by: Li, Rong-Hua, et al.
Published: (2024)

Subexponential Parameterized Algorithms for Hitting Subgraphs
by: Lokshtanov, Daniel, et al.
Published: (2024)

Finding Small Complete Subgraphs Efficiently
by: Chen, Ke, et al.
Published: (2023)

Packing Compact Subgraphs with Applications to Districting
by: Chen, Ho-Lin, et al.
Published: (2026)

A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph and 2-Vertex-Connected Spanning Subgraph
by: Çivril, Ali
Published: (2023)

The Complexity Landscape of Dynamic Distributed Subgraph Finding
by: Chang, Yi-Jun, et al.
Published: (2024)

Accelerating Maximum Common Subgraph Computation by Exploiting Symmetries
by: Kothalawala, Buddhi, et al.
Published: (2026)

Dense Subgraph Discovery Meets Strong Triadic Closure
by: Arachchi, Chamalee Wickrama, et al.
Published: (2025)

Better Decremental and Fully Dynamic Sensitivity Oracles for Subgraph Connectivity
by: Long, Yaowei, et al.
Published: (2024)

Finding Induced Subgraphs from Graphs with Small Mim-Width
by: Otachi, Yota, et al.
Published: (2024)

$Δ$-Motif: Parallel Subgraph Isomorphism via Tabular Operations
by: Wang, Yulun, et al.
Published: (2025)

Changing Induced Subgraph Isomorphisms Under Extended Reconfiguration Rules
by: Suga, Tatsuhiro, et al.
Published: (2025)

A Fine-grained Classification of Subquadratic Patterns for Subgraph Listing and Friends
by: Bringmann, Karl, et al.
Published: (2024)