Cover Image

Density Matters: A Complexity Dichotomy of Deleting Edges to Bound Subgraph Density

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bentert, Matthias, Breitkopf, Tom-Lukas, Froese, Vincent, Herrmann, Anton, Nichterlein, André
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

The Parameterized Complexity Landscape of Two-Sets Cut-Uncut
by: Bentert, Matthias, et al.
Published: (2024)

Parameterized Complexity of s-Club Cluster Edge Deletion: When Is the Diameter Bound Necessary?
by: Gaikwad, Ajinkya
Published: (2025)

Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs
by: Paul-Pena, Daniel, et al.
Published: (2024)

When does FTP become FPT?
by: Bentert, Matthias, et al.
Published: (2025)

Fault-Tolerant Matroid Bases
by: Bentert, Matthias, et al.
Published: (2025)

A Dichotomy Theorem for Linear Time Homomorphism Orbit Counting in Bounded Degeneracy Graphs
by: Paul-Pena, Daniel, et al.
Published: (2022)

Vital Edges for (s,t)-mincut: Efficient Algorithms, Compact Structures, and Optimal Sensitivity Oracle
by: Baswana, Surender, et al.
Published: (2023)

DRESS and the WL Hierarchy: Climbing One Deletion at a Time
by: Velilla, Eduar Castrillo
Published: (2026)

Dichotomies for Maximum Matching Cut: $H$-Freeness, Bounded Diameter, Bounded Radius
by: Lucke, Felicia, et al.
Published: (2023)

When Distances Lie: Euclidean Embeddings in the Presence of Outliers and Distance Violations
by: Bentert, Matthias, et al.
Published: (2025)

A Dichotomy for Maximum PCSPs on Graphs
by: Nakajima, Tamio-Vesa, et al.
Published: (2024)

Isomorphism Testing for Graphs Excluding Small Topological Subgraphs
by: Neuen, Daniel
Published: (2020)

Cutwidth Bounds via Vertex Partitions
by: Amarilli, Antoine, et al.
Published: (2025)

Temporal Graph Realization With Bounded Stretch
by: Mertzios, George B., et al.
Published: (2025)

Nearly Tight Bounds on Testing of Metric Properties
by: Bao, Yiqiao, et al.
Published: (2024)

Optimal Padded Decomposition For Bounded Treewidth Graphs
by: Filtser, Arnold, et al.
Published: (2024)

Bounding $\varepsilon$-scatter dimension via metric sparsity
by: Bourneuf, Romain, et al.
Published: (2024)

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
by: Crane, Alex, et al.
Published: (2025)

1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
by: Ciardo, Lorenzo, et al.
Published: (2023)

Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates
by: Kaul, Matthias, et al.
Published: (2024)

Efficient Algorithms for Interdicting Facilities in Trees and Bounded Treewidth Graphs
by: Abbasi, Ali, et al.
Published: (2026)

Unsplittable Cost Flows from Unweighted Error-Bounded Variants
by: Swamy, Chaitanya, et al.
Published: (2025)

An efficient algorithm for $\mathcal{F}$-subgraph-free Edge Deletion on graphs having a product structure
by: An, Shinwoo, et al.
Published: (2025)

Maximizing a Submodular Function with Bounded Curvature under an Unknown Knapsack Constraint
by: Klimm, Max, et al.
Published: (2022)

Complexity of the (Connected) Cluster Vertex Deletion problem on $H$-free graphs
by: Le, Hoang-Oanh, et al.
Published: (2024)

Parameterized Complexity of Path Set Packing
by: Aravind, N. R., et al.
Published: (2022)

The Complexity of Diameter on H-free graphs
by: Oostveen, Jelle J., et al.
Published: (2024)

Deletion-correcting codes for an adversarial nanopore channel
by: Xie, Huiling, et al.
Published: (2026)

Strong Conflict-Free Vertex-Connection via Twin Cover: Kernelization and Chromatic Bounds
by: German, Samuel
Published: (2026)

Terminal Steiner tree problem : Complexity and Algorithms
by: S, Jyothish, et al.
Published: (2026)

Parameterized Complexity of Submodular Minimization under Uncertainty
by: Kakimura, Naonori, et al.
Published: (2024)

A Lower Bound on the Competitive Ratio of the Permutation Algorithm for Online Facility Assignment on a Line
by: Harada, Tsubasa
Published: (2024)

An $Ω(n \log n)$ Randomized Lower Bound for Cutting a Cake into Proportionally Fair Pieces
by: Arndt, Stephen, et al.
Published: (2026)

The Complexity of Temporal Vertex Cover in Small-Degree Graphs
by: Hamm, Thekla, et al.
Published: (2022)

Near-Optimal Constructive Bounds for $\ell_2$ Prefix Discrepancy and Steinitz Problems via Affine Spectral Independence
by: Dutta, Kunal, et al.
Published: (2026)

Maximum Biclique for Star 1,2,3 -free and Bounded Bimodularwidth Twin-free Bipartite Graphs $\star$
by: de Montgolfier, Fabien, et al.
Published: (2025)

Output-Sensitive Enumeration of Potential Maximal Cliques in Polynomial Space
by: Brosse, Caroline, et al.
Published: (2024)

Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack
by: Schade, Jamico, et al.
Published: (2023)

An Improved Bound for the Beck-Fiala Conjecture
by: Bansal, Nikhil, et al.
Published: (2025)