2025/06/29 by Dušan Knop, Knop, Dušan, Nikolaos Melissinos +3 · 1 voice
Computer Science · Physics and Astronomy · #Advanced Graph Theory Research #Complex Network Analysis Techniques #Complexity and Algorithms in Graphs #cs.CC #cs.DS
paper · pdf · doi:10.4230/lipics.swat.2026.25
openalex publication_date 2025/06/29 · arxiv published 2025/06/29 · openalex created_date 2025/10/10 · arxiv updated 2026/02/16 · openalex updated_date 2026/07/28
We study how to sparsify connectivity in graphs under a tight deletion budget. Given a graph G and integers k,x ≥ 0, Critical Node Cut (CNC) asks whether we can delete at most k vertices so that the number of remaining unordered pairs of connected vertices is at most x. CNC generalizes Vertex Cover (the case x=0) and models tasks in network design, epidemiology, and social network analysis. We comprehensively map the structural parameterized complexity landscape for Critical Node Cut. First, we prove W[1]-hardness for the combined parameter k + fes + Δ+ pw, where fes is the feedback edge set number, Δ the maximum degree, and pw the pathwidth of the input graph respectively. This significantly improves over the known W[1]-hardness for k+tw, where tw denotes the treewidth, and is tight in that tree-depth together with maximum degree trivially yields FPT. Second, we give new positive results. Specifically, we identify three structural parameters--max-leaf number, vertex integrity, and modular-width--that render the problem fixed-parameter tractable, and develop a polynomial-time algorithm for graphs of constant clique-width. Third, leveraging a technique introduced by Lampis~[ICALP '14], we develop an FPT approximation scheme that, for any ε > 0, computes a (1+ε)-approximate solution in time (tw / ε)O(tw) nO(1), where tw denotes the treewidth of the input graph. Finally, we show that CNC admits no polynomial kernel when parameterized by vertex cover number, unless standard assumptions fail. Together, these results substantially sharpen the known complexity landscape for CNC.