Parameterized Critical Node Cut Revisited

Knop, Dušan; Melissinos, Nikolaos; Vasilakis, Manolis

doi:10.4230/LIPIcs.SWAT.2026.25

Parameterized Critical Node Cut Revisited

Dušan Knop

Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Czech Republic Nikolaos Melissinos

Computer Science Institute, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic Manolis Vasilakis

Université Paris-Dauphine, PSL University, CNRS UMR7243, LAMSADE, Paris, France

Abstract

We study how to sparsify connectivity in graphs under a tight deletion budget. Given a graph $G$ and integers $k,x\geq 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+\mathrm{fes}+\Delta+\mathrm{pw}$ , where $\mathrm{fes}$ is the feedback edge set number, $\Delta$ the maximum degree, and $\mathrm{pw}$ the pathwidth of the input graph, respectively. This significantly improves over the known W[1]-hardness for $k+\mathrm{tw}$ , where $\mathrm{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 $\varepsilon>0$ , computes a $(1+\varepsilon)$ -approximate solution in time $(\mathrm{tw}/\varepsilon)^{\mathcal{O}(\mathrm{tw})}n^{\mathcal{O}(1)}$ . 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.

Keywords and phrases:

Critical Node Cut, Parameterized Complexity, Treewidth

Funding:

Dušan Knop: Supported by the European Union under the project Robotics and advanced industrial production (reg. no. CZ.02.01.01/00/22_008/0004590).

Nikolaos Melissinos: Partially supported by Charles University projects UNCE 24/SCI/008 and PRIMUS 24/SCI/012, and by the project 25-17221S of GAČR.

Manolis Vasilakis: Supported by the ANR project ANR-21-CE48-0022 (S-EX-AP-PE-AL) and the Barrande Fellowship programme.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Parameterized complexity and exact algorithms

Editor:

Pierre Fraigniaud

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Let $G$ be a simple, undirected, and unweighted graph, and let $k$ and $x$ be two non-negative integers. The Critical Node Cut problem (CNC for short) asks whether we can delete at most $k$ vertices from $G$ so that the remaining graph contains at most $x$ connected vertex pairs. This problem arises in various applications, such as budgeted immunization for contagion control, analyzing brain connectivity, and uncovering structures in social graphs (see [4, 13] and references therein).

Importantly, CNC generalizes the well-known Vertex Cover problem, which corresponds to the special case $x=0$ . Given its NP-hardness, we study CNC through the lens of parameterized complexity.¹¹1We assume familiarity with the basics of parameterized complexity, as given e.g. in [7]. Previous work has shown that the problem is fixed-parameter tractable (FPT) when parameterized by the vertex cover number of the input graph [22], but W[1]-hard when parameterized by the natural parameter $k$ or by the treewidth $\mathrm{tw}$ [13].²²2More strongly, the reduction in [13] implies W[1]-hardness with respect to tree-depth. As a matter of fact, Agrawal, Lokshtanov, and Mouawad have shown that this hardness persists even when parameterizing by the combined parameter $k+\mathrm{tw}$ [3].

Our Contribution.

Our first result, which constitutes our main technical contribution, is to significantly improve over the aforementioned hardness result of Agrawal, Lokshtanov, and Mouawad [3]. In particular, in Theorem 2 we prove that CNC remains W[1]-hard even when parameterized by the combined parameter $k+\mathrm{fes}+\Delta+\mathrm{pw}$ , where $\mathrm{fes}$ , $\Delta$ , and $\mathrm{pw}$ denote the feedback edge set number, the maximum degree, and the pathwidth of the input graph, respectively. Notice that this also implies that the problem is W[1]-hard when parameterized by $k+\mathrm{ctw}$ , where $\mathrm{ctw}$ denotes the cutwidth of the input graph, as for any graph it holds that $\mathrm{ctw}\leq\mathrm{pw}\cdot\Delta$ . In fact, this intractability result is tight in the sense that tree-depth together with maximum degree trivially yields FPT, since this parameterization bounds the graph size.³³3A graph of tree-depth $\mathrm{td}$ and maximum degree $\Delta$ has at most $\mathrm{td}\cdot\Delta^{\mathrm{td}}$ vertices. To obtain our result, we adapt a recent reduction for the related Vertex Integrity problem by Hanaka, Lampis, Vasilakis, and Yoshiwatari [12].

Moving on, we obtain several results concerning the tractability of the problem under different structural parameterizations. We identify three structural parameters that render CNC fixed-parameter tractable, thereby contrasting the hardness result above: max-leaf number (Theorem 8), vertex integrity (Theorem 9), and modular-width (Theorem 10). Our techniques towards obtaining those results include reductions to acyclic instances [12], $N$ -fold Integer Programming [17], and dynamic programming on suitable decompositions. We also consider the parameterization by clique-width $\mathrm{cw}$ , for which the problem is known to be W[1]-hard, and obtain an algorithm with running time $n^{{\cal O}(2^{\mathrm{cw}})}$ (Theorem 11), thus placing it in XP.

We then revisit the parameterization by treewidth and identify the bottleneck in standard dynamic programming as the need to track large numerical values. To address this, we apply a rounding technique introduced by Lampis [20], obtaining an FPT approximation scheme. Specifically, in Theorem 15 we give an algorithm that, for any $\varepsilon>0$ , computes in $(\mathrm{tw}/\varepsilon)^{{\cal O}(\mathrm{tw})}\cdot n^{{\cal O}(1)}$ time a deletion set of size at most $k$ such that the number of connected pairs in the resulting graph is at most $(1+\varepsilon)$ times the minimum possible.

Finally, we investigate the compressibility of CNC. We prove that, unless standard complexity assumptions fail, the problem does not admit a polynomial kernel when parameterized by the vertex cover number of the input graph (Theorem 16). This negative result highlights that even very restrictive structural parameterizations do not yield efficient preprocessing algorithms (under standard assumptions).

Related Work.

CNC is a well-studied problem; see [18, Section 5.2] and the references therein. Approximation algorithms have been proposed [24], while Hermelin, Kaspi, Komusiewicz, and Navon [13] initiated the problem’s study under parameterized complexity, presenting a plethora of both positive and negative results with respect to natural and structural parameterizations. Among others, they prove a (tight) $n^{o(k)}$ lower bound under the ETH, W[1]-hardness by tree-depth, and that the problem is FPT parameterized by $x+\mathrm{tw}$ . Polynomial-time algorithms are known for trees [23],⁴⁴4That is the case even for weighted variants of the problem. and more generally, the problem admits a DP algorithm of running time $n^{{\cal O}(\mathrm{tw})}$ [2]. As previously mentioned, CNC is known to be W[1]-hard parameterized by $k+\mathrm{tw}$ [3]. On the other hand, it admits FPT algorithms with single-exponential parametric dependence when parameterized by vertex cover number [22] or neighborhood diversity [21].

2 Preliminaries

Throughout the paper we use standard graph notations [8] and assume familiarity with the basic notions of parameterized complexity [7]. Proofs of statements marked with $(\bigstar)$ are presented in the full version of the paper.

We use $\mathbb{N}$ to denote the set of non-negative integers. For $x,y\in\mathbb{Z}$ , let $[x,y]=\{z\in\mathbb{Z}\mid x\leq z\leq y\}$ , while $[x]=[1,x]$ . For a set of integers $S\subseteq\mathbb{N}$ let $\binom{S}{c}$ denote the set of subsets of $S$ of size $c$ , i.e., $\binom{S}{c}=\{S^{\prime}\subseteq S:|S^{\prime}|=c\}$ . For a (multi)set of positive integers $S$ , let $\Sigma(S)$ denote the sum of its elements.

All graphs considered are undirected without loops. Given a graph $G$ , $\mathtt{cc}(G)$ denotes the set of its connected components, while $\mathrm{cp}(G)$ denotes the number of pairs of connected vertices in $G$ , that is, $\mathrm{cp}(G)=\sum_{C\in\mathtt{cc}(G)}\binom{|V(C)|}{2}$ . For a vertex $v\in V(G)$ , we denote the neighborhood of $v$ in $G$ by $N_{G}(v)$ . For a subset of vertices $S\subseteq V(G)$ , $G[S]$ denotes the subgraph induced by $S$ , while $G-S$ denotes $G[V(G)\setminus S]$ .

For the basics on tree decompositions we refer to [7, Section 7]. We define the height of a node of a tree decomposition as the distance from the root of the tree decomposition to said node. In that case, the height of a tree decomposition is defined as the maximum distance from the root to any of its nodes.

A graph of clique-width $k$ can be constructed through a sequence of the following operations on vertices that are labeled with at most $k$ different labels. We can use (1) introducing a single vertex $v$ of an arbitrary label $i$ , denoted $i(v)$ , (2) disjoint union of two labeled graphs, denoted $H_{1}\oplus H_{2}$ , (3) introducing edges between all pairs of vertices of two distinct labels $i$ and $j$ in a labeled graph $H$ , denoted $\eta_{i,j}(H)$ , and (4) changing the label of all vertices of a given label $i$ in a labeled graph $H$ to a different label $j$ , denoted $\rho_{i\to j}(H)$ . An expression describes a graph $G$ if $G$ is the final graph given by the expression (after we remove all the labels). The width of an expression is the number of different labels it uses. The clique-width of a graph is the minimum width of an expression describing it [6]. For a labeled graph $H$ and $v\in V(H)$ , let $\operatorname{lab}_{H}(v)$ denote the label of $v$ in $H$ , while $\operatorname{lab}^{-1}_{H}(i)=\{v\in V(H)\mid\operatorname{lab}_{H}(v)=i\}$ denotes the set of vertices of $H$ of label $i$ . A clique-width expression is irredundant if whenever the operation $\eta_{i,j}$ is applied on a graph $G$ , there is no edge between an $i$ -vertex and a $j$ -vertex in $G$ , and we will use such expressions to simplify our algorithms. We remark that any clique-width expression can be transformed in linear time into an irredundant one of the same width [6].

Instance:	A graph $G=(V,E)$ as well as integers $k$ and $x$ .
Goal:	Determine whether there exists a set $S\subseteq V$ with $\|S\|\leq k$ such that in $G-S$ there are at most $x$ pairs of connected vertices, that is, whether $\mathrm{cp}(G-S)\leq x$ .

Lemma 1 ( $\bigstar$ ).

Let $k\in\mathbb{N}$ . Assume we are given $n$ functions $f_{i}\colon[0,k]\to\mathbb{N}$ , where $i\in[n]$ , and define $f\colon[0,k]\to\mathbb{N}$ such that for all $k^{\prime}\in[0,k]$ ,

f(k^{\prime})=\min_{\genfrac{}{}{0.0pt}{}{k_{i}\in[0,k^{\prime}]}{k_{1}+\cdots% +k_{n}=k^{\prime}}}\sum_{i\in[n]}f_{i}(k_{i}).

One can compute the function $f$ in time ${\cal O}(nk^{2})$ .

3 W[1]-hardness

In this section we prove that Critical Node Cut is W[1]-hard when parameterized by the combined parameter $k+\mathrm{fes}+\Delta+\mathrm{pw}$ , where $\mathrm{fes}$ , $\Delta$ , and $\mathrm{pw}$ denote the feedback edge set number, the maximum degree, and the pathwidth of the input graph, respectively. This significantly improves over the previous result of Agrawal, Lokshtanov, and Mouawad [3] who showed that the problem is W[1]-hard parameterized by $k$ plus the treewidth of the input graph. Our reduction follows along the lines of a recent reduction by Hanaka et al. [12] who showed the W[1]-hardness of Semi-Weighted Component Order Connectivity under a similar parameterization. We reduce from the Restricted Unary Bin Packing problem, which we formally define below and which is known to be W[1]-hard parameterized by the number of bins $k$ [12].

Instance:	A multiset $A=\{a_{1},\ldots,a_{n}\}$ of integers in unary, $k\in\mathbb{N}$ , and a function $f\colon A\to\binom{[k]}{2}$ .
Goal:	Determine whether there is a partition of $A$ into multisets $\mathcal{A}_{1},\ldots,\mathcal{A}_{k}$ , such that for all $i\in[k]$ it holds that (i) $\Sigma(\mathcal{A}_{i})=\Sigma(A)/k$ , and (ii) $\forall a\in\mathcal{A}_{i}$ , $i\in f(a)$ .

We first present a sketch of our reduction. The weight of a vertex refers to the length of a path attached to it; this is later formalized in the construction. Similarly to the construction of Hanaka et al. [12], for every bin of the Restricted Unary Bin Packing problem instance we introduce a clique of ${\cal O}(k^{2})$ heavy vertices, and then connect any pair of such cliques via two paths. The weights are set in such a way that an optimal solution will delete only vertices from the connection paths. In order to construct a path for a pair of bins, we compute the set of all subset sums of the items that can be placed in these two bins, and introduce a vertex of medium weight per such subset sum. This step can be completed in polynomial time, as all items are in unary. Moreover, every such vertex corresponding to subset sum $s$ is preceded by exactly $s$ vertices of weight $1$ . An optimal solution will cut the path so that the number of vertices of weight $1$ will be partitioned between the two bins, encoding the subset sum of the elements placed in each bin. The second path that we introduce has balancing purposes, allowing us to exactly count the number of vertices of medium weight that every connected component will end up with. In the end, the intended solution deletes only vertices of medium weight, resulting in components of only two possible sizes.

Theorem 2.

Critical Node Cut is W[1]-hard parameterized by $k+\mathrm{fes}+\Delta+\mathrm{pw}$ .

Proof.

Let $(A,k,f)$ be an instance of Restricted Unary Bin Packing, where $A=\{a_{1},\ldots,a_{n}\}$ denotes the multiset of items given in unary, $k$ is the number of bins, and $f\colon A\to\binom{[k]}{2}$ dictates the pair of bins an item may be placed into. In the following let $B=\Sigma(A)/k$ , $c=6k^{2}$ , $M=kB+1$ , $L=36k^{4}BM$ , and $T=L+(k-1)\cdot 2BM+B$ . Notice that $M>kB$ and $L/c=6k^{2}BM$ . We will reduce $(A,k,f)$ to an equivalent instance $(G,k^{\prime},x)$ of Critical Node Cut, where $k^{\prime}=2\binom{k}{2}$ and $x=k\cdot\binom{T}{2}+2\binom{k}{2}\cdot\binom{M-1}{2}$ denote the size of the deletion set and the bound on the number of pairs of connected vertices, respectively.

We proceed to describe the construction of graph $G$ . For ease of presentation, when we say that a vertex $v\in V(G)$ has weight $w\geq 1$ , it means that we introduce a path on $w-1$ vertices and connect one of its endpoints to $v$ .

For every $i\in[k]$ , we introduce a clique on vertex set $\hat{C}_{i}$ , which is comprised of $c$ vertices, each of weight $L/c$ . Fix $i$ and $j$ such that $1\leq i<j\leq k$ , and let $H_{i,j}=\{a\in A\mid f(a)=\{i,j\}\}$ denote the multiset of all items of $A$ which can be placed either on bin $i$ or bin $j$ , where $\Sigma(H_{i,j})\leq 2B$ . Let $\mathcal{S}(H_{i,j})=\{\Sigma(H)\mid H\subseteq H_{i,j}\}$ denote the set⁵⁵5We stress that $\mathcal{S}(H_{i,j})$ is a set and not a multiset. of all subset sums of $H_{i,j}$ , and notice that since every element of $H_{i,j}$ is encoded in unary, $\mathcal{S}(H_{i,j})$ can be computed in polynomial time using, e.g., Bellman’s classical DP algorithm [5]. We next construct two paths connecting the vertices of $\hat{C}_{i}$ and $\hat{C}_{j}$ . First, we introduce the vertex set $\hat{U}_{i,j}=\{v^{i,j}_{q}\mid q\in[0,4B-|\mathcal{S}(H_{i,j})|+1]\}$ , all the vertices of which are of weight $M$ . Add edges $(v^{i,j}_{q},v^{i,j}_{q+1})$ for all $q\in[0,4B-|\mathcal{S}(H_{i,j})|]$ , as well as $(v_{1},v^{i,j}_{0})$ and $(v^{i,j}_{4B-|\mathcal{S}(H_{i,j})|+1},v_{2})$ , for all $v_{1}\in\hat{C}_{i}$ and $v_{2}\in\hat{C}_{j}$ . Next, we introduce the vertex set $\hat{D}_{i,j}=\{s^{i,j}_{q}\mid q\in[\Sigma(H_{i,j})]\}\cup\{\sigma^{i,j}_{q}% \mid q\in\mathcal{S}(H_{i,j})\}$ , with the $s$ -vertices being of weight $1$ and the $\sigma$ -vertices of weight $M$ . Then, add the following edges:

$\blacksquare$

$(v_{1},\sigma^{i,j}_{0})$ and $(\sigma^{i,j}_{\Sigma(H_{i,j})},v_{2})$ , for all $v_{1}\in\hat{C}_{i}$ and $v_{2}\in\hat{C}_{j}$ ,
$\blacksquare$

for $q\in\mathcal{S}(H_{i,j})$ , add the edges $(s^{i,j}_{q},\sigma^{i,j}_{q})$ if $q\neq 0$ and $(\sigma^{i,j}_{q},s^{i,j}_{q+1})$ if $q\neq\Sigma(H_{i,j})$ , and
$\blacksquare$

for $q\in[\Sigma(H_{i,j})]\setminus\mathcal{S}(H_{i,j})$ , add the edge $(s^{i,j}_{q},s^{i,j}_{q+1})$ .

Observe that if $H_{i,j}=\varnothing$ , then $\Sigma(H_{i,j})=0$ , $\mathcal{S}(H_{i,j})=\{0\}$ , and $|\mathcal{S}(H_{i,j})|=1$ , thus $\hat{U}_{i,j}$ consists of $4B+1$ vertices of weight $M$ , while $\hat{D}_{i,j}$ consists only of the single vertex $\sigma^{i,j}_{0}$ which is connected to the two cliques $\hat{C}_{i},\hat{C}_{j}$ .

This concludes the construction of $G$ . See Figure 1 for an illustration. Notice that the number of vertices of $G$ excluding those belonging to the cliques $\hat{C}_{1},\ldots,\hat{C}_{k}$ or to a path attached to them is $(4B+2)M\cdot\binom{k}{2}+kB<6k^{2}BM=L/c$ .

Figure 1: Rectangles denote cliques of size

c

. Here we assume that

1\leq i<j\leq k

,

1\notin\mathcal{S}(H_{i,j})

, and

2\in\mathcal{S}(H_{i,j})

. The gray and black colors indicate weight of

M

and

L/c

, respectively.

Lemma 3 ( $\bigstar$ ).

If $(A,k,f)$ is a Yes-instance of Restricted Unary Bin Packing, then $(G,k^{\prime},x)$ is a Yes-instance of Critical Node Cut.

Lemma 4.

If $(G,k^{\prime},x)$ is a Yes-instance of Critical Node Cut, then $(A,k,f)$ is a Yes-instance of Restricted Unary Bin Packing.

Proof.

Let $S\subseteq V(G)$ with $|S|\leq k^{\prime}=2\binom{k}{2}$ such that the number of pairs of connected vertices in $G-S$ is minimized and is at most $x$ . Notice that $|S|=k^{\prime}$ , as otherwise there always exists a vertex whose deletion reduces said number. For all $i\in[k]$ it holds that $|\hat{C}_{i}|>k^{\prime}$ , thus the vertices of $\hat{C}_{i}\setminus S$ belong to the same connected component of $G-S$ . Our aim is to argue that $S$ contains exactly one vertex of medium weight per path between cliques. Towards this goal, we first show the following series of Claims.

$\vartriangleright$ Claim 5.

For any $i,j\in[k]$ with $1\leq i<j\leq k$ it holds that $|S\cap\hat{U}_{i,j}|\leq 1$ and $|S\cap\hat{D}_{i,j}|\leq 1$ .

Proof.

For the sake of contradiction, assume there exist $i,j\in[k]$ with $1\leq i<j\leq k$ such that $|S\cap\hat{Z}_{i,j}|\geq 2$ , where $\hat{Z}_{i,j}\in\{\hat{U}_{i,j},\hat{D}_{i,j}\}$ . Let $v$ denote the rightmost vertex of $\hat{Z}_{i,j}$ that belongs to $S$ , that is, no vertex of $\hat{Z}_{i,j}$ between $v$ and the vertices of $\hat{C}_{j}$ belongs to $S$ . Let $\mathcal{C}_{j}$ denote the connected component of $G-S$ that contains the vertices of $\hat{C}_{j}$ . It holds that $|V(\mathcal{C}_{j})|\geq 2L/3$ , since $c\geq 3k^{\prime}$ . Let $v^{\prime}\in\hat{C}_{j}\setminus S$ and consider the deletion set $S^{\prime}=(S\setminus\{v\})\cup\{v^{\prime}\}$ , where $|S^{\prime}|=|S|$ .

Starting from $G-S$ it holds that not deleting $v$ increases the number of connected pairs by $Y_{1}\leq 4BM\cdot|V(\mathcal{C}_{j})|+4BM\cdot M=\frac{2L}{3k^{2}c}\cdot(|V(% \mathcal{C}_{j})|+M)$ , while subsequently deleting $v^{\prime}$ decreases the number of pairs by $Y_{2}\geq(|V(\mathcal{C}_{j})|-L/c)\cdot(L/c)$ . In that case, $\mathrm{cp}(G-S^{\prime})=\mathrm{cp}(G-S)+Y_{1}-Y_{2}$ . Recall that by the optimality of $S$ , $\mathrm{cp}(G-S)\leq\mathrm{cp}(G-S^{\prime})\iff Y_{2}\leq Y_{1}$ , implying that

	$\displaystyle(\|V(\mathcal{C}_{j})\|-L/c)\cdot(L/c)\leq\frac{2L}{3k^{2}c}\cdot(\|% V(\mathcal{C}_{j})\|+M)$	$\displaystyle\iff$
	$\displaystyle\|V(\mathcal{C}_{j})\|-L/c\leq\frac{2}{3k^{2}}\cdot(\|V(\mathcal{C}_% {j})\|+M)$	$\displaystyle\iff$
	$\displaystyle\|V(\mathcal{C}_{j})\|\left(1-\frac{2}{3k^{2}}\right)-L/c\leq\frac{% 2M}{3k^{2}}$	$\displaystyle\implies\qquad(\text{by }\frac{2M}{3k^{2}}<\frac{L}{c})$
	$\displaystyle\|V(\mathcal{C}_{j})\|\left(1-\frac{2}{3k^{2}}\right)-L/c<L/c$	$\displaystyle\implies\qquad(\text{by }\|V(\mathcal{C}_{j})\|\geq 2L/3)$
	$\displaystyle\frac{2L}{3}\cdot\left(1-\frac{2}{3k^{2}}\right)<\frac{2L}{6k^{2}}$	$\displaystyle\iff$
	$\displaystyle\left(1-\frac{2}{3k^{2}}\right)<\frac{1}{2k^{2}}$	$\displaystyle\iff$
	$\displaystyle 1\leq\frac{7}{6k^{2}},$

which, since $k\geq 2$ , leads to a contradiction. $\hfill\vartriangleleft$

We next argue that every connected component of $G-S$ contains vertices belonging to at most one clique $\hat{C}_{i}$ .

$\vartriangleright$ Claim 6.

For any connected component $\mathcal{C}$ of $G-S$ it holds that

|\{i\in[k]\mid V(\mathcal{C})\cap\hat{C}_{i}\neq\varnothing\}|\leq 1\,.

Proof.

We first fix some notation used throughout the proof. Let $\Pi\subseteq 2^{[k]}$ be the partition of $[k]$ such that $p\in\Pi$ if and only if there exists a connected component $\mathcal{C}_{p}\in\mathtt{cc}(G-S)$ with $p=\{i\in[k]\mid V(\mathcal{C}_{p})\cap\hat{C}_{i}\neq\varnothing\}$ . Notice that for $p\neq\varnothing$ , such a component is unique. For $p\in\Pi$ we further define the set $\hat{R}(p)$ which is composed of the vertices $\bigcup_{i\in p}\hat{C}_{i}\cup\bigcup_{i,j\in p}(\hat{U}_{i,j}\cup\hat{D}_{i,% j})$ plus the vertices belonging to the paths attached to the former vertices. Let $g\colon\mathtt{cc}(G-S)\to[0,k]$ such that $g(\mathcal{C})=|\{i\in[k]\mid V(\mathcal{C})\cap\hat{C}_{i}\neq\varnothing\}|$ for all $\mathcal{C}\in\mathtt{cc}(G-S)$ . Consider a component $\mathcal{C}_{p_{\max}}\in\mathtt{cc}(G-S)$ that maximizes $g$ , where $g(\mathcal{C}_{p_{\max}})=|p_{\max}|\geq 1$ . It suffices to prove that $|p_{\max}|<2$ . Towards a contradiction assume that $|p_{\max}|\geq 2$ .

Let $\mathcal{C}_{p^{\prime}}$ with $g(\mathcal{C}_{p^{\prime}})=|p^{\prime}|<|p_{\max}|$ . We argue that $S\cap\hat{R}(p^{\prime})=\varnothing$ . To see this, notice that the deletion of such a vertex results in at most

\frac{L}{c}\cdot\left(|p^{\prime}|\cdot L+\frac{L}{c}\right)

disconnected pairs, where we use the fact that the number of vertices of $G$ excluding those belonging to the cliques $\hat{C}_{1},\ldots,\hat{C}_{k}$ or to a path attached to them is less than $L/c$ . On the other hand, $|V(\mathcal{C}_{p_{\max}})|\geq|p_{\max}|\cdot L-k^{\prime}\cdot(L/c)\geq(|p_{% \max}|-1)\cdot L+(2L)/3$ , thus the deletion of a vertex $v\in\hat{C}_{i}\setminus S$ with $i\in p_{\max}$ results in at least

\frac{L}{c}\cdot\left((|p_{\max}|-1)\cdot L+\frac{2L}{3}\right)>\frac{L}{c}% \cdot\left(|p^{\prime}|\cdot L+\frac{L}{c}\right)

disconnected pairs.

The previous paragraph, along with Claim 5 and the fact that $|S|=2\binom{k}{2}$ , imply that there exists $p\in\Pi$ with $|p|=|p_{\max}|$ such that $|S\cap\hat{R}(p)|\geq 2\binom{|p|}{2}$ . Let $S^{\prime}=(S\setminus\hat{R}(p))\cup\{v^{i,j}_{0},\sigma^{i,j}_{0}\mid i,j\in p\}$ , where $|S^{\prime}|\leq|S|$ . We argue that $\mathrm{cp}(G-S^{\prime})<\mathrm{cp}(G-S)$ . Let $x_{1}$ (resp., $x_{2}$ ) denote the number of pairs of connected vertices in $G-S$ (resp., $G-S^{\prime}$ ) such that at least one vertex belongs to $\hat{R}(p)$ (notice that the rest of the pairs remain the same in the two graphs). It holds that

	$\displaystyle 2\cdot x_{1}$	$\displaystyle>2\cdot\binom{(\|p\|-1)\cdot L+2L/3}{2}$
		$\displaystyle\geq((\|p\|-1)L+2L/3)\cdot((\|p\|-1)L+L/3)$
		$\displaystyle=L^{2}(\|p\|^{2}-\|p\|+2/9),$

where the first inequality is due to the component of $G-S$ that contains the vertices of $\{\hat{C}_{i}\mid i\in p\}\setminus S$ . On the other hand, in $G-S^{\prime}$ the vertices of each $\hat{C}_{i}$ for $i\in p$ are in distinct connected components, thus it holds that

	$\displaystyle 2\cdot x_{2}$	$\displaystyle<2\|p\|\cdot\binom{L+L/c}{2}$
		$\displaystyle\leq\|p\|(L+L/c)^{2}$
		$\displaystyle=L^{2}\big(\|p\|+\|p\|\cdot\frac{2c+1}{c^{2}}\big)$
		$\displaystyle\leq L^{2}(\|p\|+2/9),$

where the first inequality is due to the fact that the number of vertices of $G$ apart from those of $\bigcup_{i\in[k]}\hat{C}_{i}$ or attached to them is at most $L/c$ . The last inequality is due to the fact that $|p|\cdot\frac{2c+1}{c^{2}}\leq k\cdot\frac{12k^{2}+1}{36k^{4}}$ , which for $k\geq 2$ is upper-bounded by $2/9$ .

Finally, we have that

	$\displaystyle x_{1}$	$\displaystyle>x_{2}\impliedby$
	$\displaystyle L^{2}(\|p\|^{2}-\|p\|+2/9)$	$\displaystyle\geq L^{2}(\|p\|+2/9)\iff$
	$\displaystyle\|p\|^{2}$	$\displaystyle\geq 2\|p\|,$

which holds as by assumption $|p|\geq 2$ . This contradicts the optimality of set $S$ . $\hfill\vartriangleleft$

By Claim 6 and the fact that $k^{\prime}=2\binom{k}{2}$ it follows that $S$ contains exactly one vertex per path between cliques. In that case, since the vertices of those paths are of weight $1$ or $M$ , regarding the connected components of $G-S$ it holds that there are exactly $k$ of size at least $L$ , as well as $a\in[\binom{k}{2},\,2\binom{k}{2}]$ of size exactly $M-1$ , where $a\geq\binom{k}{2}$ since half the paths between cliques contain only vertices of weight $M$ . Further notice that the number of pairs of connected vertices is minimized when each component of size at least $L$ contains $\frac{|V(G)|-a\cdot M}{k}$ vertices,⁶⁶6To see this notice that $\binom{n-\varepsilon}{2}+\binom{n+\varepsilon}{2}>2\cdot\binom{n}{2}$ for all $\varepsilon>0$ . while for all $a\leq 2\binom{k}{2}$ it holds that

k\cdot\binom{(|V(G)|-a\cdot M)/k}{2}+a\cdot\binom{M-1}{2}>k\cdot\binom{(|V(G)|% -(a+1)\cdot M)/k}{2}+(a+1)\cdot\binom{M-1}{2}.

Consequently, the minimum number of pairs of connected vertices is obtained exactly when there are $2\binom{k}{2}$ components in $G-S$ of size $M-1$ , and the rest of the vertices are partitioned equally among the remaining $k$ components. Notice that

	$\displaystyle\|V(G)\|$	$\displaystyle=k\cdot L+(4B+2)M\cdot\binom{k}{2}+kB$
		$\displaystyle=k\cdot(L+2BM(k-1)+B)+2M\cdot\binom{k}{2}$
		$\displaystyle=k\cdot T+2\binom{k}{2}\cdot M,$

thus since $x=k\cdot\binom{T}{2}+2\binom{k}{2}\cdot\binom{M-1}{2}$ it follows that this is indeed the case for $G-S$ . Consequently, for all $1\leq i<j\leq k$ , there exists $\sigma^{i,j}_{q}\in S$ with $q\in\mathcal{S}(H_{i,j})$ .

Let $\mathcal{C}_{i}$ denote the connected component of $G-S$ containing the vertices of $\hat{C}_{i}$ . Since $\mathcal{C}_{i}$ contains $T$ vertices, while $kB<M$ , it follows that $\mathcal{C}_{i}$ contains exactly $B$ vertices of weight $1$ . Let $(\mathcal{A}_{1},\ldots,\mathcal{A}_{k})$ be a partition of $A$ defined in the following way: for all $1\leq i<j\leq k$ , if $\sigma^{i,j}_{q}\in S$ , then $\mathcal{A}_{i}\cap H_{i,j}=\mathcal{H}_{i,j}$ and $\mathcal{A}_{j}\cap H_{i,j}=H_{i,j}\setminus\mathcal{H}_{i,j}$ , where $\mathcal{H}_{i,j}\subseteq H_{i,j}$ such that $\Sigma(\mathcal{H}_{i,j})=q$ . Notice that $\Sigma(\mathcal{A}_{i})$ is equal to the number of vertices of weight $1$ in $\mathcal{C}_{i}$ , therefore $\Sigma(\mathcal{A}_{i})=B$ follows. $\hfill\blacktriangleleft$

Lemma 7.

It holds that $\mathrm{fes}(G)={\cal O}(k^{5})$ , $\Delta(G)={\cal O}(k^{2})$ , and $\mathrm{pw}(G)={\cal O}(k^{3})$ .

Proof.

For the feedback edge set number, let $F\subseteq E(G)$ contain all edges between vertices of $\hat{C}_{i}$ , for all $i\in[k]$ , as well as all edges between such vertices and endpoints of paths $\hat{U}_{i,j}$ and $\hat{D}_{i,j}$ . Notice that

|F|=k\cdot\binom{c}{2}+4\binom{k}{2}\cdot c={\cal O}(k^{5}),

while the graph remaining after the deletion of the edges in $F$ is a caterpillar forest. For the pathwidth bound notice that $G-\bigcup_{i=1}^{k}\hat{C}_{i}$ is a caterpillar forest, thus $\mathrm{pw}(G)={\cal O}(k^{3})$ . Lastly, for the maximum degree notice that for all $v\in\bigcup_{i\in[k]}\hat{C}_{i}$ , $|N(v)|=c+2(k-1)={\cal O}(k^{2})$ . As for the vertices of $\hat{D}_{i,j}\cup\hat{U}_{i,j}$ , they are of degree at most $3$ , apart from the endpoints which are neighbors with all the vertices of a single clique, therefore of degree ${\cal O}(k^{2})$ . Any remaining vertex is of degree at most $2$ . $\hfill\blacktriangleleft$ Due to Lemmas 3, 4, and 7, Theorem 2 follows. $\hfill\blacktriangleleft$

4 Algorithms

In this section we identify several structural parameters that render Critical Node Cut fixed-parameter tractable, namely max-leaf number, vertex integrity, and modular-width. Furthermore, we show that the problem parameterized by clique-width belongs to XP.

4.1 Max-Leaf Number

Here we present a single-exponential algorithm for Critical Node Cut parameterized by the max-leaf number of the input graph.⁷⁷7The max-leaf number of a graph is the maximum number of leaves among all its spanning trees. This is a well-studied but very restricted parameter [9, 10, 19]. Note that this nicely complements the W[1]-hardness of the problem parameterized by $\mathrm{fes}+\Delta$ which follows by Theorem 2; graphs of max-leaf number at most $k$ are known to be a subdivision of a graph of at most ${\cal O}(k)$ vertices [16], thus their feedback edge set number and their maximum degree are bounded by a function of $k$ . As a matter of fact, the reduction of Theorem 2 produces a graph that, at first glance, appears to have bounded max-leaf number. The value of this parameter increases due to attaching long paths on the weighted vertices, and Theorem 8 implies that this increase is unavoidable, as the problem is FPT under this parameterization.

Our algorithm closely follows the one presented by Hanaka, Lampis, Vasilakis, and Yoshiwatari [12] for Vertex Integrity parameterized by max-leaf number. In particular, our first step is to contract any cycles, reducing the instance to a weighted forest on which some of the vertices are marked as undeletable. Then we apply a simple DP algorithm for trees in order to compute, for every connected component of the instance, the minimum number of pairs of connected vertices remaining after at most $b$ vertex deletions from said component, for all $b\in[0,k]$ . Having computed this for every component, applying Lemma 1 then allows us to determine the number of deletions per component such that the total number of connected pairs is minimized.

Theorem 8 ( $\bigstar$ ).

There is an algorithm that given any instance $\mathcal{I}=(G,k,x)$ of Critical Node Cut, decides $\mathcal{I}$ in time $2^{{\cal O}(\mathrm{ml})}n^{{\cal O}(1)}$ , where $\mathrm{ml}$ denotes the max-leaf number of $G$ .

4.2 Vertex Integrity

The vertex integrity of a graph $G=(V,E)$ , denoted $\mathrm{vi}(G)$ , is the minimum integer $k$ such that there is a vertex set $U\subseteq V$ with $|U|+\max_{C\in\mathtt{cc}(G-U)}|V(C)|\leq k$ , where $\mathtt{cc}(G-U)$ denotes the set of connected components of $G-U$ . Here we show that the parameterization by vertex integrity renders Critical Node Cut fixed-parameter tractable. Given the fact that the vertex integrity of a graph is upper-bounded by its vertex cover number, this improves over the known FPT algorithm parameterized by vertex cover number [22]. On the other hand, the vertex integrity of a graph is lower-bounded by its tree-depth, under which parameterization the problem remains W[1]-hard [13], so our result is in that sense tight.

Theorem 9 ( $\bigstar$ ).

There is an algorithm that, given any instance $\mathcal{I}=(G,k,x)$ of Critical Node Cut, decides $\mathcal{I}$ in time ${\mathrm{vi}}^{{\cal O}(\mathrm{vi}^{2})}n^{{\cal O}(1)}$ , where $\mathrm{vi}$ denotes the vertex integrity of $G$ .

4.3 Modular-width

All our previous results are concerned with sparse classes of graphs. Here we prove that Critical Node Cut is fixed-parameter tractable parameterized by the modular-width of the input graph, thus improving over the analogous result for neighborhood diversity [21].

Theorem 10 ( $\bigstar$ ).

There is an algorithm that, given any instance $\mathcal{I}=(G,k,x)$ of Critical Node Cut, decides $\mathcal{I}$ in time $2^{\mathrm{mw}}n^{{\cal O}(1)}$ , where $\mathrm{mw}$ denotes the modular-width of $G$ .

4.4 Clique-width

Theorem 2 implies that Critical Node Cut is W[1]-hard parameterized by clique-width. Here we show that for this parameterization, the problem belongs to XP. To obtain this result, we proceed by presenting a standard dynamic programming algorithm. On a high level, as we go over the clique-width expression of the input graph, we consider a partition of the connected components of our graph based on the labels appearing in their vertices. For every such partitioning, we keep track of both the total size as well as the total number of connected pairs of vertices for the connected components belonging to the partitioning. As we prove, this amount of information is sufficient in order to solve Critical Node Cut.

Theorem 11.

There is an algorithm that, given a graph $G$ along with an irredundant clique-width expression $\psi$ of $G$ of width $\mathrm{cw}$ , determines for all $k\in[0,n]$ the minimum value of $\mathrm{cp}(G-S)$ over all subsets $S\subseteq V(G)$ with $|S|=k$ , as well as the number of subsets achieving this minimum, in time $n^{{\cal O}(2^{\mathrm{cw}})}$ .

Proof.

Before describing our algorithm we start with some definitions and notations. Let $\mathcal{H}$ denote the set of all $\mathrm{cw}$ -labeled graphs generated by subexpressions of $\psi$ . Furthermore, let $\mathcal{L}=2^{[\mathrm{cw}]}\setminus\varnothing$ denote the set of all non-empty subsets of $[\mathrm{cw}]$ . We say that $\sigma=(\alpha,\beta)$ is a signature, where $\sigma$ is a tuple consisting of functions $\alpha,\beta\colon\mathcal{L}\to\mathbb{N}$ . Moreover, let $\Sigma$ denote the set of all possible signatures, where $|\Sigma|=n^{{\cal O}(2^{\mathrm{cw}})}$ . We say that the label set of a connected component of a labeled graph is the set of labels appearing in the component’s vertices. For $H\in\mathcal{H}$ and $L\in\mathcal{L}$ , let $\mathcal{C}^{L}_{H}\subseteq\mathtt{cc}(H)$ denote the set of connected components of $H$ with label set $L$ . Lastly, for $H\in\mathcal{H}$ , we define the function $\operatorname{sgn}_{H}\colon 2^{V(H)}\to\Sigma$ , such that for $S\subseteq V(H)$ , the $H$ -signature of $S$ is the tuple $\operatorname{sgn}_{H}(S)=\sigma=(\alpha,\beta)\in\Sigma$ , where for all $L\in\mathcal{L}$ it holds that

$\blacksquare$

$\alpha(L)$ is equal to the sum of the sizes of the connected components of $\mathcal{C}^{L}_{H-S}$ ,
$\blacksquare$

$\beta(L)$ is equal to the number of pairs of connected vertices belonging to connected components of $\mathcal{C}^{L}_{H-S}$ .

Our algorithm proceeds by dynamic programming along $\psi$ in a bottom-up fashion. In particular, for every $H\in\mathcal{H}$ it stores a table $\operatorname{DP}_{H}[\cdot,\cdot]$ where, as we show, for $k\in[0,n]$ and $\sigma\in\Sigma$ , $\operatorname{DP}_{H}[k,\sigma]$ is equal to the number of subsets of $V(H)$ of size $k$ and $H$ -signature $\sigma$ . We now proceed to describe how to populate the DP tables, as well as establish this invariant by induction.

Singleton $H=i(v)$ .

For $H=i(v)$ , notice that $\operatorname{lab}^{-1}_{H}(i)=\{v\}$ and $\operatorname{lab}^{-1}_{H}(w)=\varnothing$ for all $w\in[\mathrm{cw}]\setminus\{i\}$ . Consequently, for $k\in[0,n]$ and signature $\sigma=(\alpha,\beta)\in\Sigma$ we set

\operatorname{DP}_{H}[k,\sigma]=\begin{cases}1&\text{if $k=0$, $\alpha\equiv% \alpha_{0}[\{i\}\mapsto 1]$, and $\beta\equiv\beta_{0}$},\\ 1&\text{if $k=1$, $\alpha\equiv\alpha_{0}$, and $\beta\equiv\beta_{0}$},\\ 0&\text{otherwise},\end{cases}

(1)

where for all $L\in\mathcal{L}$ , $\alpha_{0}(L)=\beta_{0}(L)=0$ . By Equation 1 we can fill the table $\operatorname{DP}_{H}[\cdot,\cdot]$ in time $n^{{\cal O}(2^{\mathrm{cw}})}$ . Furthermore, notice that $2^{V(H)}=\{\varnothing,\{v\}\}$ and one can easily verify that the invariant holds.

Disjoint union, $H=H_{1}\oplus H_{2}$ .

We define a function $h\colon\Sigma\times\Sigma\to\Sigma$ such that, for $\sigma_{1}=(\alpha_{1},\beta_{1})$ and $\sigma_{2}=(\alpha_{2},\beta_{2})$ , $h(\sigma_{1},\sigma_{2})=\sigma=(\alpha,\beta)$ where for all $L\in\mathcal{L}$ it holds that

$\blacksquare$

$\alpha(L)=\alpha_{1}(L)+\alpha_{2}(L)$ ,
$\blacksquare$

$\beta(L)=\beta_{1}(L)+\beta_{2}(L)$ .

For a fixed size $k\in[0,n]$ and signature $\sigma\in\Sigma$ , we set the value of $\operatorname{DP}_{H}[k,\sigma]$ to be

\operatorname{DP}_{H}[k,\sigma]=\sum_{k_{1}+k_{2}=k}\,\sum_{(\sigma_{1},\sigma% _{2})\in h^{-1}(\sigma)}\operatorname{DP}_{H_{1}}[k_{1},\sigma_{1}]\cdot% \operatorname{DP}_{H_{2}}[k_{2},\sigma_{2}].

(2)

If $h^{-1}(\sigma)=\varnothing$ we set $\operatorname{DP}_{H}[k,\sigma]=0$ . Notice that computing $h^{-1}(\sigma)$ requires $n^{{\cal O}(2^{\mathrm{cw}})}$ time, thus by Equation 2 we can fill the table $\operatorname{DP}_{H}[\cdot,\cdot]$ in time $n^{{\cal O}(2^{\mathrm{cw}})}$ .

$\vartriangleright$ Claim 12.

Let $H=H_{1}\oplus H_{2}$ . Assume that for $H_{i}\in\{H_{1},H_{2}\}$ , $k\in[0,n]$ , and $\sigma\in\Sigma$ , $\operatorname{DP}_{H_{i}}[k,\sigma]$ is equal to the number of subsets of $V(H_{i})$ of size $k$ and $H_{i}$ -signature $\sigma$ . Then it holds that $\operatorname{DP}_{H}[k,\sigma]$ is equal to the number of subsets of $V(H)$ of size $k$ and $H$ -signature $\sigma$ .

Proof.

Observe that $V(H)=V(H_{1})\cup V(H_{2})$ and $E(H)=E(H_{1})\cup E(H_{2})$ . Thus, for every $S\subseteq V(H)$ , it holds that $S=S_{1}\cup S_{2}$ where $S_{i}=S\cap V(H_{i})$ for $i\in\{1,2\}$ . Furthermore, notice that the connected components of $H-S$ are exactly the connected components of $H_{1}-S_{1}$ and $H_{2}-S_{2}$ , each with the same label set. Consequently, for every $L\in\mathcal{L}$ it holds that

$\blacksquare$

$\alpha(L)=\alpha_{1}(L)+\alpha_{2}(L)$ ,
$\blacksquare$

$\beta(L)=\beta_{1}(L)+\beta_{2}(L)$ ,

where $\sigma=(\alpha,\beta)$ is the $H$ -signature of $S$ , and $\sigma_{i}=(\alpha_{i},\beta_{i})$ is the $H_{i}$ -signature of $S_{i}$ for $i\in\{1,2\}$ . This implies that $\sigma=h(\sigma_{1},\sigma_{2})$ . The claim follows by Equation 2 and by the fact that there are $\operatorname{DP}_{H_{1}}[k_{1},\sigma_{1}]$ ways to choose a subset of size $k_{1}$ with $H_{1}$ -signature $\sigma_{1}$ , and $\operatorname{DP}_{H_{2}}[k_{2},\sigma_{2}]$ ways to choose a subset of size $k_{2}$ with $H_{2}$ -signature $\sigma_{2}$ , for every pair $(\sigma_{1},\sigma_{2})\in h^{-1}(\sigma)$ and every pair $(k_{1},k_{2})$ such that $k=k_{1}+k_{2}$ . $\hfill\vartriangleleft$

Relabeling, $H=\rho_{i\to j}(H^{\prime})$ .

Observe that a connected component with label set $L\in\mathcal{L}$ in $H$ has label set either $L$ , $L\cup\{i\}$ , or $L\cup\{i\}\setminus\{j\}$ in $H^{\prime}$ . For each pair of distinct $i,j\in[\mathrm{cw}]$ we define a function $f_{i\to j}\colon\Sigma\to\Sigma$ such that, for $\sigma^{\prime}=(\alpha^{\prime},\beta^{\prime})$ , $f_{i\to j}(\sigma^{\prime})=\sigma=(\alpha,\beta)$ where for all $L\in\mathcal{L}$ it holds that

$\blacksquare$

if $i\in L$ , then $\alpha(L)=\beta(L)=0$ ,
$\blacksquare$

if $i,j\notin L$ , then $\alpha(L)=\alpha^{\prime}(L)$ and $\beta(L)=\beta^{\prime}(L)$ ,
$\blacksquare$
if $i\notin L$ and $j\in L$ , then it holds that
- –
  
  $\alpha(L)=\alpha^{\prime}(L)+\alpha^{\prime}(L\cup\{i\})+\alpha^{\prime}(L\cup% \{i\}\setminus\{j\})$ ,
- –
  
  $\beta(L)=\beta^{\prime}(L)+\beta^{\prime}(L\cup\{i\})+\beta^{\prime}(L\cup\{i% \}\setminus\{j\})$ .

For a fixed size $k\in[0,n]$ and signature $\sigma\in\Sigma$ , we set the value of $\operatorname{DP}_{H}[k,\sigma]$ to be

\operatorname{DP}_{H}[k,\sigma]=\sum_{\sigma^{\prime}\in f^{-1}_{i\to j}(% \sigma)}\operatorname{DP}_{H^{\prime}}[k,\sigma^{\prime}].

(3)

If $f^{-1}_{i\to j}(\sigma)=\varnothing$ we set $\operatorname{DP}_{H}[k,\sigma]=0$ . Notice that computing $f^{-1}_{i\to j}(\sigma)$ requires $n^{{\cal O}(2^{\mathrm{cw}})}$ time, thus by Equation 3 we can fill the table $\operatorname{DP}_{H}[\cdot,\cdot]$ in time $n^{{\cal O}(2^{\mathrm{cw}})}$ .

$\vartriangleright$ Claim 13.

Let $H=\rho_{i\to j}(H^{\prime})$ . Assume that for $k\in[0,n]$ and $\sigma\in\Sigma$ , $\operatorname{DP}_{H^{\prime}}[k,\sigma]$ is equal to the number of subsets of $V(H^{\prime})$ of size $k$ and $H^{\prime}$ -signature $\sigma$ . Then it holds that $\operatorname{DP}_{H}[k,\sigma]$ is equal to the number of subsets of $V(H)$ of size $k$ and $H$ -signature $\sigma$ .

Proof.

Observe that $V(H)=V(H^{\prime})$ and $E(H)=E(H^{\prime})$ . Furthermore, notice that for all $S\subseteq V(H)$ , the connected components of $H-S$ are exactly the connected components of $H^{\prime}-S$ , albeit with potentially different label sets. Let $S\subseteq V(H)$ such that $\operatorname{sgn}_{H}(S)=\sigma=(\alpha,\beta)$ and $\operatorname{sgn}_{H^{\prime}}(S)=\sigma^{\prime}=(\alpha^{\prime},\beta^{% \prime})$ . We argue that $f_{i\to j}(\sigma^{\prime})=\sigma$ . Given that each subset $S$ has a unique $H^{\prime}$ -signature, Equation 3 and the fact that there are $\operatorname{DP}_{H^{\prime}}[k,\sigma^{\prime}]$ ways to choose a subset of size $k$ with $H^{\prime}$ -signature $\sigma^{\prime}$ , this implies the claim.

Let $L\in\mathcal{L}$ . If $i\in L$ , then since $\operatorname{lab}^{-1}_{H}(i)=\varnothing$ , it holds that no connected component of $H-S$ has label set $L$ , thus $\alpha(L)=\beta(L)=0$ . If $i,j\notin L$ , then the connected components of $H-S$ with label set $L$ are exactly the connected components of $H^{\prime}-S$ with label set $L$ , thus $\alpha(L)=\alpha^{\prime}(L)$ and $\beta(L)=\beta^{\prime}(L)$ . Lastly, if $i\notin L$ and $j\in L$ , then the connected components of $H-S$ with label set $L$ are exactly the connected components of $H^{\prime}-S$ with label set $L$ , $L\cup\{i\}$ , and $L\cup\{i\}\setminus\{j\}$ . Thus, $\alpha(L)=\alpha^{\prime}(L)+\alpha^{\prime}(L\cup\{i\})+\alpha^{\prime}(L\cup% \{i\}\setminus\{j\})$ and $\beta(L)=\beta^{\prime}(L)+\beta^{\prime}(L\cup\{i\})+\beta^{\prime}(L\cup\{i% \}\setminus\{j\})$ . It follows that $f_{i\to j}(\sigma^{\prime})=\sigma$ , and this concludes the proof. $\hfill\vartriangleleft$

Joining labels with edges, $H=\eta_{i,j}(H^{\prime})$ .

For each pair of distinct $i,j\in[\mathrm{cw}]$ we define a function $g_{i,j}\colon\Sigma\to\Sigma$ as follows. Let for $\sigma^{\prime}=(\alpha^{\prime},\beta^{\prime})$ , $g_{i,j}(\sigma^{\prime})=\sigma=(\alpha,\beta)$ . We consider two cases. First, assume that either $\sum_{L\in\mathcal{L}_{i}}\alpha^{\prime}(L)=0$ or $\sum_{L\in\mathcal{L}_{j}}\alpha^{\prime}(L)=0$ , where for $z\in\{i,j\}$ , $\mathcal{L}_{z}=\{L\in\mathcal{L}\mid z\in L\}$ denotes the label sets containing label $z$ . In that case, we set $\sigma=\sigma^{\prime}$ . Otherwise, let $\mathcal{L}^{\sigma^{\prime}}_{i,j}=\{L\in\mathcal{L}\mid\{i,j\}\cap L\neq% \varnothing\text{ and }\alpha^{\prime}(L)\neq 0\}$ and $L^{\sigma^{\prime}}_{i,j}=\bigcup_{L\in\mathcal{L}^{\sigma^{\prime}}_{i,j}}L$ . For all $L\in\mathcal{L}$ we set the values of $\alpha(L)$ and $\beta(L)$ as follows:

$\blacksquare$

if $i,j\notin L$ , then $\alpha(L)=\alpha^{\prime}(L)$ and $\beta(L)=\beta^{\prime}(L)$ ,
$\blacksquare$

if $\{i,j\}\cap L\neq\varnothing$ and $L\neq L^{\sigma^{\prime}}_{i,j}$ , then $\alpha(L)=\beta(L)=0$ ,
$\blacksquare$

if $L=L^{\sigma^{\prime}}_{i,j}$ , then $\alpha(L)=\sum_{L\in\mathcal{L}^{\sigma^{\prime}}_{i,j}}\alpha^{\prime}(L)$ and $\beta(L)=\binom{\alpha(L)}{2}$ .

For a fixed size $k\in[0,n]$ and signature $\sigma\in\Sigma$ , we set the value of $\operatorname{DP}_{H}[k,\sigma]$ to be

\operatorname{DP}_{H}[k,\sigma]=\sum_{\sigma^{\prime}\in g^{-1}_{i,j}(\sigma)}% \operatorname{DP}_{H^{\prime}}[k,\sigma^{\prime}].

(4)

If $g^{-1}_{i,j}(\sigma)=\varnothing$ we set $\operatorname{DP}_{H}[k,\sigma]=0$ . Notice that computing $g^{-1}_{i,j}(\sigma)$ requires $n^{{\cal O}(2^{\mathrm{cw}})}$ time, thus by Equation 4 we can fill the table $\operatorname{DP}_{H}[\cdot,\cdot]$ in time $n^{{\cal O}(2^{\mathrm{cw}})}$ .

$\vartriangleright$ Claim 14.

Let $H=\eta_{i,j}(H^{\prime})$ . Assume that for $k\in[0,n]$ and $\sigma\in\Sigma$ , $\operatorname{DP}_{H^{\prime}}[k,\sigma]$ is equal to the number of subsets of $V(H^{\prime})$ of size $k$ and $H^{\prime}$ -signature $\sigma$ . Then it holds that $\operatorname{DP}_{H}[k,\sigma]$ is equal to the number of subsets of $V(H)$ of size $k$ and $H$ -signature $\sigma$ .

Proof.

Observe that $V(H)=V(H^{\prime})$ , each vertex has the same label in both $H$ and $H^{\prime}$ , and $E(H)=E(H^{\prime})\cup\{uv\mid u\in\operatorname{lab}^{-1}_{H^{\prime}}(i),v% \in\operatorname{lab}^{-1}_{H^{\prime}}(j)\}$ . Let $S\subseteq V(H)$ such that $\operatorname{sgn}_{H}(S)=\sigma=(\alpha,\beta)$ and $\operatorname{sgn}_{H^{\prime}}(S)=\sigma^{\prime}=(\alpha^{\prime},\beta^{% \prime})$ . We argue that $g_{i,j}(\sigma^{\prime})=\sigma$ . Given that each subset $S$ has a unique $H^{\prime}$ -signature, Equation 4 and the fact that there are $\operatorname{DP}_{H^{\prime}}[k,\sigma^{\prime}]$ ways to choose a subset of size $k$ with $H^{\prime}$ -signature $\sigma^{\prime}$ , this implies the claim. Let $L\in\mathcal{L}$ . We will consider multiple cases.

First, assume that either $\sum_{L\in\mathcal{L}_{i}}\alpha^{\prime}(L)=0$ or $\sum_{L\in\mathcal{L}_{j}}\alpha^{\prime}(L)=0$ , where for $z\in\{i,j\}$ , $\mathcal{L}_{z}=\{L\in\mathcal{L}\mid z\in L\}$ denotes the label sets containing label $z$ . In that case, it follows that either $\operatorname{lab}^{-1}_{H^{\prime}}(i)\subseteq S$ or $\operatorname{lab}^{-1}_{H^{\prime}}(j)\subseteq S$ . Consequently, no new edges are added in $H-S$ compared to $H^{\prime}-S$ , thus, for all $L\in\mathcal{L}$ , it holds that $\alpha(L)=\alpha^{\prime}(L)$ and $\beta(L)=\beta^{\prime}(L)$ , which implies that $\sigma=\sigma^{\prime}$ .

Alternatively it holds that $\sum_{L\in\mathcal{L}_{i}}\alpha^{\prime}(L)\neq 0$ and $\sum_{L\in\mathcal{L}_{j}}\alpha^{\prime}(L)\neq 0$ . If $i,j\notin L$ , then the connected components of $H-S$ with label set $L$ are exactly the connected components of $H^{\prime}-S$ with label set $L$ , thus $\alpha(L)=\alpha^{\prime}(L)$ and $\beta(L)=\beta^{\prime}(L)$ follow. To handle the remaining cases, we let $\mathcal{L}^{\sigma^{\prime}}_{i,j}=\{L\in\mathcal{L}\mid\{i,j\}\cap L\neq% \varnothing\text{ and }\alpha^{\prime}(L)\neq 0\}$ and $L^{\sigma^{\prime}}_{i,j}=\bigcup_{L\in\mathcal{L}^{\sigma^{\prime}}_{i,j}}L$ . Since there are vertices $u$ and $v$ in $H^{\prime}-S$ with labels $i$ and $j$ , respectively, it follows that in $H-S$ , all vertices of label $i$ and all vertices of label $j$ belong to the same connected component. Furthermore, the label set of that connected component is exactly $L^{\sigma^{\prime}}_{i,j}$ , as it contains all labels of connected components of $H^{\prime}-S$ with label set in $\mathcal{L}^{\sigma^{\prime}}_{i,j}$ . As for its size, it holds that $\alpha(L^{\sigma^{\prime}}_{i,j})=\sum_{L\in\mathcal{L}^{\sigma^{\prime}}_{i,j% }}\alpha^{\prime}(L)$ , from which we can infer the number of pairs of connected vertices $\beta(L^{\sigma^{\prime}}_{i,j})=\binom{\alpha(L^{\sigma^{\prime}}_{i,j})}{2}$ . For any other label set $L\in\mathcal{L}$ with $\{i,j\}\cap L\neq\varnothing$ and $L\neq L^{\sigma^{\prime}}_{i,j}$ , it holds that $\alpha(L)=\beta(L)=0$ as either (i) $\alpha^{\prime}(L)=\beta^{\prime}(L)=0$ , or (ii) the connected components of $\mathcal{C}^{L}_{H^{\prime}-S}$ are all connected in $H-S$ and are part of the single connected component of label set $L^{\sigma^{\prime}}_{i,j}$ in $H-S$ . It follows that $g_{i,j}(\sigma^{\prime})=\sigma$ , and this concludes the proof. $\hfill\vartriangleleft$ Correctness follows by induction and Claims 12, 13, and 14. As for the running time, notice that for every $H\in\mathcal{H}$ the table $\operatorname{DP}_{H}[\cdot,\cdot]$ is filled in time $n^{{\cal O}(2^{\mathrm{cw}})}$ . Since $|\mathcal{H}|=n^{{\cal O}(1)}$ , the overall running time of our algorithm is $n^{{\cal O}(2^{\mathrm{cw}})}$ . Finally, notice that for any $S\subseteq V(G)$ of size $k\in[0,n]$ and $G$ -signature $\sigma=(\alpha,\beta)$ , it holds that $\mathrm{cp}(G-S)=\sum_{L\in\mathcal{L}}\beta(L)$ . Consequently, by iterating over all signatures $\sigma\in\Sigma$ , we can determine the minimum value of $\mathrm{cp}(G-S)$ over all subsets $S\subseteq V(G)$ of size $k$ , as well as the number of such subsets achieving this minimum. This concludes the proof. $\hfill\blacktriangleleft$

5 FPT Approximation Scheme

Given the fact that, as evidenced by Theorem 2, Critical Node Cut remains W[1]-hard even under severe structural parameterizations, in this section we aim to bypass this computational hardness by adding approximation into the mix. In particular, we design an efficient FPT-AS for the parameterization by treewidth by modifying the standard $n^{{\cal O}(\mathrm{tw})}$ DP algorithm [2] and making use of a technique introduced by Lampis [20].

Theorem 15 ( $\bigstar$ ).

There is an algorithm which, for all $\varepsilon>0$ , when given as input a graph $G$ of treewidth $\mathrm{tw}$ returns in time $(\mathrm{tw}/\varepsilon)^{{\cal O}(\mathrm{tw})}n^{{\cal O}(1)}$ a set $S\subseteq V(G)$ of size at most $k$ such that $\mathrm{cp}(G-S)\leq(1+\varepsilon)\cdot\mathrm{cp}(G-S^{\prime})$ for all $S^{\prime}\subseteq V(G)$ of size $|S^{\prime}|\leq k$ , for all $k\leq n$ .

Proof sketch.

Here we describe the main idea behind our algorithm. On a high level, we aim to develop a DP which, while traversing the tree decomposition, keeps track of the sizes of any active components (those whose vertices intersect the bag), while for the rest of the components (i.e., the inactive ones) there exists a variable on which we account for their number of pairs of connected vertices. To this end, assuming that the exact size of an active component is $c$ , our DP stores a value $\hat{c}\leq(1+\varepsilon^{\prime})\cdot c$ where $\varepsilon^{\prime}$ is such that $\binom{\hat{c}}{2}\leq(1+\varepsilon)\cdot\binom{c}{2}$ . Notice that for this to hold, $c=1$ implies that $\hat{c}=1$ . Consequently, it suffices to present a dynamic program which correctly stores the size of any singleton active component, while for the rest of active components it allows for $(1+\varepsilon^{\prime})$ -approximate values on their sizes. In that case, the number of pairs of connected vertices accounted for every connected component is a $(1+\varepsilon)$ -approximation, and since we sum over those, the final value has a $(1+\varepsilon)$ -approximation ratio as well. Our algorithm is thus a DP that does exactly as required. $\hfill\blacktriangleleft$

6 Kernelization

Given that, as we have shown in Theorem 9, Critical Node Cut is FPT parameterized by the vertex integrity of the input graph, a natural question arising is whether one can develop a polynomial kernel under this parameterization. In this section we prove that this cannot be the case under standard assumptions, even for the much more restricted parameterization by vertex cover number.

Theorem 16.

Critical Node Cut does not admit a polynomial kernel when parameterized by the vertex cover number of the input graph, unless $\mathsf{NP}\subseteq\mathsf{coNP}/\mathsf{poly}$ .

Proof.

We present a polynomial parameter transformation reducing from $k$ -Multicolored Clique. In the latter, we are given a graph $G=(V,E)$ and a partition of $V$ into $k$ independent sets (also called color classes) $V_{1},\ldots,V_{k}$ , each of size $n$ , and we are asked to determine whether $G$ contains a $k$ -clique. It is known that $k$ -Multicolored Clique parameterized by $k\log n$ does not admit a polynomial kernel unless $\mathsf{NP}\subseteq\mathsf{coNP}/\mathsf{poly}$ [14].

Construction.

Consider an instance $(G,k)$ of $k$ -Multicolored Clique, where $V_{i}=\{v^{i}_{j}\mid j\in[n]\}$ for all $i\in[k]$ . By adding isolated vertices to the color classes if necessary, we may assume that $n$ is a power of two. For each color class $V_{i}$ , we assign to each of its vertices a unique (among the vertices of $V_{i}$ ) bit-string of length $\log n$ . For all $w\in[\log n]$ , let $b_{w}\colon V\to\{0,1\}$ denote the $w$ -th bit in the bit-string of $v^{i}_{j}\in V_{i}$ . Construct the graph $G^{\prime}$ as follows.

$\blacksquare$

We first introduce a clique on vertex set $K=\{g^{i,w}_{z}\mid i\in[k],\,w\in[\log n],\,z\in\{0,1\}\}$ , which we refer to as core vertices. We say that a core vertex $g^{i,w}_{z}$ corresponds to color class $i$ , with $K_{i}$ being composed of all core vertices corresponding to color class $i$ , for $i\in[k]$ . Furthermore, we say that a vertex $v\in V_{i}$ of $G$ is encoded by the vertices $\{g^{i,w}_{b_{w}(v)}\mid w\in[\log n]\}$ .
$\blacksquare$

Introduce a clique on the vertex set $C=\{c_{i}\mid i\in[k\log n+1]\}$ , and add edges such that every vertex of $C$ is adjacent to all the core vertices.
$\blacksquare$

For every edge $e=\{u_{1},u_{2}\}\in E(G)$ , where $u_{1}\in V_{i_{1}}$ and $u_{2}\in V_{i_{2}}$ , introduce an adjacency vertex $h_{e}$ which is adjacent to all vertices encoding its endpoints, that is, with vertices $g^{i_{1},w}_{b_{w}(u_{1})}$ and $g^{i_{2},w}_{b_{w}(u_{2})}$ for all $w\in[\log n]$ . Let $H_{i_{1},i_{2}}$ denote the set of all adjacency vertices due to edges in $G$ between vertices in $V_{i_{1}}$ and $V_{i_{2}}$ .
$\blacksquare$

For all $\{i_{1},i_{2}\}\in\binom{[k]}{2}$ (that is, for all pairs of different color classes), and for all $w_{1},w_{2}\in[\log n]$ and $z_{1},z_{2}\in\{0,1\}$ , introduce an independent set of size $A=|E|+1$ , each vertex of which is incident with $g^{i_{1},w_{1}}_{z_{1}}$ and $g^{i_{2},w_{2}}_{z_{2}}$ . We refer to the vertices added in this step of the construction as dummy vertices.

This concludes the construction of the graph $G^{\prime}$ . Notice that $G^{\prime}-(K\cup C)$ is an independent set, consequently the vertex cover number of $G^{\prime}$ is at most $3k\log n+1$ . We will show that $(G^{\prime},k^{\prime},x)$ is an equivalent instance of Critical Node Cut, where $k^{\prime}=k\log n$ and $x=\binom{|V(G^{\prime})|-k^{\prime}-\binom{k}{2}-A\binom{k}{2}\log^{2}n}{2}$ .

For the forward direction, consider a function $s\colon[k]\to[n]$ such that $\mathcal{V}=\{v^{i}_{s(i)}\mid i\in[k]\}$ is a $k$ -clique in $G$ . In that case, let $S=\{g^{i,w}_{b_{w}(v^{i}_{s(i)})}\mid i\in[k],\,w\in[\log n]\}$ be a set of size $k^{\prime}$ . We will prove that $G^{\prime}-S$ has at most $x$ pairs of connected vertices. First, notice that for every pair of core vertices belonging to $S$ that correspond to different color classes, their removal results in an independent set of dummy vertices of size $A$ in $G^{\prime}-S$ . Since there are $\binom{k}{2}\log^{2}n$ such pairs, $G^{\prime}-S$ contains $A\binom{k}{2}\log^{2}n$ isolated dummy vertices. Furthermore, we argue that the adjacency vertex of any edge in $G[\mathcal{V}]$ is isolated in $G^{\prime}-S$ . To see this, consider the adjacency vertex $h_{e}\in V(G^{\prime})$ where $e=\{v^{i_{1}}_{s(i_{1})},v^{i_{2}}_{s(i_{2})}\}\in E(G)$ . It holds that $N_{G^{\prime}}(h_{e})=\{g^{{i_{1}},w}_{b_{w}(v^{i_{1}}_{s(i_{1})})},\,g^{{i_{2% }},w}_{b_{w}(v^{i_{2}}_{s(i_{2})})}\mid w\in[\log n]\}\subseteq S$ , thus $h_{e}$ is indeed an isolated vertex in $G^{\prime}-S$ . Since $\mathcal{V}$ induces a $k$ -clique, there are $\binom{k}{2}$ such isolated adjacency vertices. Finally, $S$ itself is of size $k^{\prime}$ . Consequently, the number of pairs of connected vertices in $G^{\prime}-S$ is at most the number of pairs of non-isolated vertices in the graph, which is at most $\binom{|V(G^{\prime})|-A\binom{k}{2}\log^{2}n-\binom{k}{2}-k^{\prime}}{2}=x$ .

For the opposite direction, let $S\subseteq V(G^{\prime})$ be of size at most $k^{\prime}$ such that $G^{\prime}-S$ has at most $x$ pairs of connected vertices. Notice that $|C|>k^{\prime}$ , consequently there exists a vertex $c\in C\setminus S$ . Since $N_{G^{\prime}}(c)\supseteq K$ and $C$ is a clique, it follows that all vertices of $(K\cup C)\setminus S$ are in the same connected component of $G^{\prime}-S$ ; let this component be denoted by $D_{\mathsf{big}}\in\mathtt{cc}(G^{\prime}-S)$ . Furthermore, since for any vertex $v\in V(G^{\prime})\setminus(K\cup C)$ it holds that $N_{G^{\prime}}(v)\subseteq K$ , any such vertex either belongs to $D_{\mathsf{big}}$ or is isolated in $G^{\prime}-S$ .

$\vartriangleright$ Claim 17.

We have $|S\cap K_{i}|=\log n$ , for all $i\in[k]$ .

Proof.

To prove the claim we argue about the number of isolated dummy vertices in $G^{\prime}-S$ . First, notice that $(n-\varepsilon)(n+\varepsilon)=n^{2}-\varepsilon^{2}<n^{2}$ for all $\varepsilon>0$ . Consequently, the number of isolated dummy vertices in $G^{\prime}-S$ is maximized when $|S\cap K_{i}|=\log n$ for all $i\in[k]$ , in which case the number of isolated dummy vertices is $A\binom{k}{2}\log^{2}n$ .

Assume that the claim is false. In that case, the number of isolated dummy vertices in $G^{\prime}-S$ is at most $A\left(\binom{k}{2}\log^{2}n-1\right)$ ; any other dummy vertex in $G^{\prime}-S$ must belong to $D_{\mathsf{big}}$ , which also contains all vertices of $(K\cup C)\setminus S$ . Consequently, the size of $D_{\mathsf{big}}\in\mathtt{cc}(G^{\prime}-S)$ is at least $|V(G^{\prime})|-|E|-k^{\prime}-A\left(\binom{k}{2}\log^{2}n-1\right)$ . In that case

	$\displaystyle\|V(G^{\prime})\|-\|E\|-k^{\prime}-A\left(\binom{k}{2}\log^{2}n-1\right)$	$\displaystyle>\|V(G^{\prime})\|-A\binom{k}{2}\log^{2}n-\binom{k}{2}-k^{\prime}\iff$
	$\displaystyle-\|E\|+A$	$\displaystyle>-\binom{k}{2}\impliedby$
	$\displaystyle A$	$\displaystyle=\|E\|+1,$

thereby yielding a contradiction as $G^{\prime}-S$ has more than $x$ pairs of connected vertices. $\hfill\vartriangleleft$

Recall that $G^{\prime}-S$ is composed of a connected component $D_{\mathsf{big}}$ containing all non-isolated vertices, as well as some isolated vertices. By Claim 17 it holds that $|S|=k^{\prime}$ , thus for $G^{\prime}-S$ to have at most $x$ pairs of connected vertices the number of its isolated vertices must be at least $\binom{k}{2}+A\binom{k}{2}\log^{2}n$ . Due to Claim 17 it follows that it has exactly $A\binom{k}{2}\log^{2}n$ isolated dummy vertices, while none of the remaining vertices of $K\cup C$ can be isolated. Consequently, the deletion of $S$ isolates at least $\binom{k}{2}$ adjacency vertices.

We argue that no two isolated adjacency vertices $h_{e_{1}},h_{e_{2}}$ belong to the same set $H_{i_{1},i_{2}}$ . Assume that this is the case, and let $h_{e_{1}},h_{e_{2}}\in H_{i_{1},i_{2}}$ . For $u\in\{h_{e_{1}},h_{e_{2}}\}$ it holds that $|N_{G^{\prime}}(u)\cap K_{i_{1}}|=|N_{G^{\prime}}(u)\cap K_{i_{2}}|=\log n$ , while $N_{G^{\prime}}(h_{e_{1}})\neq N_{G^{\prime}}(h_{e_{2}})$ . Due to Claim 17, this leads to a contradiction. Consequently, there is exactly one isolated adjacency vertex in $G^{\prime}-S$ belonging to $H_{i_{1},i_{2}}$ for all $\{i_{1},i_{2}\}\in\binom{[k]}{2}$ .

Now consider one such isolated adjacency vertex $h_{e}\in H_{i_{1},i_{2}}$ . Notice that $|N_{G^{\prime}}(h_{e})\cap\{g^{p,w}_{0},g^{p,w}_{1}\}|=1$ for all $w\in[\log n]$ and $p\in\{i_{1},i_{2}\}$ . Since $S\supseteq N_{G^{\prime}}(h_{e})$ , and this holds for all isolated adjacency vertices, due to Claim 17 it follows that $|S\cap\{g^{i,w}_{0},g^{i,w}_{1}\}|=1$ for all $w\in[\log n]$ and $i\in[k]$ .

Let $s\colon[k]\to[n]$ such that $v^{i}_{s(i)}$ is encoded by the vertices $S\cap K_{i}$ , for all $i\in[k]$ . We claim that $\mathcal{V}=\{v^{i}_{s(i)}\mid i\in[k]\}$ induces a $k$ -clique in $G$ . Consider $\{i_{1},i_{2}\}\in\binom{[k]}{2}$ . Notice that there exists an isolated adjacency vertex $h_{e}$ in $G^{\prime}-S$ belonging to $H_{i_{1},i_{2}}$ ; the neighborhood of $h_{e}$ is exactly the vertices encoding its two endpoints in $G$ , thus $\{v^{i_{1}}_{s(i_{1})},v^{i_{2}}_{s(i_{2})}\}\in E(G)$ . $\hfill\blacktriangleleft$

7 Conclusion

In this paper we have thoroughly studied Critical Node Cut from the perspective of parameterized complexity, and presented a plethora of results, mostly taking into account the structure of the input graph. As a direction of future work, it is currently unknown whether the problem is FPT when parameterized by $k+\mathrm{td}$ , where $\mathrm{td}$ denotes the tree-depth of the input graph, or when parameterized by the cluster vertex deletion number of the input graph. Another interesting direction would be to (dis)prove the optimality of the $n^{{\cal O}(\mathrm{tw})}$ or the $n^{{\cal O}(2^{\mathrm{cw}})}$ algorithm; especially for the latter, we note that there are only a handful of natural problems for which such a running time is known to be optimal under the ETH [1, 11, 15]. Given the similarity of the construction of Theorem 2 and the algorithm of Theorem 8 with the corresponding results for Vertex Integrity [12], a natural question is whether we can obtain similar results for other optimization functions that take into account the sizes of the components of the graph remaining after the vertex deletions. Some of our results seem to be easily adaptable to such a more general setting (e.g., for general separately convex functions), however we do not know whether that is the case for the W[1]-hardness as well.

References

[1] Pierre Aboulker, Édouard Bonnet, Eun Jung Kim, and Florian Sikora. Grundy coloring and friends, half-graphs, bicliques. Algorithmica, 85(1):1–28, 2023. doi:10.1007/S00453-022-01001-2.
[2] Bernardetta Addis, Marco Di Summa, and Andrea Grosso. Identifying critical nodes in undirected graphs: Complexity results and polynomial algorithms for the case of bounded treewidth. Discret. Appl. Math., 161(16-17):2349–2360, 2013. doi:10.1016/J.DAM.2013.03.021.
[3] Akanksha Agrawal, Daniel Lokshtanov, and Amer E. Mouawad. Critical node cut parameterized by treewidth and solution size is W[1]-hard. In Graph-Theoretic Concepts in Computer Science - 43rd International Workshop, WG 2017, volume 10520 of Lecture Notes in Computer Science, pages 32–44. Springer, 2017. doi:10.1007/978-3-319-68705-6_3.
[4] Ashwin Arulselvan, Clayton W. Commander, Lily Elefteriadou, and Panos M. Pardalos. Detecting critical nodes in sparse graphs. Comput. Oper. Res., 36(7):2193–2200, 2009. doi:10.1016/J.COR.2008.08.016.
[5] Richard E. Bellman. Dynamic programming. Princeton University Press, Princeton, NJ, 1957.
[6] Bruno Courcelle and Stephan Olariu. Upper bounds to the clique width of graphs. Discret. Appl. Math., 101(1-3):77–114, 2000. doi:10.1016/S0166-218X(99)00184-5.
[7] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.
[8] Reinhard Diestel. Graph Theory, volume 173 of Graduate texts in mathematics. Springer, 2017. doi:10.1007/978-3-662-53622-3.
[9] Michael R. Fellows, Bart M. P. Jansen, and Frances A. Rosamond. Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity. Eur. J. Comb., 34(3):541–566, 2013. doi:10.1016/J.EJC.2012.04.008.
[10] Michael R. Fellows, Daniel Lokshtanov, Neeldhara Misra, Matthias Mnich, Frances A. Rosamond, and Saket Saurabh. The complexity ecology of parameters: An illustration using bounded max leaf number. Theory Comput. Syst., 45(4):822–848, 2009. doi:10.1007/S00224-009-9167-9.
[11] Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Clique-width III: Hamiltonian cycle and the odd case of graph coloring. ACM Trans. Algorithms, 15(1):9:1–9:27, 2019. doi:10.1145/3280824.
[12] Tesshu Hanaka, Michael Lampis, Manolis Vasilakis, and Kanae Yoshiwatari. Parameterized vertex integrity revisited. In 49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024, volume 306 of LIPIcs, pages 58:1–58:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.MFCS.2024.58.
[13] Danny Hermelin, Moshe Kaspi, Christian Komusiewicz, and Barak Navon. Parameterized complexity of critical node cuts. Theor. Comput. Sci., 651:62–75, 2016. doi:10.1016/J.TCS.2016.08.018.
[14] Danny Hermelin, Stefan Kratsch, Karolina Soltys, Magnus Wahlström, and Xi Wu. A completeness theory for polynomial (Turing) kernelization. Algorithmica, 71(3):702–730, 2015. doi:10.1007/S00453-014-9910-8.
[15] Lars Jaffke, Paloma T. Lima, and Daniel Lokshtanov. b-coloring parameterized by clique-width. Theory Comput. Syst., 68(4):1049–1081, 2024. doi:10.1007/S00224-023-10132-0.
[16] Daniel J. Kleitman and Douglas B. West. Spanning trees with many leaves. SIAM J. Discret. Math., 4(1):99–106, 1991. doi:10.1137/0404010.
[17] Martin Koutecký, Asaf Levin, and Shmuel Onn. A parameterized strongly polynomial algorithm for block structured integer programs. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 85:1–85:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPIcs.ICALP.2018.85.
[18] Mohammed Lalou, Mohammed Amin Tahraoui, and Hamamache Kheddouci. The critical node detection problem in networks: A survey. Comput. Sci. Rev., 28:92–117, 2018. doi:10.1016/J.COSREV.2018.02.002.
[19] Michael Lampis. Algorithmic meta-theorems for restrictions of treewidth. Algorithmica, 64(1):19–37, 2012. doi:10.1007/S00453-011-9554-X.
[20] Michael Lampis. Parameterized approximation schemes using graph widths. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, volume 8572 of Lecture Notes in Computer Science, pages 775–786. Springer, 2014. doi:10.1007/978-3-662-43948-7_64.
[21] Jannik Schestag. Critical node problem with vulnerable vertices. Master’s thesis, Philipps-Universität Marburg, 2021.
[22] Jannik Schestag, Niels Grüttemeier, Christian Komusiewicz, and Frank Sommer. On critical node problems with vulnerable vertices. J. Graph Algorithms Appl., 28(1):1–26, 2024. doi:10.7155/JGAA.V28I1.2922.
[23] Marco Di Summa, Andrea Grosso, and Marco Locatelli. Complexity of the critical node problem over trees. Comput. Oper. Res., 38(12):1766–1774, 2011. doi:10.1016/J.COR.2011.02.016.
[24] Mario Ventresca and Dionne M. Aleman. A derandomized approximation algorithm for the critical node detection problem. Comput. Oper. Res., 43:261–270, 2014. doi:10.1016/J.COR.2013.09.012.

[bib.bib1] [1] Pierre Aboulker, Édouard Bonnet, Eun Jung Kim, and Florian Sikora. Grundy coloring and friends, half-graphs, bicliques. Algorithmica, 85(1):1–28, 2023. doi:10.1007/S00453-022-01001-2.

[bib.bib2] [2] Bernardetta Addis, Marco Di Summa, and Andrea Grosso. Identifying critical nodes in undirected graphs: Complexity results and polynomial algorithms for the case of bounded treewidth. Discret. Appl. Math., 161(16-17):2349–2360, 2013. doi:10.1016/J.DAM.2013.03.021.

[bib.bib3] [3] Akanksha Agrawal, Daniel Lokshtanov, and Amer E. Mouawad. Critical node cut parameterized by treewidth and solution size is W[1]-hard. In Graph-Theoretic Concepts in Computer Science - 43rd International Workshop, WG 2017, volume 10520 of Lecture Notes in Computer Science, pages 32–44. Springer, 2017. doi:10.1007/978-3-319-68705-6_3.

[bib.bib4] [4] Ashwin Arulselvan, Clayton W. Commander, Lily Elefteriadou, and Panos M. Pardalos. Detecting critical nodes in sparse graphs. Comput. Oper. Res., 36(7):2193–2200, 2009. doi:10.1016/J.COR.2008.08.016.

[bib.bib5] [5] Richard E. Bellman. Dynamic programming. Princeton University Press, Princeton, NJ, 1957.

[bib.bib6] [6] Bruno Courcelle and Stephan Olariu. Upper bounds to the clique width of graphs. Discret. Appl. Math., 101(1-3):77–114, 2000. doi:10.1016/S0166-218X(99)00184-5.

[bib.bib7] [7] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.

[bib.bib8] [8] Reinhard Diestel. Graph Theory, volume 173 of Graduate texts in mathematics. Springer, 2017. doi:10.1007/978-3-662-53622-3.

[bib.bib9] [9] Michael R. Fellows, Bart M. P. Jansen, and Frances A. Rosamond. Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity. Eur. J. Comb., 34(3):541–566, 2013. doi:10.1016/J.EJC.2012.04.008.

[bib.bib10] [10] Michael R. Fellows, Daniel Lokshtanov, Neeldhara Misra, Matthias Mnich, Frances A. Rosamond, and Saket Saurabh. The complexity ecology of parameters: An illustration using bounded max leaf number. Theory Comput. Syst., 45(4):822–848, 2009. doi:10.1007/S00224-009-9167-9.

[bib.bib11] [11] Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Clique-width III: Hamiltonian cycle and the odd case of graph coloring. ACM Trans. Algorithms, 15(1):9:1–9:27, 2019. doi:10.1145/3280824.

[bib.bib12] [12] Tesshu Hanaka, Michael Lampis, Manolis Vasilakis, and Kanae Yoshiwatari. Parameterized vertex integrity revisited. In 49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024, volume 306 of LIPIcs, pages 58:1–58:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.MFCS.2024.58.

[bib.bib13] [13] Danny Hermelin, Moshe Kaspi, Christian Komusiewicz, and Barak Navon. Parameterized complexity of critical node cuts. Theor. Comput. Sci., 651:62–75, 2016. doi:10.1016/J.TCS.2016.08.018.

[bib.bib14] [14] Danny Hermelin, Stefan Kratsch, Karolina Soltys, Magnus Wahlström, and Xi Wu. A completeness theory for polynomial (Turing) kernelization. Algorithmica, 71(3):702–730, 2015. doi:10.1007/S00453-014-9910-8.

[bib.bib15] [15] Lars Jaffke, Paloma T. Lima, and Daniel Lokshtanov. b-coloring parameterized by clique-width. Theory Comput. Syst., 68(4):1049–1081, 2024. doi:10.1007/S00224-023-10132-0.

[bib.bib16] [16] Daniel J. Kleitman and Douglas B. West. Spanning trees with many leaves. SIAM J. Discret. Math., 4(1):99–106, 1991. doi:10.1137/0404010.

[bib.bib17] [17] Martin Koutecký, Asaf Levin, and Shmuel Onn. A parameterized strongly polynomial algorithm for block structured integer programs. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 85:1–85:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPIcs.ICALP.2018.85.

[bib.bib18] [18] Mohammed Lalou, Mohammed Amin Tahraoui, and Hamamache Kheddouci. The critical node detection problem in networks: A survey. Comput. Sci. Rev., 28:92–117, 2018. doi:10.1016/J.COSREV.2018.02.002.

[bib.bib19] [19] Michael Lampis. Algorithmic meta-theorems for restrictions of treewidth. Algorithmica, 64(1):19–37, 2012. doi:10.1007/S00453-011-9554-X.

[bib.bib20] [20] Michael Lampis. Parameterized approximation schemes using graph widths. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, volume 8572 of Lecture Notes in Computer Science, pages 775–786. Springer, 2014. doi:10.1007/978-3-662-43948-7_64.

[bib.bib21] [21] Jannik Schestag. Critical node problem with vulnerable vertices. Master’s thesis, Philipps-Universität Marburg, 2021.

[bib.bib22] [22] Jannik Schestag, Niels Grüttemeier, Christian Komusiewicz, and Frank Sommer. On critical node problems with vulnerable vertices. J. Graph Algorithms Appl., 28(1):1–26, 2024. doi:10.7155/JGAA.V28I1.2922.

[bib.bib23] [23] Marco Di Summa, Andrea Grosso, and Marco Locatelli. Complexity of the critical node problem over trees. Comput. Oper. Res., 38(12):1766–1774, 2011. doi:10.1016/J.COR.2011.02.016.

[bib.bib24] [24] Mario Ventresca and Dionne M. Aleman. A derandomized approximation algorithm for the critical node detection problem. Comput. Oper. Res., 43:261–270, 2014. doi:10.1016/J.COR.2013.09.012.

	$\displaystyle 2\cdot x_{1}$	$\displaystyle>2\cdot\binom{(\|p\|-1)\cdot L+2L/3}{2}$
		$\displaystyle\geq((\|p\|-1)L+2L/3)\cdot((\|p\|-1)L+L/3)$
		$\displaystyle=L^{2}(\|p\|^{2}-\|p\|+2/9),$

	$\displaystyle 2\cdot x_{2}$	$\displaystyle<2\|p\|\cdot\binom{L+L/c}{2}$
		$\displaystyle\leq\|p\|(L+L/c)^{2}$
		$\displaystyle=L^{2}\big(\|p\|+\|p\|\cdot\frac{2c+1}{c^{2}}\big)$
		$\displaystyle\leq L^{2}(\|p\|+2/9),$

	$\displaystyle x_{1}$	$\displaystyle>x_{2}\impliedby$
	$\displaystyle L^{2}(\|p\|^{2}-\|p\|+2/9)$	$\displaystyle\geq L^{2}(\|p\|+2/9)\iff$
	$\displaystyle\|p\|^{2}$	$\displaystyle\geq 2\|p\|,$

	$\displaystyle\|V(G^{\prime})\|-\|E\|-k^{\prime}-A\left(\binom{k}{2}\log^{2}n-1\right)$	$\displaystyle>\|V(G^{\prime})\|-A\binom{k}{2}\log^{2}n-\binom{k}{2}-k^{\prime}\iff$
	$\displaystyle-\|E\|+A$	$\displaystyle>-\binom{k}{2}\impliedby$
	$\displaystyle A$	$\displaystyle=\|E\|+1,$

Parameterized Critical Node Cut Revisited

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editor:

Series and Publisher:

1 Introduction

Our Contribution.

Related Work.

2 Preliminaries

Lemma 1 (★).

3 W[1]-hardness

Theorem 2.

Proof.

Lemma 3 (★).

Lemma 4.

Proof.

⊳ Claim 5.

Proof.

⊳ Claim 6.

Proof.

Lemma 7.

Proof.

4 Algorithms

4.1 Max-Leaf Number

Theorem 8 (★).

4.2 Vertex Integrity

Theorem 9 (★).

4.3 Modular-width

Theorem 10 (★).

4.4 Clique-width

Theorem 11.

Proof.

Singleton 𝑯=𝒊⁢(𝒗).

Disjoint union, 𝑯=𝑯𝟏⊕𝑯𝟐.

⊳ Claim 12.

Proof.

Relabeling, 𝑯=𝝆𝒊→𝒋⁢(𝑯′).

⊳ Claim 13.

Proof.

Joining labels with edges, 𝑯=𝜼𝒊,𝒋⁢(𝑯′).

⊳ Claim 14.

Proof.

5 FPT Approximation Scheme

Theorem 15 (★).

Proof sketch.

6 Kernelization

Theorem 16.

Proof.

Construction.

⊳ Claim 17.

Proof.

7 Conclusion

References

Lemma 1 ( $\bigstar$ ).

Lemma 3 ( $\bigstar$ ).

$\vartriangleright$ Claim 5.

$\vartriangleright$ Claim 6.

Theorem 8 ( $\bigstar$ ).

Theorem 9 ( $\bigstar$ ).

Theorem 10 ( $\bigstar$ ).

Singleton $H=i(v)$ .

Disjoint union, $H=H_{1}\oplus H_{2}$ .

$\vartriangleright$ Claim 12.

Relabeling, $H=\rho_{i\to j}(H^{\prime})$ .

$\vartriangleright$ Claim 13.

Joining labels with edges, $H=\eta_{i,j}(H^{\prime})$ .

$\vartriangleright$ Claim 14.

Theorem 15 ( $\bigstar$ ).

$\vartriangleright$ Claim 17.