Pierre Hosteins
email: pierre.hosteins@ifsttar.fr

Rosario Scatamacchia

Andrea Grosso

Roberto Aringhieri

The Connected Critical Node Problem

Keywords: Critical Node Problem, Complexity, Dynamic Programming, Treewidth, trees, seriesparallel graphs, K-way Vertex Cut Problem

The Critical Node Problem is a well-known optimization problem that aims to find the subset of nodes in a graph whose removal impacts the graph connectivity as much as possible according to a specific connectivity measure. In this work, we study a new version of the Critical Node Problem, which we call the Connected Critical Node Problem, where the set of the removed nodes has to form a connected subgraph. We consider three connectivity measures and provide complexity results and solution approaches for general graphs and specific classes of graphs such as graphs with bounded treewidth, trees and series-parallel graphs. We consider the Connected Critical Node Problem where the pairwise connectivity (related to the number of pairs of vertices still connected in the graph) is minimized. We prove that this problem is strongly NP-hard and inapproximable on general graphs and is polynomial-time solvable on graphs with bounded treewidth and with unit connection costs. Further, we prove the NP-hardness of the problem with arbitrary connection costs over trees and series-parallel graphs and derive dynamic programming algorithms. We extend our results to the problem variants that consider the minimization of the largest connected component and the maximization of the number of connected components (also called K-way Vertex Cut Problem). As side results, we provide new complexity results for the classic Critical Node Problem on series-parallel graphs.

Introduction

The Critical Node Problem (CNP) belongs to the family of Network Interdiction Problems [START_REF] Smith | Modern network interdiction problems and algorithms[END_REF] and aims at maximally fragmenting a graph by deleting a subset of its nodes (and all incident edges on such nodes) according to a specific connectivity measure. Considerable attention has been centered on this problem in the literature due to its numerous applications, including the identification of key players in a social network [START_REF] Borgatti | Identifying sets of key players in a network[END_REF], transportation networks vulnerability [START_REF] Jenelius | Importance and exposure in road network vulnerability analysis[END_REF], power grid construction and vulnerability [START_REF] Salmerón | Analysis of electric grid security under terrorist threat[END_REF], homeland security [START_REF] Brown | Defending critical infrastructure[END_REF], telecommunications [START_REF] Alevras | Capacity and survivability models for telecommunication networks[END_REF] or epidemic control [START_REF] Zhou | Epidemic dynamics on complex networks[END_REF] and immunisation strategies [START_REF] Arulselvan | Detecting critical nodes in sparse graphs[END_REF][START_REF] Cohen | Efficient immunization strategies for computer networks and populations[END_REF][START_REF] Ventresca | Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem[END_REF].

Different connectivity measures can be considered according to specific applications of interest and this choice typically leads to different optimal solution sets, as shown in [START_REF] Aringhieri | A general Evolutionary Framework for different classes of Critical Node Problems[END_REF][START_REF] Shen | Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs[END_REF][START_REF] Veremyev | An integer programming framework for critical elements detection in graphs[END_REF]. The connectivity measures considered in the literature are often linked to the number of maximal connected components, their maximum cardinality or the overall number of node pairs connected by a path (the so called pairwise connectivity) [START_REF] Arulselvan | Detecting critical nodes in sparse graphs[END_REF][START_REF] Arulselvan | Cardinality-constrained critical node detection problem[END_REF][START_REF] Dinh | On approximation of new optimization methods for assessing network vulnerability[END_REF][START_REF] Shen | Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs[END_REF][START_REF] Shen | Exact interdiction models and algorithms for disconnecting networks via node deletions[END_REF]. At the current state of the art, many heuristic algorithms have been proposed for these problems [START_REF] Addis | Hybrid Constructive Heuristics for the Critical Node Problem[END_REF][START_REF] Aringhieri | A general Evolutionary Framework for different classes of Critical Node Problems[END_REF][START_REF] Aringhieri | Local Search Metaheuristics for the Critical Node Problem[END_REF][START_REF] Pullan | Heuristic identification of critical nodes in sparse real-world graphs[END_REF][START_REF] Purevsuren | Heuristic algorithm for identifying critical nodes in graphs[END_REF][START_REF] Ventresca | Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem[END_REF][START_REF] Ventresca | Efficiently identifying critical nodes in large complex networks[END_REF]. We refer to [START_REF] Aringhieri | A general Evolutionary Framework for different classes of Critical Node Problems[END_REF][START_REF] Veremyev | An integer programming framework for critical elements detection in graphs[END_REF] for a comprehensive literature review of problems involving the main graph fragmentation metrics and to [START_REF] Lalou | The critical node detection problem in networks: A survey[END_REF] for a recent and general survey of the CNP. Other alternative ways to quantify the fragmentation of a graph also exist, such as: the network's diameter [START_REF] Albert | Error and attack tolerance of complex networks[END_REF], single/multiple-commodity maximum flow or the shortest path between given source-sink node pairs [START_REF] Grubesic | Vital nodes, interconnected infrastructures, and the geographies of network survivability[END_REF][START_REF] Lim | Algorithms for discrete and continuous multicommodity flow network interdiction problems[END_REF][START_REF] Matisziw | Modeling s-t path availability to support disaster vulnerability assessment of network infrastructure[END_REF][START_REF] Wood | Deterministic network interdiction[END_REF] or functions of the shortest paths lengths between pairs of nodes [START_REF] Aringhieri | Polynomial and pseudo-polynomial time algorithms for different classes of the Distance Critical Node Problem[END_REF][START_REF] Veremyev | Critical nodes for distance-based connectivity and related problems in graphs[END_REF].

Two recent works consider versions of the CNP where the set of critical nodes has a specific structure. The work of [START_REF] Granata | Network interdiction via a critical disruption path: Branch-and-price algorithms[END_REF] focus on finding a Critical Path, i.e. a set of critical nodes that creates a path in the graph between a source node and a sink node. The study of Walteros et al [START_REF] Walteros | Detecting critical node structures on graphs: A mathematical programming approach[END_REF] considers sets of critical nodes that are either cliques or stars. The additional constraints on the set of deleted nodes make the CNP more tailored to specific applications of interest (such as, e.g., surveillance paths). Following this interesting trend, in this work we consider a variation of the CNP where the set of critical nodes has to be a connected subgraph. We denote this problem as the Connected CNP. The connectivity requirement can reflect many practical situations further motivating the study of such a CNP variant. In general terms, the Connected CNP finds applications when the nodes could be deleted only through diffusive processes that progressively remove the nodes in the graph or alternatively when the CNP is considered as a conquest problem where some resources in a graph (e.g. nodes) are taken by a player who wants to have connected resources for implementing appropriate defensive strategies. We mention below some specific application examples associated with the Connected CNP:

• The work of [START_REF] Granata | Network interdiction via a critical disruption path: Branch-and-price algorithms[END_REF] focuses on surveillance applications where drones or patrols aim to intercept movements in a geographical area represented by a graph. Here the goal is to select paths for the drones constituted by the most critical nodes that connect a source node and a sink node in a graph. We can extend the analysis to situations where the surveillance patrol is allowed to move back and forward to explore relevant parts of a given area, defining a connected subgraph without a specific topology. Such an extension can be highly reasonable also for disaster relief applications.

• The study of influential processes in social networks has attracted a lot of attention in the recent years, see, e.g., [START_REF] Bapat | Safe sets, network majority on weighted trees[END_REF][START_REF] Dinh | On the approximability of positive influence dominating set in social networks[END_REF][START_REF] Fujita | Safe set problem on graphs[END_REF][START_REF] Lin | An ilp based memetic algorithm for finding minimum positive influence dominating sets in social networks[END_REF]. A social network can be typically represented by a graph where the nodes are people of the social network and each edge represents a friendship between two people. When one would like to spread an opinion or information in a social network, it is important to identify a community of people having a large impact on the network in terms of connectivity. At the same time, such a community must be convinced to spread the information.

To this aim, in practice, it is usually easier to obtain the consensus of individuals if their friends have already been convinced, giving a more stable community for the spreading process (as also addressed in some recent versions of network domination problems). In these contexts, we can consider the Connected CNP so as to identify a connected and robust community that can partition the social network into small connected components which cannot communicate except through the critical set of selected people.

Let us formally recall the CNP. Consider an undirected graph G = (V, E) with a set of vertices V and a set of edges E. We denote by n = |V | the number of vertices and by m = |E| the number of edges. We denote by c ij the connection cost between two nodes i ∈ V and j ∈ V in the graph, by k i the deletion cost associated with the deletion of node i ∈ V , by S the set of deleted nodes (critical set) and by G[V \ S] the graph induced by the set V \ S. Considering a budget K on the overall deletion costs, the classic CNP based on pairwise connectivity, thereafter called Pairwise CNP, can be formulated as follows:

min

S⊆V i<j {c ij : i, j are connected in G[V \ S]} (1)
i∈S

k i ≤ K (2)
This CNP variant was proven to be strongly NP-hard on general graphs in [START_REF] Arulselvan | Detecting critical nodes in sparse graphs[END_REF][START_REF] Addis | Removing critical nodes from a graph: complexity results and polynomial algorithms for the case of bounded treewidth[END_REF]. A negative approximation result (under P = N P ) is also given in [START_REF] Addis | Removing critical nodes from a graph: complexity results and polynomial algorithms for the case of bounded treewidth[END_REF], i.e., there does not exist a polynomial time approximation algorithm for the CNP.

The Pairwise CNP has also been studied over specially structured graphs. A class of graphs strongly investigated is the class of trees T = (V, E), often solved by Dynamic Programming (DP). In [START_REF] Di Summa | Complexity of the critical node problem over trees[END_REF], it has been shown that the Pairwise CNP on trees with unit connection costs, namely when c ij = 1 for all (i, j), is polynomially solvable (even with non-unit node deletion costs k i ) while the case with non-unit connection costs remains strongly NP-hard. Further results are provided in [START_REF] Addis | Removing critical nodes from a graph: complexity results and polynomial algorithms for the case of bounded treewidth[END_REF] where it is shown that the Pairwise CNP with unit connection costs is polynomially solvable on graphs with bounded treewidth. Polynomial and Pseudo-polynomial algorithms are provided in [START_REF] Aringhieri | Polynomial and pseudo-polynomial time algorithms for different classes of the Distance Critical Node Problem[END_REF] for the Pairwise CNP over trees with non-unit but specific connection costs. Additional results on specially structured graphs with different types of objective functions have been provided in the works of [START_REF] Aringhieri | Polynomial and pseudo-polynomial time algorithms for different classes of the Distance Critical Node Problem[END_REF][START_REF] Lalou | Component-cardinality-constrained critical node problem in graphs[END_REF][START_REF] Shen | Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs[END_REF]. A stochastic version of the problem over trees is studied in [START_REF] Hosteins | The Stochastic Critical Node Problem over trees[END_REF].

Another popular version of the CNP focuses on the minimization of the weight of the heaviest component (or its cardinality in case of unit node weights) instead of the pairwise connectivity, see, e.g., [START_REF] Addis | Removing critical nodes from a graph: complexity results and polynomial algorithms for the case of bounded treewidth[END_REF][START_REF] Aringhieri | A general Evolutionary Framework for different classes of Critical Node Problems[END_REF][START_REF] Arulselvan | Cardinality-constrained critical node detection problem[END_REF][START_REF] Shen | Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs[END_REF][START_REF] Shen | Exact interdiction models and algorithms for disconnecting networks via node deletions[END_REF][START_REF] Veremyev | An integer programming framework for critical elements detection in graphs[END_REF]. This problem is sometimes called MinMaxC CNP. It is characterised by node deletion costs k i as well as node weights c i for all nodes i ∈ V . We define c(H) as the total weight of the nodes inside a subset of nodes H ⊆ V and comp(G[V \ S]) as the set of maximally connected components of the graph induced by V \ S. The objective function of the MinMaxC CNP is written as follows:

min S⊆V max{c(H) : H ∈ comp(G[V \ S])} (3)
As observed in [START_REF] Shen | Exact interdiction models and algorithms for disconnecting networks via node deletions[END_REF], this version of the CNP is strongly NP-hard on general graphs with unit node weights.

Finally, the third version of the CNP considers the maximisation of the number of connected components after the deletion of a subset of nodes S. The objective function of this problem, denoted in [START_REF] Shen | Exact interdiction models and algorithms for disconnecting networks via node deletions[END_REF] as the MaxNum CNP, is:

max S⊆V |comp(G[V \ S])| (4)
This problem is also known in the literature as the K-Way Vertex Cut Problem (K-WVCP) and has been tackled, among others, in [START_REF] Addis | Removing critical nodes from a graph: complexity results and polynomial algorithms for the case of bounded treewidth[END_REF][START_REF] Aringhieri | A general Evolutionary Framework for different classes of Critical Node Problems[END_REF][START_REF] Berger | Complexity and approximability of the k-way vertex cut[END_REF][START_REF] Shen | Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs[END_REF][START_REF] Shen | Exact interdiction models and algorithms for disconnecting networks via node deletions[END_REF]. It is shown to be strongly NP-complete with unit deletion costs on general graphs in [START_REF] Shen | Exact interdiction models and algorithms for disconnecting networks via node deletions[END_REF] by a reduction from the Independent Set Problem.

In this work, we introduce the connected version of the CNP and study the problem with the three objective functions indicated above. Our contributions are summarised as follows:

• We prove that the Connected CNP is strongly NP-hard, even on biconnected planar bipartite graphs, for all three objective functions. We also prove that the Connected CNP based on pairwise connectivity cannot be approximated by a constant factor in polynomial time.

• For the Connected Pairwise CNP with unit connection costs, we derive a DP algorithm over the nice tree decomposition of a graph and show that the algorithm is polynomial when the treewidth of the graph is bounded by a constant. We extend the proposed algorithm to the other objective functions as well.

• We prove that the Connected Pairwise CNP with arbitrary costs is NP-hard on trees and seriesparallel graphs, and polynomial-time solvable on paths. We also provide efficient DP algorithms over trees for different input configurations and illustrate the corresponding differences in the complexity results between the Connected Pairwise CNP and the classic Pairwise CNP. We perform a similar analysis for the Connected MinMaxC CNP and the Connected MaxNum CNP.

• As side results, we prove the NP-hardness of the classic Pairwise CNP and the MinMaxC CNP over series-parallel graphs with arbitrary connection costs and arbitrary node weights, respectively, which were still open problems.

The paper is organised as follows. We first prove the strong NP-hardness and inapproximability of the Connected CNP over biconnected planar bipartite graphs in Section 2. We then describe a DP algorithm to solve some problem variants over nice tree decompositions of a general graph in Section 3 and show that the algorithm is polynomial when the treewidth of the graph is bounded by a constant. The proof of correctness of the algorithm is reported in Appendix A. We provide algorithms and complexity results over trees in Section 4 and series-parallel graphs in Section 5. For the sake of exposition, we only present the results for the Connected Pairwise CNP in the main body of the paper. Extensions of our results to Connected CNP versions based on the weight of the heaviest connected component and on the number of connected components are presented in Appendices B and C, respectively. Section 6 draws some conclusions.

NP-hardness and inapproximability on biconnected planar bipartite graphs

We derive complexity results for the decision version of the Connected CNP by considering the existing results for the Connected Minimum Vertex Cover problem. The decision version of the Connected CNP asks whether there exists a solution with an objective function not worse than a given threshold value. We prove the NP-completeness of the problem for the three objective functions considered in the paper in biconnected planar bipartite graphs of maximum degree 4.

Proposition 1:

The decision version of the Connected Pairwise CNP is strongly NP-complete in biconnected planar bipartite graphs of maximum degree 4, even with unit connection costs and unit deletion costs.

Proof. As already noticed in the literature [START_REF] Addis | Removing critical nodes from a graph: complexity results and polynomial algorithms for the case of bounded treewidth[END_REF], the Pairwise CNP with unit costs generalises the Minimum Vertex Cover problem on a given graph G. In fact, a solution of the Pairwise CNP has zero objective function (i.e., induces a disconnected subgraph) if and only if the same solution is a vertex cover of G with cardinality bounded by K (< n). Since the MinCVC, where the vertex cover constitutes a connected subgraph, has been shown to be NP-complete in biconnected planar bipartite graphs of maximum degree 4 in [START_REF] Escoffier | Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs[END_REF], we can infer that the Connected Pairwise CNP with unit costs is also NP-complete in such graphs. Moreover, since the MinCVC tackled in [START_REF] Escoffier | Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs[END_REF] is not a number problem (all data parameters are equal to one), a pseudo-polynomial algorithm for the Connected Pairwise CNP would solve the MinCVC in polynomial time. Clearly this is not possible under P = N P , implying the NP-Completeness in the strong sense of the Connected Pairwise CNP with unit costs.

The NP-completeness results for the Connected MinMaxC CNP and the Connected MaxNum CNP are reported in Appendices B and C. Employing an argument similar to the reasoning in [START_REF] Addis | Removing critical nodes from a graph: complexity results and polynomial algorithms for the case of bounded treewidth[END_REF], we also prove the following result:

Proposition 2: The Connected Pairwise CNP does not admit a polynomial time approximation algorithm with a bounded approximation ratio unless P = NP, even in biconnected planar bipartite graphs of maximum degree 4 with unit connection costs and unit deletion costs.

Proof. Consider an instance of the Connected Pairwise CNP over biconnected planar bipartite graphs of maximum degree 4, with unit connection and deletion costs and a budget capacity K. Deciding whether there exists a solution set S inducing a zero pairwise connectivity in G[V \ S] corresponds to finding a connected vertex cover S in G with a size smaller than (or equal to ) K, i.e. |S|≤ K.

At the same time, deciding whether a connected vertex cover with a size not larger than K exists in biconnected planar bipartite graphs of maximum degree 4 is NP-complete. A polynomial time approximation algorithm with a bounded approximation ratio for the Connected Pairwise CNP would allow us to decide the connected vertex cover in polynomial time by just checking if its approximate solution has a strictly positive objective function. Clearly this is impossible under P = NP.

3 The Connected CNP over graphs with bounded treewidth

In this section we provide a DP algorithm over any nice tree decomposition of a graph. In particular, we extend the algorithmic framework proposed in [START_REF] Addis | Removing critical nodes from a graph: complexity results and polynomial algorithms for the case of bounded treewidth[END_REF] for the classic Pairwise CNP in order to handle the additional requirement of having a connected critical set. In our solution approach, we explicitly keep track of the number of connected components in the partial solutions of the critical set S during the steps of the algorithm and combine these solutions in polynomial time to eventually compute an optimal critical set with a single connected component. We start considering the Connected Pairwise CNP with unit connection costs (c ij = 1 for each pair i, j ∈ V ) and arbitrary deletion costs. Our results are then extended to the other objective functions considered in the previous section (see Appendices B and C).

Notations and definitions

Notation. Let V (G) and E(G) denote the node set and the edge set of an undirected graph G respectively; {u, v} denotes an undirected edge, that is an element of E(G); N (v) = {u: {u, v} ∈ E} is the set of neighbours of a node v. For any graph H, let comp(H) be the set of connected components of H; for any set I ⊂ V (H) we denote by G[I] the subgraph induced by I. We also denote the number of connected node pairs in graph H as

#conn(H) = |V ( Ĥ)| 2 : Ĥ ∈ comp(H) .
Tree decomposition. A tree decomposition of a connected graph G is a rooted tree T with node set V (T ) whose elements X i ∈ V (T ) are called bags and are subsets of V (G), satisfying the following properties:

(i) {X: X ∈ V (T )} = V (G); (ii) {u, v} ∈ E(G) =⇒ ∃X ∈ V (T ): u, v ∈ X; (iii) If P is the unique path in T linking two bags X i , X j u ∈ X i , u ∈ X j =⇒ u ∈ X k for all X k ∈ P .
In general, a graph can have many tree decompositions. The width of the tree decomposition T is max{|X|: X ∈ V (T )} -1; the treewidth of G is the minimum possible width of a tree decomposition of G. Although finding the treewidth of a general graph is an NP-hard problem [START_REF] Arnborg | Complexity of finding embeddings in a k-tree[END_REF], it is possible to construct (if it exists) a tree decomposition of width τ ≤ κ in linear time, for any constant κ [START_REF] Bodlaender | A linear-time algorithm for finding tree-decompositions of small treewidth[END_REF].

The union of a bag X i with all its descendant bags in T is denoted V i . A nice tree decomposition for graph G is a tree decomposition where, in addition to properties (i)-(iii) listed above, each bag falls in one of the following cases:

• a leaf (or start) bag X i has no child and

|X i | = 1; • a join bag X i has two child bags X i ,X i such that X i = X i = X i ;
• a forget bag X i has a single child X j such that X i = X j \ {v} for some v ∈ V (G);

• an introduce bag X i has a single child X j such that X i = X j ∪ {v} for some v ∈ V (G).

A nice tree decomposition with width τ can be obtained from any given tree decomposition with width τ in polynomial time, with an O(τ n) number of bags, see, e.g., [START_REF] Kloks | Treewidth: Computations and Approximations[END_REF]. Finally, we recall two well-known and useful properties of a nice tree decomposition: (a) for an introduce with bag X i = X j ∪ {v} with child X j , all neighbours of v in V i are included in X j ; (b) for a join bag X i with two children X i and X i , the intersection between V i \ X i and V i \ X i is empty and there is no edge between a node in V i \ X i and a node in V i \ X i .

Connected components configurations

In order to tackle the Connected Pairwise CNP with unit connection costs over a nice tree decomposition of a graph, we consider a specific structure from [START_REF] Addis | Removing critical nodes from a graph: complexity results and polynomial algorithms for the case of bounded treewidth[END_REF] called connected component configuration (CCC for short). Given a graph G and a set Σ ⊆ V (G), the CCC of Σ in G is the set of pairs

α = {(Σ ∩ V (H), |V (H) \ Σ|): H ∈ comp(G), Σ ∩ V (H) = ∅}.
The number |V (H) \ Σ| represents the number of nodes of a component H not appearing in Σ. We stress that only the components of G which have a non-trivial intersection with Σ are listed in the CCC. A collection α = {(A i , a i )} k i=1 of subset-number pairs where the A i 's are a partition of Σ ⊆ V (G) and k i=1 a i ≤ |V (G)| is called a potential CCC, meaning that it may or may not be a CCC of Σ in G. We denote by Γ(Σ, r) the set of all possible potential CCCs of Σ such that k i=1 a i ≤ r. We say that a potential CCC α is realisable if there exists a subset S such that Σ ⊆ S ⊆ V (G) and α is the CCC of Σ in G[S]. In such a case, we call G[S] a realisation of α.

We use the concept of CCC to capture the structure of the critical set S and its complement V i \ S inside a given bag X i . In the dynamic programming algorithm presented in the next section, the set Σ will represent the intersection of X i with a partial critical set S ⊆ V i . This allows us to keep track of the variation in the number of connected components in G[S] and in the pairwise connectivity in G[V i \ S] when a node is added to or removed from a bag (for introduce and forget bags).

We will employ in the dynamic program the following operations on CCCs, taken from [START_REF] Addis | Removing critical nodes from a graph: complexity results and polynomial algorithms for the case of bounded treewidth[END_REF], to process forget, introduce and join bags, respectively. Let k = |α| be the number of pairs in a potential CCC α.

Restriction. Given α = {(A i , a i )} k i=1 ∈ Γ(Σ, r) and v ∈ Σ, we define α -v = {(A i \ {v}, a i + |A i ∩ {v}|): i = 1, . . . , k s.t. |A i \ {v}| > 0}.
Hence, the operation α -v induces a potential CCC ∈ Γ(Σ \ {v}, r) where the node v is removed from the corresponding set A i in α. If v is the only node in the set, then the associated pair (A i , a i ) is disregarded.

Extension. Given α = {(A i , a i )} k i=1 ∈ Γ(Σ, r), v ∈ Σ and L = {i : A i ∩ N (v) = ∅}, we define α + v = {(A i , a i ) : i = 1, . . . , k s.t. i / ∈ L} ∪ {v} ∪ i∈L A i , i∈L a i .
The operation α + v induces a potential CCC ∈ Γ(Σ ∪ {v}, r) where the node v is (possibly) merged with the sets A i in α containing at least one neighbour of v.

Sum. For α = {(A i , a i )} k i=1 ∈ Γ(Σ, r) and α = {(A i , a i )} k i=1 ∈ Γ(Σ, r), we define the sum CCC α = α + α as α = {(A i , a i )} k i=1 such that • u, v appear in the same A if u, v appear in the same A i of α or A i of α ; • a = A i ⊆A a i + A i ⊆A a i .
The following lemmas allow us to consistently restrict, extend and sum CCCs over a nice tree decomposition.

Lemma 1 (Lemma 9 in [START_REF] Addis | Removing critical nodes from a graph: complexity results and polynomial algorithms for the case of bounded treewidth[END_REF]). Consider a bag X j in a nice tree decomposition T and Σ ⊂ X j , and suppose there exists

S such that Σ ⊆ S ⊆ V j \ (X j \ Σ) and α is the CCC of Σ in G[S]: (a) For a forget bag X i = X j \ {v} with child X j , α -v is the CCC of Σ \ {v} in G[S], and Σ \ {v} ⊆ S ⊆ V i \ (X i \ Σ). (b) For an introduce bag X i = X j ∪{v} with child X j , α+v is the CCC of Σ = Σ∪{v} in Ŝ = S ∪{v}, and Σ ⊆ Ŝ ⊆ V i \ (X i \ Σ).
Lemma 2 (Lemma 10 in [START_REF] Addis | Removing critical nodes from a graph: complexity results and polynomial algorithms for the case of bounded treewidth[END_REF]). Let X i be a join bag of T with children X i and X i and let Σ ⊆ X i = X i = X i . Suppose there exist S and S such that

Σ ⊆ S ⊆ V i , Σ ⊆ S ⊆ V i . If α , α are CCCs of Σ in G[S ], G[S ], then α = α + α is the CCC of Σ in G[S ∪ S ].

Dynamic programming

We consider a nice tree decomposition of G with bags {X i } and perform a recursion from the leaves to the root node of the tree decomposition by properly combining the partial solutions obtained in each bag of the tree. Given a bag X i ∈ T , let Σ be the intersection of a partial critical set S ⊆ V i with X i . The corresponding complementary sets are Σ = X i \ Σ and S = V i \ S. Therefore, S represents the remaining nodes in V i after the removal of the critical set S, and the pairwise connectivity of G[V i ] is thus given by the residual graph G[ S] . We consider in the DP algorithm CCCs that refer to both (Σ, S) (as described above with a CCC α) and Σ, S. In particular, for a potential CCC

β ∈ Γ( Σ, |V i \ X i |), we consider a realisation G[ S] of β, i.e. such that β = {( Σ ∩ V (H), |V (H) \ Σ|): H ∈ comp(G[ S]), Σ ∩ V (H) = ∅}.
Similarly to the previous notations for α, we adopt the general notation

β = {(B i , b i )} i=1...k .
The following definition will represent the number of connected pairs (i.e., the pairwise connectivity) of the components in G[ S] that have at least one node in Σ:

β def = (B i ,b i )∈β |B i | + b i 2 .
For each bag X i , we define f i (Σ, α, β, π, p) as the minimum sum of the deletion costs of nodes in S, denoted as k(S), where S is such that

(i) S ∪ S is a partition of V i , Σ ⊆ S ⊆ V i \ Σ, Σ ⊆ S ⊆ V i \ Σ, (ii) G[S] is a realisation of α, |comp(G[S])|= p, (iii) G[ S] is a realisation of β, #conn(G[ S]) = π.
Let Π i (Σ, α, β, π, p) be the above optimisation problem.

Optimal value. The optimal value is recovered by reading the states

f 1 (Σ, α, β, π, p) with f 1 ≤ K, α = {(A 1 , a 1 )} or α = ∅ with π ≤ |V |
2 , p = 1 and selecting the state with π as small as possible. Note that requiring p = 1 forces the deleted set to be connected since there is only one connected component inside S. We also remark that an optimal solution can be easily recovered from the DP entries by implementing a backtracking procedure. We iteratively compute the f i values by going from the leaves up to the root bag X 1 through the following recursions. For the ease of exposition, we provide the proof of correctness of the recursions in Appendix A.

Start bag.

A start bag is a singleton X i = {v}. We have

f i (Σ, α, β, π, p) =      k v if Σ = {v}, α = {({v}, 0)}, β = ∅, π = 0, p = 1 0 if Σ = ∅, α = ∅, β = {({v}, 0)}, π = 0, p = 0 +∞ in all other cases. Forget bag. Bag X i has one child bag X j , with X i = X j \ {v}. We compute f i (Σ, α, β, π, p) as follows. f i (Σ, α, β, π, p) = min {f j (Σ ∪ {v}, α , β, π, p): α -v = α} ∪ {f j (Σ, α, β , π, p): β -v = β} (5)
Introduce bag. Bag X i has one child bag X j , with X i = X j ∪ {v}. In this case, we compute f i (Σ, α, β, π, p) as follows.

f i (Σ, α, β, π, p) =          min {f j (Σ \ {v}, α , β, π, p ): α + v = α, p = p + |α|-|α |} + k v (v ∈ Σ) min {f j (Σ, α, β , π , p): β + v = β, π = π + β -β } (v / ∈ Σ) (6)
Join bag. Bag X i has two child bags X i , X i and X i = X i = X i . The recursion for f i (Σ, α, β, π, p) is written as follows.

f i (Σ, α, β, π, p) = min f i (Σ, α , β , π , p ) + f i (Σ, α , β , π , p ) -k(Σ): α + α = α, β + β = β, p + p -|α |-|α |+|α|= p, π + π -β -β + β = π (7)
Proposition 3: The Connected Pairwise CNP with unit connection costs is solved to optimality by the recursive functions ( 5)-( 7) over any nice tree decomposition of a given graph.

Proof. See Appendix A.

Theorem 1: The Connected Pairwise CNP with unit connection costs can be solved in polynomial time over graphs with a treewidth bounded by a constant κ.

Proof. If the treewidth of a graph is bounded by κ, we can find a nice tree decomposition of the graph with a number of bags O(κn) in polynomial time.

The DP algorithm requires to compute the values As noticed in [START_REF] Addis | Removing critical nodes from a graph: complexity results and polynomial algorithms for the case of bounded treewidth[END_REF], the latter conditions imply that the number of potential CCCs α (β) is bounded by a polynomial function in n: the number of the different partitions A i (B i ) is a function of κ and, for each partition, the possible choices of elements 0 ≤ a i (b i ) ≤ n is bounded by (n + 1) (κ+1) . Hence, the number of f i values to be computed is bounded by a polynomial in n.

f i (Σ, α, β, π, p) for all bags X i , all Σ ⊆ X i , all α ∈ Γ(Σ, |V i \ X i |), β ∈ Γ( Σ, |V i \ X i |),
Finally, since all the potential CCCs can be enumerated in polynomial time, it is easy to observe that computing each entry of the recursive functions ( 5)-( 7) requires only a polynomial number of operations. Therefore, the DP algorithm has a polynomial time complexity when κ is a constant.

We close this section by underlining that in the case of arbitrary connection costs, the value of the parameter π would not be polynomially bounded anymore. Moreover, the computation of the connection cost of a connected component is less straightforward and would invalidate the recursion relations ( 6) and ( 7).

The Connected CNP over trees

This section investigates the complexity for the Connected CNP over trees. Since trees have a bounded treewidth (equal to 1), the results of the previous section apply to the instances of the Connected CNP over trees with unit connection costs and to the instances of the Connected MinMaxC /MaxNum CNP over trees. However, while our DP algorithm over a nice tree decomposition of a graph has a higher time complexity than the algorithm of [START_REF] Addis | Removing critical nodes from a graph: complexity results and polynomial algorithms for the case of bounded treewidth[END_REF] for the classic CNP, we will show in the following that exploiting the connected structure of the critical set leads to faster specialised algorithms than those for the classic CNP over trees.

In this section we first prove that the Connected Pairwise CNP over trees with arbitrary connection and deletion costs is NP-complete. Then, we present pseudopolynomial and polynomial algorithms for different input configurations and compare the obtained results with the existing results for the Pairwise CNP over trees in [START_REF] Di Summa | Complexity of the critical node problem over trees[END_REF]. Our results are summarised in Table 1 together with the results of [START_REF] Di Summa | Complexity of the critical node problem over trees[END_REF] on the classic CNP over trees for comparison. We also report in the table the results for the problems over paths. In Appendix B, we also prove that the Connected MinMaxC CNP over trees turns out to be polynomially solvable. As the Connected MaxNum CNP over trees can be solved in polynomial time by the DP algorithm developed for graphs with bounded treewidth without imposing any restriction on the input data (see Appendix C), we decided not to analyse further this problem variant over trees.

c ij k i Complexity Connected Pairwise CNP Pairwise CNP Trees: ≥ 0 > 0 Weakly NP-hard Strongly NP-hard [18] ≥ 0 = 1 Solvable in O(n 3 ) Strongly NP-hard [18] = 1 > 0 Solvable in O(n 4 ) Solvable in O(n 7 ) [18]
Paths:

≥ 0 > 0 Solvable in O(n 3 )
Weakly NP-hard [START_REF] Aringhieri | Polynomial and pseudo-polynomial time algorithms for different classes of the Distance Critical Node Problem[END_REF][START_REF] Di Summa | Complexity of the critical node problem over trees[END_REF] Table 1: Summary of the derived complexity results for the Connected Pairwise CNP over trees/paths and comparison with the complexity results in the literature for the Pairwise CNP over trees/paths.

NP-completeness

In [START_REF] Di Summa | Complexity of the critical node problem over trees[END_REF] it has been shown that the Pairwise CNP over trees with general connection costs (c ij ≥ 0) is strongly NP-hard. It is also shown that the same result holds even with the further input restriction k i = 1 for each i ∈ V . The Pairwise CNP over paths with general costs has been proved to be NPcomplete in [START_REF] Di Summa | Complexity of the critical node problem over trees[END_REF] and shown to be weakly NP-complete in [START_REF] Aringhieri | Polynomial and pseudo-polynomial time algorithms for different classes of the Distance Critical Node Problem[END_REF]. We show here that the decision version of the Connected Pairwise CNP over trees, where we seek for solutions with a pairwise connectivity less than (or equal to) a threshold value Π, is also NP-complete.

Theorem 2: The decision version of the Connected Pairwise CNP over trees with arbitrary connection and deletion costs is NP-complete.

Proof. The decision version of the Connected Pairwise CNP over trees is indeed an NP-problem as we can compute and check the objective value of any solution in polynomial time. We prove the theorem by reducing an arbitrary instance of the decision version of the Knapsack Problem (KP), a well known NP-complete problem, to an instance of the decision version of the Connected Pairwise CNP over trees. In an instance of the decision version of the KP we have n items, each with a profit p i and a weight w i for i = 1, . . . , n, and a threshold value P . The problem asks whether there exists a subset of the items with a total weight that does not exceed a capacity W and a total profit greater than (or equal to) P . If we consider binary variables x i equal to 1 if item i is chosen and equal to 0 otherwise, we need to find a solution vector x * such that n i=1 w i x * i ≤ W and n i=1 p i x * i ≥ P . We now construct an instance of the Connected Pairwise CNP as follows. For each item i, we introduce two nodes 2i -1 and 2i linked by an edge {2i -1, 2i}. Each node 2i -1 is a leaf node with k 2i-1 = 1. We set k 2i = w i for each node 2i and c 2i-1,2i = p i for each pair (2i -1, 2i). We then add a root node 2n + 1 with k 2n+1 = 1 and an edge {2i, 2n + 1} to each node 2i with c 2i,2n+1 = Π + 1. All other connection costs are set to 0. Finally, we set K = W + 1 and Π = n i=1 p i -P . Obviously, such a reduction is polynomial.

We show that there exists a feasible solution for the decision version of the KP if and only if there exists a feasible solution for the decision version of the Connected Pairwise CNP. Let v * denote a feasible solution vector of the Connected Pairwise CNP with binary variables v j (j = 1, . . . , 2n+1) equal to 1 if node j is removed. Given a solution x * to the decision version of the KP, we derive the corresponding Connected Pairwise CNP solution by setting

v * 2i = x * i , v * 2i-1 = 0 for i = 1, . . . , n and v * 2n+1 = 1. Such a solution is feasible because it has a connected set of removed nodes, 2n+1 j=1 k j v * j ≤ W + 1 = K and a pairwise connectivity equal to n i=1 p i - i:v * 2i =1 p i ≤ n i=1 p i -P = Π.
On the other hand, suppose we have a solution v * to the decision version of the Connected CNP. This solution must necessarily have v * 2n+1 = 1 or else the objective function would be larger than Π (as in that case we could remove at most one intermediate node 2i in order to maintain the connectivity of the critical set). We can also assume without loss of generality that v * 2i-1 = 0 for i = 1, . . . , n. In fact, as v * 2n+1 = 1, any leaf node 2i -1 can be removed only if its neighbour 2i is removed. But in this case the removal of a leaf node is suboptimal as this operation would only induce budget consumption without lowering the objective function. We derive a feasible KP solution x * by setting x * i = v * 2i for i = 1, . . . , n. Indeed, we have:

n i=1 w i x * i = n i=1 w i v * 2i ≤ W and n i=1 p i x * i = i:v * 2i =1 p i ≥ P
where the inequality i:v * 2i =1 p i ≥ P is implied by considering that for the objective function of v * we have n i=1 p ii:v * 2i =1 p i ≤ Π = n i=1 p i -P . Hence, since the decision version of the KP can be reduced to the decision version of the Connected Pairwise CNP over trees, the Connected Pairwise CNP over trees is NP-complete.

Dynamic Programming algorithms

We derive dynamic programming algorithms to solve the Connected Pairwise CNP over trees. The logic of the algorithms is to recursively exploit the requirement that the set of the removed nodes must be connected, which implies that over trees the removed nodes must constitute a tree as well. This consideration leads to dynamic programming schemes running with a considerably lower time complexity with respect to the solution methods derived in [START_REF] Di Summa | Complexity of the critical node problem over trees[END_REF] for the Pairwise CNP over trees. The proposed dynamic programs allow us to show that the Pairwise CNP over trees with arbitrary connection and deletion costs is weakly NP-hard and that the problem is polynomially solvable when either the connection costs or the deletion costs are one. Hence, we make progress in evaluating at what extent the inherent difficulty of solving the Pairwise CNP over trees reduces when the set of the deleted nodes is required to be connected.

Consider a tree T rooted in a given node r. We define the levels of T as follows. The children of the root node r constitute the first level of T , the children of the children of r define the second level of T , and we proceed in the same way moving down in T until all its levels are identified. For our algorithmic developments, we denote by T a the subtree of tree T rooted in a node a. Any subtree T a has node a as root, it contains the children of a and all the subsequent nodes in the lower levels of T . We denote the i -th child of a as a i and the set of children of a as CH a , i.e. CH a = {a 1 , a 2 , . . . }. Also, let n a = |T a | be the number of nodes in T a . We indicate by P W (T a ) = i<j {c ij : i, j ∈ T a } the overall cost of the connections between each node pair in T a . Notice that the computation of all P W (T a ) can be performed in O(n 3 ). Finally, let f i denote the father node of a node i.

The structure of the dynamic programming recursions will be based on a suitable exploration of each subtree T a where node a is removed and any other node can be removed only if all the nodes in the unique path between the root a and it are removed. We remark that our dynamic programming schemes resemble the so called left-right approach proposed in [START_REF] Johnson | On knapsacks, partitions, and a new dynamic programming technique for trees[END_REF] and a related variant proposed in [START_REF] Cho | A depth-first dynamic programming algorithm for the tree knapsack problem[END_REF] for the precedence constraint knapsack problem over trees. This problem is a variant of the standard knapsack problem where the items are associated with the nodes of a tree and an item can be packed only if all its predecessors in the unique path from the root node are selected. In the following, we first handle the case with arbitrary connection costs c ij and then consider the case with unit connection costs.

Arbitrary connection costs (c

ij ≥ 0 for i, j ∈ V )
For each subtree T a , we compute an optimal solution that minimises the pairwise connectivity in the subtree when root a is removed. We first index the nodes by a depth first search starting from the root, i.e. a = 1, and excluding the leaves. Let n a (< n a ) denote the overall number of ordered nodes. Then, we recursively consider the nodes for removal according to the depth first search (see the example in Figure 1 after the description of the dynamic program functions). The leaves in T a will not be visited as if their father node is removed in a solution, the removal of any leaf node will not contribute to further lowering the objective function. If instead the father node is not removed, no leaf node can be removed as the resulting set of deleted nodes would not be connected. For each subtree T a , we consider the subproblems where a subset of the nodes can be removed. Correspondingly, we define for a triple (i, j, k) with 1 ≤ i ≤ j ≤ n a and 0 ≤ k ≤ K: R a (i, j, k) := minimum connection costs of a solution for subtree T a when the nodes in the path from 1 to i are removed and other nodes in set {1, . . . , j} can be removed, given a budget k.

If no feasible solution exists for a triple (i, j, k), we set R(i, j, k) = +∞ (i.e. an arbitrarily large value). We analyse all the subtrees and compute an optimal solution for the original tree T by selecting the node a * ∈ V such that:

a * = arg min{R a (1, n a , K) + P W (T \ T a ) : a ∈ V } (8)
where the connection costs R a (1, n a , K) in T a are summed with the connection costs P W (T \ T a ) in the remaining part of the tree. Notice that when a is a leaf node or a node whose children are leaves, we have n a = 1 and either R a (1, n a , K) = 0 if k a ≤ K or else R a (1, n a , K) = +∞. In the remaining cases, to compute R a (1, n a , K) we can recursively compute the R a (i, j, k) values for some triples (i, j, k) identified by the depth first exploration of T a . In particular, we will only consider specific values of j for given values of i and k. For the root node a = 1 and k = 0, . . . , K we have:

R a (1, 1, k) = h∈CH 1 P W (T h ) if k 1 ≤ k; +∞ otherwise. (9)
In fact, if the value k of the budget allows the removal of node 1, the connection costs are equal to the sums of the pairwise connectivities of the subtrees rooted in each child of node 1, i.e. h∈CH 1 P W (T h ). Then, we consider the removal of a node i > 1 by going down in the tree and applying a down move.

More precisely, in a down move we set j = i and have for k = 0, . . . , K:

R a (i, j, k) = R a (f i , j -1, k -k i ) -P W (T i ) + h∈CH i P W (T h ) if k i ≤ k; +∞ otherwise. ( 10
)
Hence, in a down move the node i is added to the set of nodes available for removal (j = i) and node i is removed when k i ≤ k. In such a case, the pairwise connectivity in T a is given by the connection costs obtained with triple (f i , j -1, k -k i ), without the term P W (T i ), plus the connection costs in the subtrees rooted in each child of i. The latter costs are represented by the term h∈CH i P W (T h ).

A down move is performed whenever we can visit a new node by moving down in T a . Otherwise, after visiting a node i, we backtrack to its father node f i and apply an up move where we have for k = 0, . . . , K:

R a (f i , j, k) = min{R a (f i , i -1, k); R a (i, j, k)}. (11)
In the min comparison in [START_REF] Bapat | Safe sets, network majority on weighted trees[END_REF], we evaluate, for a given value of k and father node f i , whether it is convenient to remove the child node i when the nodes available for removal are the nodes 1, . . . , j.

If node i is removed, we consider the term R a (i, j, k). Else, we consider the subproblem associated with triple (f i , i -1, k) and take the term R a (f i , i -1, k) as the nodes i + 1, . . . , j (which lie in the tree under the node i when an up move is considered) cannot be available for removal if node i is not removed. An up move is performed until a new down move can be applied. By following these rules, the tree is explored until we compute the optimal solution value R a (1, n a , K) (see the example in Figure 1). Without going into the details, we remark that we can implement a simple backtracking procedure to compute also the optimal solution corresponding to R(1, n a , K) without increasing the time complexity of the algorithm. Considering the proposed dynamic program, we can state the following proposition.

Proposition 4: The Connected Pairwise CNP over trees with arbitrary connection and deletion costs admits a pseudopolynomial time algorithm with time complexity O(n 2 K).

Proof. For a given subtree T a , the dynamic programming algorithm analyses the relevant edges twice for each value of k. Thus, the number of elementary operations needed to execute the algorithm is bounded by O(n a K). Since we consider all the subtrees to compute an optimal solution for T , the overall running time is bounded by O(n 2 K).

With the results of Proposition 4 and Theorem 2, we immediately have the following statement.

Corollary 1: The Connected Pairwise CNP over trees with arbitrary connection and deletion costs is weakly NP-hard.

In problem instances with unit deletion costs (k i = 1 for each i ∈ V ), we have the following result.

Down move

Up move

Figure 1: Example of a sequence of down/up moves for the exploration of a subtree T a where the following sequence of R a (i, j, k) entries is computed for k = 0, . . . , K: R a

(1, 1, k), R a (2, 2, k), R a (3, 3, k), R a (2, 3, k), R a (4, 4, k), R a (2, 4, k), R a (1, 4, k), R a (5, 5, k), R a (6, 6, k), R a (5, 6, k), R a (7, 7, k), R a (5, 7, k), R a (1, 7, k).
Corollary 2: The Connected Pairwise CNP over trees with arbitrary connection costs and unit deletion costs is polynomially solvable.

Proof. Since we have K < n in the meaningful instances with unit deletion costs, the dynamic program described above constitutes a polynomial time algorithm as it runs with O(n 3 ) time complexity.

Unit connection costs (c

ij = 1 for i, j ∈ V )
In any instance of the Connected Pairwise CNP over trees with unit connection costs, the pairwise connectivity is bounded from above by the number of node pairs n(n -1)/2. We can modify the above recursions for dynamic programming by deletion costs and perform dynamic programming by connection costs for a given subtree T a . For a triple (i, j, c) with 1 ≤ i ≤ j ≤ n a and 0 ≤ c ≤ h∈CH 1 P W (T h ), we define: R a (i, j, c) := minimum deletion cost of a solution for subtree T a with connection costs ≤ c when the nodes in the path from 1 to i are removed and other nodes in set {1, . . . , j} can be removed.

As in the previous algorithm, we set R(i, j, c) = +∞ if no feasible solution exists for a triple (i, j, c).

In the root node a = 1 we have for each value of c:

R a (1, 1, c) =    k 1 if h∈CH 1 P W (T h ) ≤ c; +∞ otherwise. (12)
Clearly, when we only remove the root node, the value of R coincides with k 1 when h∈CH 1 P W (T h ) ≤ c. In a down move we again set j = i and have for each value of c:

R a (i, j, c) =          R a (f i , j -1, c + c ) + k i if R a (f i , j -1, c + c ) + k i ≤ K, with c = P W (T i ) - h∈CH i P W (T h ) and c + c ≤ h∈CH 1 P W (T h ); +∞ otherwise. (13)
Here, we consider the removal of node i in a feasible solution for triple (i, j, c). Correspondingly, we add the deletion cost k i to the deletion cost given by the triple (f i , j -1, c + c ) (with j = i), where c represents the decrease of the pairwise connectivity when node i is removed. Clearly, a value c + c out of the relevant range of values of c is not considered. Similarly to the previous dynamic program, in an up move we have for each c:

R a (f i , j, c) = min{R a (f i , i -1, c); R a (i, j, c)}. (14)
The optimal value for the subtree T a is given by the smallest quantity c min such that R a (1, n a , c min ) ≤ K. The corresponding solution value for T is c min + P W (T \ T a ). By analyzing all the subtrees, we identify the subtree T a that contains a global optimal solution and recover such a solution by a backtracking procedure. Considering the modified dynamic program, we state the following proposition.

Proposition 5: The Connected Pairwise CNP over trees with unit connection costs admits a polynomial time algorithm with time complexity O(n 4 ).

Proof. The dynamic programming algorithm for each subtree T a has a running time of O(2n a • n a (n a -1)/2) = O(n 3 a ) as we consider the relevant edges in the subtree twice for each value of c and we have c ≤ n a (n a -1)/2. Considering all the O(n) subtrees, the overall time complexity is O(n 4 ).

Polynomiality over paths

The Pairwise CNP was suggested to be weakly NP-hard over paths with arbitrary connection and deletion costs in [START_REF] Di Summa | Complexity of the critical node problem over trees[END_REF]. This result was then proved in [START_REF] Aringhieri | Polynomial and pseudo-polynomial time algorithms for different classes of the Distance Critical Node Problem[END_REF]. We show here that the Connected Pairwise CNP over paths can be easily solved in polynomial time. We consider the nodes indexed by increasing numbers from left to right in the path. It suffices to evaluate n solutions where we start removing a different node i ∈ V and progressively delete subsequent nodes j > i until the deletion budget allows it. Since the connection costs of a given solution can be computed in O(n 2 ), the problem can be solved to optimality in O(n 3 ) time. We summarise this result in the following proposition. Notice that the same algorithm can be applied over paths to the other objective functions studied in this article, MinMaxC and MaxNum, but with a lower time complexity due to the computation of the objective function, i.e., O(n 2 ) for the Connected MinMaxC CNP and O(n) for the Connected MaxNum CNP (whose solutions can yield either one or two connected components).

We conclude this section by observing that even stronger results can be obtained for the version of the CNP where the set of critical nodes is further restricted to form a path, see e.g. [START_REF] Granata | Network interdiction via a critical disruption path: Branch-and-price algorithms[END_REF]. In such a version of the CNP over trees, since there exists a unique path between any two nodes, there is only a polynomial number of O(n 2 ) paths that we can consider for the critical set, therefore solving such a problem over trees can be done in polynomial time. [START_REF] Aringhieri | A general Evolutionary Framework for different classes of Critical Node Problems[END_REF] The Connected CNP over series-parallel graphs Several variants of the CNP have been studied specifically over series-parallel graphs: for example, [START_REF] Shen | Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs[END_REF] established the polynomiality of the CNP based on the cardinality of the largest connected component or the number of connected components, while [START_REF] Aringhieri | Polynomial and pseudo-polynomial time algorithms for different classes of the Distance Critical Node Problem[END_REF] established polynomiality for a certain class of the Distance-CNP with unit connection costs. Since series-parallel graphs have treewidth 2, they can be solved by the (pseudo-)polynomial algorithm described in Section 3 in certain cases. In this section, we provide further insight on the cases where such instances prove to be NP-hard.

We recall a few definitions and facts about series-parallel graphs. Two-terminal graphs (TTG) G(s, t) with source node s and sink node t represent the building blocks of a series-parallel graph, since such a graph can be obtained by performing series and parallel compositions of two TTG at a time: the series operation consists in merging nodes t 1 and s 2 of TTG graphs G 1 (s 1 , t 1 ) and G 2 (s 2 , t 2 ) while the parallel operation consists in merging node s 1 with s 2 on one part and node t 1 with t 2 on the other part. The full series-parallel graph G can be constructed by a set of series-parallel operations which can be represented by a binary tree where the leaves are two-nodes single-edged graphs called K2 and the construction can be performed by following the operations from leaves to root (each node being either a series or a parallel operation between the graphs of the nodes below). Such a binary tree can be identified in linear time [START_REF] Takamizawa | Linear-time computability of combinatorial problems on series-parallel graphs[END_REF][START_REF] Valdes | The recognition of series-parallel digraphs[END_REF]. An example is given in Figure 2 where two TTGs are merged using a parallel operation. We now propose to study the complexity of the Connected Pairwise CNP over series-parallel graphs when the connection costs are non-unitary, since the case of unitary connection costs is handled by the recursion proposed in Section 3. We will first establish the NP-completeness of the Connected CNP based on pairwise connectivity over series-parallel graphs with integer connection and deletion costs and provide a result of strong NP-hardness for the classic Pairwise CNP over series-parallel graphs with integer connection costs. We sum up our findings over series-parallel graphs in Table 2 along with existing results for the classic Pairwise CNP.

s 1 t 1 s 2 t 2 s t
We first perform a reduction of the decision version of the Partition Problem to prove the NPcompleteness of the Connected CNP over series-parallel graphs.

c ij k i complexity Connected Pairwise CNP Pairwise CNP ≥ 0 > 0 NP-hard Strongly NP-hard = 1 > 0 Polynomial Polynomial [2]
Table 2: Summary of our complexity results for the Connected Pairwise CNP over series-parallel graphs along with complexity results for the Pairwise CNP (partially taken from [START_REF] Addis | Removing critical nodes from a graph: complexity results and polynomial algorithms for the case of bounded treewidth[END_REF]). Proof. We introduce an instance of the Partition Problem [START_REF] Garey | Computers and intractability: A guide to the theory of NPcompleteness[END_REF] as follows. An instance of the Partition Problem is made of a set A = {1, . . . , n} of n positive integers a i and its decision version consists in identifying a subset A ⊂ A such that i∈A a i = i∈A a i /2.

n + 1 1 2 n n + 2 c 1,n+2 = a 1 c 2,n+2 = a 2 c n,n+2 = a n k n+1 = 1 k n+2 = K + 1 k 1 = a 1 k 2 = a 2 k n = a n
We construct an instance of the decision version of the Connected CNP based on a general instance of the Partition Problem as follows. For each i ∈ A, we define a node i with k i = a i . We also define a node n + 1 with k n+1 = 1 and a node n + 2 with k n+2 = i∈A a i /2 + 2 and add edges (i, n + 1) and (i, n + 2) for i ∈ A. We set c i n+2 = a i for i ∈ A while all other connection costs are null. The terminal nodes s and t are nodes n + 1 and n + 2 and the overall graph is a series-parallel graph. The maximum threshold K on the total weight of deleted nodes is fixed at K = i∈A a i /2 + 1 and the maximum threshold Π on total pairwise connectivity is fixed at P = i∈A a i /2 for the decision version of the Connected CNP. We display a graphical example of the obtained Connected CNP instance in Figure 3 where it can be seen that the graph is obtained by series combinations of K2 graphs and finish the combination by an overall parallel operation. The reduction is polynomial.

We now prove that there exists a feasible solution for the decision version of the Partition Problem iff there exists a feasible solution for the decision version of the Connected CNP. Let us consider a solution A * to the decision version of the Partition Problem and define the corresponding Connected CNP solution as v * i = i for i ∈ A * , v * n+1 = 1 and v * n+2 = 0. Such a solution is connected and has:

n+2 i=1 k i v * i = i∈A * a i + 1 = K and i<j c ij u * ij = i∈A\A * a i = i∈A a i /2 = P,
which implies it is a feasible solution to the decision version of the Connected CNP. On the other hand, suppose that we have a feasible solution to the decision version of the Connected CNP. It has necessarily v * n+2 = 0 (in order to respect the budget constraint). Since the critical set must be connected, setting v * n+1 = 0 would mean that we can delete only one node in the graph. This could result in an optimal solution only if, given the index i m ∈ A, we have a im = i∈A a i /2. In such a case, the deleted node corresponds to the optimal subset A * of the Partition Problem and the correspondence is easy to obtain. In any other case, any feasible solution to the decision version of the Connected CNP must have v * n+1 = 1 so that the deletion of any subset of the nodes i ≤ n induces a connected subgraph. The residual budget for deleting such nodes is K -1 = i∈A a i /2. By construction of the connection cost, we have that i,j∈V

:i<j c ij u * ij = i∈A:v * i =0 a i = i∈A a i -i∈A:v * i =1 a i , hence we have that i,j∈V :i<j c ij u * ij ≥ i∈A a i -K + 1 = i∈A a i /2.
In order to have a Yes instance for the Connected CNP, we need to have the relation:

i∈A:v * i =1 a i = i∈A:v * i =0 a i = i∈A a i /2,
which guarantees that the partition instance is a Yes instance too, which completes the proof.

Since one of our goals is to compare the complexity of the Connected CNP with the complexity of the classic CNP, we will also derive an NP-completeness result for the classic Pairwise CNP over seriesparallel graphs, albeit stronger than the one above. In order to do this, we will use the reduction from the Multicut in Trees (MCT) presented in [START_REF] Di Summa | Complexity of the critical node problem over trees[END_REF] to derive the strong NP-completeness of the Pairwise CNP over trees and we refer to [START_REF] Di Summa | Complexity of the critical node problem over trees[END_REF] for more details. The MCT consists in finding the edge set of minimum weight whose deletion will disconnect a collection H = {{u 1 , v 1 }, . . . , {u t , v t }} of node pairs in the tree. In the proof of the following theorem, we consider only the unweighted version of the MCT where each edge has unitary weight, which has been shown to be strongly NP-complete in [START_REF] Garg | Primal-dual approximation algorithms for integral flow and multicut in trees[END_REF].

Theorem 4: The decision version of the Pairwise CNP is strongly NP-complete on seriesparallel graphs with integer connection costs, even with unit deletion costs.

Proof. We need to prove the equivalence of a Yes instance of the MCT with a Yes instance of the Pairwise CNP over series-parallel graphs with unit deletion costs. Consider an instance of the unweighted MCT, i.e. a tree T = (V, E) with n = |V | and a collection H of pairs of nodes to disconnect. An instance of the decision version of the MCT also contains a maximum threshold B and asks whether there exists an edge subset W ⊂ E with |W |≤ B such that the removal of edge subset W disconnects each pair in H. In order to construct an instance of the decision version of the Pairwise CNP over series-parallel graphs, we will first follow the reduction provided in Section 2 of [START_REF] Di Summa | Complexity of the critical node problem over trees[END_REF]. Therefore we first construct a tree T = (V , E ) containing all the nodes in V . For each edge of e = {i, j} ∈ E, we add two nodes e 1 and e 2 and three edges {i, e 1 }, {e 1 , e 2 } and {e 2 , j}, i.e. i -e 1 -e 2 -j forms a subpath. We set the connection cost c uv = 1 for {u, v} ∈ H, c uv = M > |H| if {u, v} = {e 1 , e 2 } for all e ∈ E and c uv = 0 in any other case. Finally, we add an extra node q with an edge between q and each leaf node in T to obtain a series-parallel graph G(r, q) with terminal nodes r and q where r is the root node of T . We set the connection costs c iq = 0 for all nodes i ∈ V and all deletion costs k i = 1 for i ∈ V ∪ {q}. We set the maximum deletion threshold K = B and the maximum connectivity threshold P = M (n -K -1). We observe that the deletion of terminal node q does not provide any reduction of the total connection in the decision version of the Connected CNP. Therefore, the logic of the proof follows the steps of Proposition 2.1 in [START_REF] Di Summa | Complexity of the critical node problem over trees[END_REF] and we refer the reader to it for further details. Since the unweighted MCT is strongly NP-complete, it follows that the Connected CNP on series-parallel graphs is strongly NP-complete, even with unit deletion costs.

The results for the MinMaxC CNP over series-parallel graphs are reported in Appendix B.

Conclusions

We have introduced in this work a variant of the Critical Node Problem where the set of critical nodes forms a connected subgraph. This requirement had only been partially investigated for specially structured critical sets in [START_REF] Granata | Network interdiction via a critical disruption path: Branch-and-price algorithms[END_REF][START_REF] Walteros | Detecting critical node structures on graphs: A mathematical programming approach[END_REF]. We studied three versions of the problem based on three different objective functions and stated their NP-hardness status on even biconnected planar bipartite graphs.

We then studied the complexity of the Connected CNP on tree decompositions of a general graph and derived dynamic programming algorithms. We showed that the problems are polynomially solvable with unit weights in the objective function when the treewidth of the graph is bounded by a constant. We also investigated the considered problems over trees and highlighted the differences in complexity with the classic CNP over trees. Finally, we studied the complexity of the problems over series-parallel graphs with arbitrary costs and we provided additional results on the NP-hardness of several variants of the classic CNP over series-parallel graphs.

The complexity of some versions of the CNP in other types of graphs has been successfully investigated, e.g., in [START_REF] Lalou | Component-cardinality-constrained critical node problem in graphs[END_REF] for proper interval graphs and in [START_REF] Lalou | A polynomial-time algorithm for finding critical nodes in bipartite permutation graphs[END_REF] for bipartite permutation graphs. Therefore, an analysis of the Connected CNP over such specially structured graphs could be a natural direction for future research. Another interesting research line would be the development of decomposition methods based on mathematical programming to solve the Connected CNP on general graphs, as in, e.g., [START_REF] Granata | Network interdiction via a critical disruption path: Branch-and-price algorithms[END_REF] and [START_REF] Walteros | Detecting critical node structures on graphs: A mathematical programming approach[END_REF]. Finally, as underlined in the Introduction, many heuristic approaches were developed for the CNP given the inherent difficulty of solving any variant of the problem over general graphs. It would be interesting to tailor some of these approaches to include the constraint of having a connected critical set.

Appendix A Proof of correctness of the DP algorithm over tree decompositions

We consider the following strategy to show the correctness of the recursive functions ( 5)- [START_REF] Aringhieri | Polynomial and pseudo-polynomial time algorithms for different classes of the Distance Critical Node Problem[END_REF]. For each type of bag of the nice tree decomposition, we show that f i (Σ, α, β, π, p), i.e. the left hand side (lhs) of the equations, is at least as large as the right hand side (rhs) of the equations under the assumption that f i (Σ, α, β, π, p) exists finite. We also show that f i (Σ, α, β, π, p) is at most as large as a finite value of the rhs of the equations. This implies that the recursive functions are correct when the f i values are finite. Notice that when the f i values are not finite, we just have a propagation of +∞ values and thus the correctness of the recursive functions still holds.

α is also the CCC of Σ = Σ in G[S ]. Define β as the CCC of Σ in G[ S ]. By Lemma 1(b) β + v is the CCC of Σ = Σ ∪ {v} in G[ S], hence β + v = β.
As v is not added to the critical set when G[V i ] is considered, the variation of the pairwise connectivity of G[V i ] and G[V j ] is given by the difference β -β . This because all the neighbours of v in G[ S] are included in Σ due to the properties of an introduce bag (see Section 3.1). Thus, we can compute the variation of the pairwise connectivity by considering only the components in G[ S] and G[ S ] with a non trivial intersection with Σ and Σ , respectively. Given this counting argument, if we also have π = π + β -β then S(= S ) is a feasible solution to Π j (Σ, α, β , π , p), the rhs of (6) exists, finite, and

f i (Σ, α, β, π, p) = k(S) = k(S ) ≥ min {f j (Σ, α, β , π , p): β + v = β, π = π + β -β }.
Now let the rhs of ( 6) exist, finite, and consider S ⊆ V j such that min {f j (Σ, α, β , π , p):

β + v = β, π = π + β -β } = k(S ).
We define S = S ∪ {v} and note here that S = V i \ S = S . We have that α is the CCC of Σ in G[S] and

β + v = β is the CCC of Σ ∪ {v} in G[ S]
by Lemma 1(b). If the equality π = π + β -β also holds, we can state that S is a feasible solution to Π i (Σ, α, β, π, p). Hence, f i is finite and we have

f i (Σ, α, β, π, p) ≤ k(S) = min {f j (Σ, α, β , π , p): β + v = β, π = π + β -β }.
Clearly, the previous two inequalities show that equality (6) holds when v / ∈ Σ.

Case v ∈ Σ. Let f i (Σ, α, β, π, p) exist, finite, and S be the optimal solution to Π i (Σ, α, β, π, p).

f i (Σ, α, β, π, p) ≤ k(S) = k(S ) + k v = min {f j (Σ \ {v}, α , β, π, p ): α + v = α, p = p + |α|-|α |} + k v .
The previous inequalities prove that equality (6) also holds when v ∈ Σ.

Join bag. First, assume that f i (Σ, α, β, π, p) = k(S) is finite for some S ⊂ V i \ Σ. Then Σ ⊆ S ⊆ V i \Σ, Σ ⊆ S ⊆ V i \ Σ, #conn(G[ S]) = π, |comp(G[S])|= p.
Let us define S = S∩V i , S = V i \ S , S = S∩V i , S = V i \ S . We have S = S ∪ S and S = S ∪S . Notice also that Σ Since by construction Σ is included in both S and S , we have k(S) = k(S ) + k(S ) -k(Σ). Thus, when S and S are feasible solutions to Π i (Σ, α , β , π , p ) and Π i (Σ, α , β , π , p ), the rhs of ( 7) is finite and we have

⊆ S =⇒ Σ ⊆ S since Σ ⊆ X i = X i ; also, S ⊆ V i \ Σ =⇒ S ∩ V i ⊆ V i \ Σ, hence Σ ⊆ S ⊆ V i \ Σ. Similarly, it follows that Σ ⊆ S ⊆ V i \ Σ, Σ ⊆ S ⊆ V i \ Σ, Σ ⊆ S ⊆ V i \ Σ. Let
f i (Σ, α, β, π, p) = k(S) = k(S ) + k(S ) -k(Σ) ≥ ≥ min{f i (Σ, α , β , π , p ) + f i (Σ, α , β , π , p ) -k(Σ)}.
Now assume that the rhs of (7) exists, finite, i.e. f i (Σ, α , β , π , p ) = k(S ) and f i (Σ, α , β , π , p ) = k(S ) for a suitable choice of S and S that minimises the rhs. Define S = S ∪ S , S = S ∪ S . Note that here Σ

⊂ S ⊆ V i \ Σ, Σ ⊆ S ⊆ V i \ Σ. By Lemma 2, since α ,α are CCCs of Σ in G[S ], G[S ], α + α = α is the CCC of Σ in G[S]. Similarly, β + β = β is the CCC of Σ in G[ S]. As before, if π = (π -β ) + (π -β ) + β and p = (p -|α |) + (p -|α |) + |α|, then S is a feasible solution to Π i (Σ, α, β, π, p), f i is finite and f i (Σ, α, β, π, p) ≤k(S) = k(S ) + k(S ) -k(Σ) = min f i (Σ, α , β , π , p ) + f i (Σ, α , β , π , p ) -k(Σ) .
The derived inequalities prove that equality (7) holds. deal with such an objective function, we redefine the second elements of the pairs of a CCC α (or β). More precisely, we now define α = {(Σ ∩ V (H), c(V (H) \ Σ)): H ∈ comp(G), Σ ∩ V (H) = ∅} as the CCC of a set Σ in a graph G and we modify only the restriction operation of a potential CCC α = {(A i , a i )} k i=1 ∈ Γ(Σ, r) as follows:

α -v = {(A i \ {v}, a i + c(A i ∩ {v})): (A i , a i ) ∈ α, |A i \ {v}| > 0}.
Also, we now have

β = max{c(B i ) + b i } i=1...k for a CCC β = {(B i , b i )} i=1...k .
We consider the same function f i (Σ, α, β, π, p) as in Section 3.3 but now π = max{c(H) : H ∈ comp(G[ S])}. The dynamic program follows the same reasonings as those of the algorithm for the Connected Pairwise CNP. For a start bag X i = {v} we have

f i (Σ, α, β, π, p) =      k v if Σ = {v}, α = {({v}, 0)}, β = ∅, π = 0, p = 1 0 if Σ = ∅, α = ∅, β = {({v}, 0)}, π = c v , p = 0 +∞
in all other cases.

The recursive functions ( 5)-( 7) are respectively replaced with:

f i (Σ, α, β, π, p) = min {f j (Σ ∪ {v}, α , β, π, p): α -v = α} ∪ {f j (Σ, α, β , π, p): β -v = β} (15) f i (Σ, α, β, π, p) =                    min f j (Σ \ {v}, α , β, π, p ): α + v = α, p = p + |α|-|α | + k v (v ∈ Σ) min f j (Σ, α, β , π , p): β + v = β, π = max{π , c v + l=1...|β|:B l ∩N (v) =∅ (c(B l ) + b l )} (v / ∈ Σ) (16)
f i (Σ, α, β, π, p) = min f i (Σ, α , β , π , p ) + f i (Σ, α , β , π , p ) -k(Σ): α + α = α, β + β = β, p + p -|α |-|α |+|α|= p, max{π , π , β } = π (17)
The optimal value is given by the state f 1 (Σ, α, β, π, p) ≤ K with α = {(A 1 , a 1 )} or α = ∅, p = 1 and π as small as possible. The proof of correctness of our algorithm is very similar to that for the Connected Pairwise CNP. As regards the time complexity of the DP algorithm, given the definition of the CCCs we now have a number of indices in f i (Σ, α, β, π, p) and a number of operations to perform for the recursive functions which are pseudo-polynomial in n and c(V ). We derive the following proposition and corollary.

Proposition 8: The Connected MinMaxC CNP with arbitrary node weights and arbitrary deletion costs can be solved in pseudo-polynomial time over graphs with a treewidth bounded by a constant κ.

Corollary 3: The Connected MinMaxC CNP with unit node weights and arbitrary deletion costs can be solved in polynomial time over graphs with a treewidth bounded by a constant κ.

We observe that Proposition 8 is more general than Theorem 1 and implies that over graphs with bounded treewidth, the Connected MinMaxC CNP is never strongly NP-hard. Besides, we will show in the next section that the Connected MinMaxC CNP over trees turns out to be polynomial even with arbitrary node weights and arbitrary deletion costs.

B.3 Complexity results over trees

The complexity of the MinMaxC CNP over trees has been studied in [START_REF] Shen | Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs[END_REF], where the problem was proved to be polynomial with unit node weights (k i = 1 ∀i ∈ T ) and weakly NP-hard with arbitrary node weights and arbitrary deletion costs. We show here that the Connected MinMaxC CNP with arbitrary node weights and arbitrary deletion costs is a polynomial problem. We again consider all the subtrees where the root node is removed. For each T a , we solve to optimality the problem over the considered subtree by the following greedy strategy. After the removal of the root node a, we progressively remove the node i with maximum c(T i ) and whose father was already removed (in order to guarantee the connectivity of the deleted set), and iterate as long as the budget constraint is not violated. Notice that each value c(T i ) can be pre-computed in O(n). It is easy to see that this algorithm is optimal. Consider the initial situation where the root node is removed. Clearly, it would be suboptimal to remove other nodes (one or more) instead of the child node i with maximum c(T i ) as this operation would consume deletion budget without improving the objective function. So an optimal solution will indeed remove the node i whenever possible. The same argument applies for the progressive selection of the next nodes to remove in an optimal solution.

After solving the subproblem associated with T a , we take the maximum between the corresponding optimal value and c(T \T a ) to compute the value of the objective function over T . An optimal solution for T is given by analyzing all the relevant subtrees and considering the subproblem that gives the minimum global objective function. The following proposition holds.

Proposition 9: The Connected MinMaxC CNP over trees admits a polynomial time algorithm with time complexity O(n 3 ).

Proof. The execution time of the algorithm for solving each problem associated with a subtree T a is trivially bounded by O(n 2 a ) since, at each iteration, we can select the node to remove in O(n a ) and n a nodes are removed at most. Since the number of subtrees to consider is in O(n), the resulting time complexity is O(n 3 ).

We summarise our results in Table 3.

B.4 Series-parallel graphs

We can state the following proposition for the Connected MinMaxC CNP over series-parallel graphs.

c i k i complexity Connected MinMaxC CNP MinMaxC CNP ≥ 0 > 0 Solvable in O(n 3 ) Weakly NP-hard [40] = 1 > 0 Solvable in O(n 3 ) Solvable in O(n 3 log n) [40]
Table 3: Summary of our complexity results for the Connected MinMaxC CNP over trees and comparison with the complexity results in [START_REF] Shen | Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs[END_REF] for the MinMaxC CNP over trees.

Theorem 5: The decision version of the Connected MinMaxC CNP over series-parallel graphs is NP-complete with arbitrary connection and deletion costs.

Proof. We can show the above theorem by performing a reduction from the Partition Problem, very similar to the one in Theorem 3. The only difference is that we give a node weight c i = a i to all nodes i ∈ A, a deletion budget K = i∈A a i /2 and a deletion cost k n+1 = K + 1 to node n + 1 so that it cannot be deleted anymore. We refer to Figure 4 for a visual example of the Connected MinMaxC CNP instance obtained. Consequently, the undeleted nodes will always form a single connected component whose total weight will be:

i∈A:v * i =0 a i . The rest of the proof is very similar to the proof of Theorem 3.

Corollary 4:

The Connected MinMaxC CNP is weakly NP-hard on series-parallel graphs with arbitrary node weights and deletion costs.

Proof. The DP algorithm of Section 3 for the Connected MinMaxC CNP is valid for integer node weights, which provides a pseudopolynomial time algorithm. Since the problem has an NP-complete decision version, the above result follows.

We can use a slightly modified version of the above proof to show that the classic MinMaxC CNP on series-parallel graphs is NP-complete with arbitrary weights, which had not been investigated before.

Theorem 6: The decision version of the MinMaxC CNP is NP-complete on series-parallel graphs with arbitrary node weights and deletion costs.

Proof. We can perform the same reduction as in the above proof for the Connected MinMaxC CNP, changing the deletion weight of node n + 1 to k n+1 = K + 1 so it cannot be deleted and choosing K = W . The rest of the proof follows very similarly to the one of Theorem 6.

Using the results of [START_REF] Shen | Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs[END_REF] we can formulate the following corollary:

Corollary 5: The MinMaxC CNP is Weakly NP-hard on series-parallel graphs with arbitrary node weights and deletion costs.

Proof. The recursion functions and equations of [START_REF] Shen | Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs[END_REF] can be easily extended to integer node weights, which provides a pseudopolynomial time algorithm. Since the problem has an NP-complete decision version, the above result follows. Our results for the Connected MinMaxC CNP over series-parallel graphs are summed up in Table 4.

n + 1 1 2 n n + 2 k n+1 = K + 1 c n+1 = 0 k n+2 = K + 1 c n+2 = 0 k 1 = c 1 = a 1 k 2 = c 2 = a 2 k n = c n = a n
c i k i complexity Connected MinMaxC CNP MinMaxC CNP ≥ 0 > 0
Weakly NP-hard Weakly NP-hard = 1 > 0 Polynomial Polynomial [START_REF] Shen | Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs[END_REF] Table 4: Summary of our complexity results for the Connected MinMaxC CNP based on the heaviest component weight over series-parallel graphs, along with complexity results for the CNP (partially from [START_REF] Shen | Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs[END_REF]).

Proposition 10: The decision version of the Connected MaxNum CNP is strongly NP-complete in biconnected planar bipartite graphs of maximum degree 4, even with unit deletion costs.

Proof. Analogously to the proof of Proposition

C.2 Graphs with bounded treewidth

We also extend the proposed DP algorithm of Section 3 to the Connected MaxNum CNP. Here we consider the definition of f i (S, α, β, π, p) as in Section 3.

The optimal value is given by the state f 1 (Σ, α, β, π, p) ≤ K with α = {(A 1 , a 1 )} or α = ∅, p = 1 and π as large as possible. Again, the proof of correctness of the algorithm is very similar to that for the Connected Pairwise CNP.

Proposition 11: The Connected MaxNum CNP with arbitrary deletion costs can be solved in polynomial time over graphs with a treewidth bounded by a constant κ.

  all values of π and p with 0 ≤ π ≤ |V i |(|V i |-1)/2 and 0 ≤ p ≤ |V i |. As |V i |≤ n, only n(n -1)/2 + 1 values are possible for parameters π and only n + 1 values for parameter p. Since κ is a constant, the number of possible bags is in O(n) and each bag X i contains a constant number of nodes bounded by κ + 1. So there are at most 2 κ+1 sets Σ and, for any Σ ⊆ X i , both |Σ| and | Σ| are ≤ κ + 1.

Proposition 6 :

 6 The Connected Pairwise CNP over paths is solvable in polynomial time with time complexity O(n 3 ).

Figure 2 :

 2 Figure 2: Example of a parallel operation between two TTGs of a series-parallel graph (on the left), where the final result is displayed on the right.

Figure 3 :Theorem 3 :

 33 Figure 3: Example of a series-parallel instance for the Connected CNP over series-parallel graphs obtained by reduction of a Partition instance.

  Note that v ∈ Σ =⇒ v / ∈ S. Define S = S, S = V j \ S = S \ {v}. Then G[ S ] = G[ S] and β is the CCC of Σ in G[ S]. Note that Σ = Σ \ {v}. Define α as the CCC of Σ in G[S ]. Then by Lemma 1(b) α +v = α is the CCC of Σ in G[S]. If the equality p = p +|α|-|α | also holds, by employing a counting argument similar to the previous one we can state that S is a feasible solution to Π j (Σ , α , β, π, p ). So we have a finite rhs in[START_REF] Aringhieri | Local Search Metaheuristics for the Critical Node Problem[END_REF] andf i (Σ, α, β, π, p) = k(S) = k(S ) + k v ≥ min {f j (Σ \ {v}, α , β, π, p ): α + v = α, p = p + |α|-|α |} + k v .Let the rhs of (6) exist, finite, and consider a solution S minimising the rhs. We define S = S andS = V i \ S = S ∪ {v}. Note that Σ = Σ \ {v} and Σ = Σ. If α is the CCC of Σ in G[S ], then by Lemma 1(b) α + v = α is the CCC of Σ in G[S]. Also, β is the CCC of Σ in G[ S]. It is easy to see that if p is the number of components in G[S ] then p = p + |α|-|α | is the number of components in G[S]. Thus, S is a feasible solution to Π i (Σ, α, β, π, p), f i is finite and

  α and β denote the CCCs of Σ and Σ in G[S ] and G[ S ], respectively. Also, let α and β denote the CCCs of Σ and Σ in G[S ] and G[ S ], respectively. By Lemma 2, α + α is the CCC of Σ in G[S], and β + β is the CCC of Σ in G[ S]. Hence α = α + α and β = β + β . Let π = #conn(G[ S ]), π = #conn(G[ S ]), p = |comp(G[S ])|, p = |comp(G[S ])|. We show now that if we also haveπ = #conn(G[ S]) = (π -β ) + (π -β ) + β , p = |comp(G[S])| = (p -|α |) + (p -|α |) + |α|,then S and S are indeed feasible solutions to Π i (Σ, α , β , π , p ) and Π i (Σ, α , β , π , p ), respectively. Let us consider the first equality. As observed in [2], a component of G[ S ] or G[ S ] that does not intersect Σ is also a component of G[ S] with a trivial intersection with Σ and vice versa. To compute π, we can sum the pairwise connectivity of the components in G[ S] that do not intersect Σ with the pairwise connectivity of the components in G[ S] that intersect Σ. The first term is given by (π -β ) + (π -β ) as the number of connected pairs in G[ S ] or G[ S ] belonging to components that intersect Σ are subtracted from the total number of pairs π and π . The second term is given by β as β is the CCC of Σ in G[ S]. A similar counting argument applies to p = (p -|α |)+(p -|α |)+|α| when set Σ and graphs G[S], G[S ] and G[S ] are considered.

Figure 4 :

 4 Figure 4: Example of a series-parallel instance for the Connected MinMaxC CNP over series-parallel graphs obtained by reduction from a Partition instance.

  3 but with π = |comp(G[ S])| and do not need to modify the definition of a CCC. For a start bag X i = {v} we now havef i (Σ, α, β, π, p) {v}, α = {({v}, 0)}, β = ∅, π = 0, p = 1 0 if Σ = ∅, α = ∅, β = {({v}, 0)}, π = 1, p = 0 +∞ in all other cases.We can then replace the recursive functions (5)-(7) respectively with:f i (Σ, α, β, π, p) = min {f j (Σ ∪ {v}, α , β, π, p): α -v = α} ∪ {f j (Σ, α, β , π, p): β -v = β}(18)f i (Σ, α, β, π, p) {f j (Σ \ {v}, α , β, π, p ):α + v = α, p = p + |α|-|α |} + k v (v ∈ Σ)min {f j (Σ, α, β , π , p):β + v = β, π = π + |β|-|β |}

f

  i (Σ, α, β, π, p) = min f i (Σ, α , β , π , p ) + f i (Σ, α , β , π , p ) -k(Σ): α + α = α, β + β = β, p + p -|α |-|α |+|α|= p, π + π -|β |-|β |+|β|= π

  1, it suffices to reduce the decision version of the Minimum Connected Vertex Cover problem to the decision version of Connected MaxNum CNP with unit deletion costs. Given a connected graph G and a number K, the decision version of the MinCVC asks whether there exists a connected set S that is a vertex cover of G and such that |S|≤ K . Given an instance of the MinCVC, we can straightforwardly construct an instance of the Connected MaxNum CNP with unit deletion costs, a deletion budget K and a minimum threshold n -K on the number of connected components. It is easy to check that if a Yes instance exists for the MinCVC with a solution S * with,|S * |≤ K, the number of connected components in G[V \ S * ] is n -|S * |≥ n -K.Hence, set S * constitutes also a solution of the corresponding instance of the Connected MaxNum CNP. Conversely, consider a Yes instance of the Connected MaxNum CNP with solution S * that induces a remaining graph with at least n -K components. If |S * |= K, clearly |S * | is also a connected vertex cover as each of the n -K components in G[V \ S * ] must have one node only. Suppose now that |S * |< K. Since each component in G[V \ S * ] must necessarily have at least one neighbour in S * , we can iteratively add nodes in S * by adding nodes from the connected components in G[V \ S * ] (with cardinality > 1) until again |S * |= K and ensuring that set S * is connected. Thus, a Yes instance of the Connected MaxNum CNP implies a Yes instance of the MinCVC, completing the reduction.

Start bag. The recursion for start bags is straightforward: we evaluate the possible removal of node v and consider the corresponding settings of Σ, α, β, π and p.

Forget bag. For a forget bag X i , we have V i = V j . First assume that the lhs of (5) exists and is finite. Then there exists an optimal set S for Π i (Σ, α, β, π, p) satisfying the requirements (i)-(iii). As v / ∈ X i , v is never included in Σ when X i is considered. We have either v ∈ S or v / ∈ S.

Case v ∈ S. This implies v / ∈ Σ for the child bag X j . Let Σ = Σ ∪ {v}, Σ = Σ; Σ , Σ form a partition of X j , and Σ ⊆ S ⊆ V j \Σ , Σ ⊆ S ⊆ V j \ Σ . Among all the potential CCCs β ∈ Γ( Σ ,

)|= p. Thus, S is a feasible solution to problem Π j (Σ, α, β , π, p), min{f j (Σ, α, β , π, p: β -v = β} exists, finite, and

exists, finite, and

This analysis shows that a finite f i (Σ, α, β, π, p) is not smaller than the rhs of [START_REF] Aringhieri | A general Evolutionary Framework for different classes of Critical Node Problems[END_REF]. Now assume the rhs of (5) exists, finite, and is given by either min{f j (Σ, α, β , π, p: β -v = β} (Case (1)) or min{f j (Σ ∪ {v}, α , β, π, p: α -v = α} (Case (2)).

Case [START_REF] Addis | Hybrid Constructive Heuristics for the Critical Node Problem[END_REF]. Assume that min{f j (Σ, α, β , π, p: β -v = β} = k(S) is finite for some S, and let Σ = Σ∪{v} and Σ = Σ as v / ∈ Σ. By definition of f j , we have

Hence S is also a feasible solution to Π i (Σ, α, β, π, p), f i is finite and

Hence S is a feasible solution to Π i (Σ, α, β, π, p), f i is finite and

The previous inequalities show that f i (Σ, α, β, π, p) is also bounded from above by a finite rhs of [START_REF] Aringhieri | A general Evolutionary Framework for different classes of Critical Node Problems[END_REF]. Putting all the results together proves that equality (5) holds for a forget bag.

Introduce bag. We have v ∈ X i and v / ∈ X j . We distinguish two cases for bag

Case v / ∈ Σ. Let f i (Σ, α, β, π, p) exist, finite, and S be the optimal solution to Π i (Σ, α, β, π, p). Considering the child bag X j , we define S = S \ {v}, S = V j \ S = S. By the definition of f i (Σ, α, β, π, p),

Appendix B Extensions to the Connected MinMaxC CNP

Many results obtained for the Connected Pairwise CNP can be extended to the MinMaxC CNP as well. We extend here the analysis of the complexity over graphs with bounded treewidth, trees, and series-parallel graphs.

B.1 NP-hardness on biconnected planar bipartite graphs

We can use the reasonings in the proof of Proposition 1 to show that the unweighted Connected MinMaxC CNP provides a solution to the MinCVC when the maximum cardinality of the remaining components must be one at most. We state the following proposition.

Proposition 7:

The decision version of the Connected MinMaxC CNP is strongly NP-complete in biconnected planar bipartite graphs of maximum degree 4, even with unit node weights and unit deletion costs.

B.2 Graphs with bounded treewidth

We can modify the DP algorithm of Section 3 to prove similar results for the Connected MinMaxC CNP where the objective is to minimise the weight of the heaviest component in G[ S]. In order to

Appendix C Extensions to the Connected MaxNum CNP

In this section, we present the results for the Connected MaxNum CNP. We first show the NP-hardness of the problem on biconnected planar bipartite graphs. Then, we illustrate our results on graphs with bounded treewidth. No additional meaningful findings can be derived for the Connected MaxNum CNP over trees or series-parallel graphs with respect to the more general results obtained in graphs with bounded treewidth.

C.1 NP-hardness on biconnected planar bipartite graphs

We can state the following proposition for the Connected MaxNum CNP: