Weakening Covert Networks by Minimizing Inverse Geodesic Length

1 Introduction

Strategic aspects of network analysis is an important research area in many fields including AI (see, e.g., [Michalak et al., 2017]). Within this area, pinpointing the most important nodes or edges is a fundamental problem [Michalak et al., 2013; Chen et al., 2012; Zheng et al., 2011]. Applications include disrupting an epidemic network (see, e.g., [Kov´acs and Barab´asi, 2015]), weakening a terrorist network (see, e.g., [Michalak et al., 2013]), finding the most critical or vulnerable nodes (see, e.g., [Holme et al., 2002]) and reducing reachability on a graph for network security (see, e.g., [Zheng et al., 2011]). The problem is relevant to various fields and sectors such as epidemiology, sociology, physics, security and logistics. We focus on the problem of weakening a covert network by identifying and eliminating the individuals who are most critical for a high performance of these networks. The problem has been considered both in social network analysis and artificial intelligence (see, e.g., [Carley et al., 2003; Lindelauf et al., 2013; Michalak et al., 2013]). A common practice among these studies is to use a heuristic to rank the vertices by their importance (see, e.g, [Michalak et al., 2013; Michalak et al., 2015; Szczepanski et al., 2015]). In order to measure the quality of their pick they either use expert domain knowledge on the importance of vertices in the network or turn to widely used network performance measures like component order connectivity (size of the largest connected component) [Gross et al., 2013; Drange et al., 2016] and inverse geodesic length (IGL; sum of the inverse distances between all pairs of vertices). Formally, IGL(G) = ∑{u,v}⊆V,u̸=v 1 d(u,v) . The average inverse geodesic length (AIGL) of G is the inverse geodesic length of G normalized by the number of vertex pairs. Formally, AIGL(G) = 2 n(n-1) · IGL(G). We opt to quantify network performance by IGL; the motivation for that is two-fold. Firstly, AIGL has been frequently used in the literature as a global measure of the connectivity or robustness of a network. It has been used to examine network vulnerability [Dagon et al., 2008; Holme et al., 2002] and the effect of critical nodes [Barab´asi and Albert, 1999] in the network security domain. It has also been used to identify influential nodes in a social network [Morone and Makse, 2015]. Game-theoretic values and centrality measures, such as the Shapley value and betweenness centrality of the nodes, have been used as heuristics to delete nodes with large impact on network performance [Holme et al., 2002; Amer and Gim´enez, 2004; Michalak et al., 2015; Szczepanski et al., 2015]. In particular, Szczepanski et al. [2015] delete the nodes with the highest Shapley value as a heuristic to decrease the IGL. Secondly, performance measures like component order connectivity and diameter prove ineffective on dense graphs. On the contrary, IGL remains effective in identifying critical nodes irrespective of the input graph structure. Surprisingly, despite its widespread use as a network performance measure, the optimization problem with respect to IGL has not been examined previously. We consider the vertex deletion optimization problem corresponding to IGL:

MINIMIZE IGL (MINIGL)

Input: A graph G, an integer k, and a target inverse geodesic length T .

Question: Does there exist X ⊆ V (G), such that |X| ≤ k and IGL(G-X) ≤ T?

The problem is NP-complete and we show that it remains NP-complete on several graph classes that naturally occur in application domains [Belik, 2016; Borgatti, 2012]. Our main focus is a parameterized complexity analysis of the problem.

Our Results. We observe that, for T = 0, MINIGL is equivalent to VERTEX COVER and it is therefore para-NP-hard for parameter T. For parameter k, we give reductions from CLIQUE on regular graphs to show that MINIGL is W[1]-hard and NP-complete, even when restricted to bipartite and split graphs. For parameter k + T, we give a kernel of size O(k2 + T), which establishes that the problem is FPT for this combined parameter. Next, we consider structural parameters. The vertex cover number is among the most widely studied structural parameters [Fellows et al., 2008; Fomin et al., 2014], neighborhood diversity [Lampis, 2012; Ganian, 2012] is a parameter that generalizes vertex cover to dense graphs, and Ganian [2015] recently proposed an alternative generalization, the twin cover number, that still preserves some of the nice properties of the vertex cover number. Our main result is that MINIGL is FPT parameterized by twin cover number. Since a vertex cover is a twin cover, this implies that MINIGL is also FPT parameterized by vertex cover number. However, we give a faster algorithm for this parameter. We also provide an FPT algorithm parameterized by neighborhood diversity and the deletion budget combined.

Our choice of parameters is motivated by real-world datasets. Table 1 shows five representative datasets of covert networks from [UCINET Software, 2017] with some parameter values. Even on this small sample, we can already see the importance of considering multiple parameters. While, for the FIFA network, both the vertex cover number and the neighborhood diversity are large, the smallest twin cover contains fewer than 10% of the vertices. For instances where all parameters are large, our current best approach will turn out to be a simple FPT algorithm parameterized by ω+k.

Our key take-home message is that minimizing IGL is computationally hard even for very restricted graph classes and that a parametrized complexity approach by identifying and exploiting suitable parameters promises to be fruitful.

2 Preliminaries

Let G = (V,E) be an undirected, simple graph. We denote the set of vertices and edges in G as V (G) and E(G), respectively, with n = V and m = E. For graph terminologies not defined here we refer to [Diestel, 2010]. Let u, v ∈ V with u ̸= v. An edge xy is incident to v if v ∈ {x, y}. We say that u and v are adjacent or neighbors if uv ∈ E(G). We denote the neighborhood of v, i.e., the set of vertices adjacent to v, as N(v). The closed neighborhood of v is N[v] = N(v) ∪ {v}. The closed neighborhood of a vertex set S is N[S] = ⋃v∈S N[v], and its open neighborhood is N(S) = N[S] \ S. A path between u and v is an alternating sequence of vertices and edges that starts with u and ends with v, with each edge in the path being adjacent to the preceding and succeeding vertex, and each vertex occurring at most once in the sequence. The length of a path is its number of edges. The distance between u and v, denoted by d(u, v), is the length of a shortest path between u and v. The ith neighborhood of a vertex v is the set of vertices at distance i from v and is denoted by N i (v). If there is no path between u and v then their distance is infinite. A pair of vertices at finite distance is connected. Let S ⊆ V . A graph induced on S is denoted as G[S], i.e., V (G[S]) = S and E(G[S]) = {uv ∈ E : u, v ∈ S}. Similarly, we denote by G - S the graph G[V \ S]. A connected component of G is a maximal subgraph of G where each vertex pair is connected. A d-regular graph is a graph where each vertex has d neighbors. A bipartite graph is a graph whose vertex set can be partitioned into two independent sets. A split graph is a graph whose vertex set can be partitioned into a clique K and an independent set I. Such a partition (K, I) is known as a split partition. Throughout this article we assume that K is a maximal clique in a given split partition (K, I).

Two vertices u and v are twins if N(u) \ {v} = N(v) \ {u}. Vertices u, v are true twins if they are twins and uv ∈ E(G). A set of vertices C ⊆ V (G) is a twin cover of G, if for every edge xy ∈ E(G), either xy is incident to a vertex in C or x and y are true twins [Ganian, 2015]. A graph G has neighborhood diversity ω, if there exists a partition of V (G) into at most ω sets, such that all the vertices in each set are twins; such a partition is called the neighborhood partition of G and can be computed in polynomial time [Lampis, 2012].

A parameterized decision problem Π is in FPT (Fixed Parameter Tractable), if there is an algorithm solving any instance x with parameter k in time f (k)·|x|c , where f (k) is a computable function of k and c is a constant. A parameterized reduction from a parameterized decision problem Π1 to a parameterized decision problem Π2 is an algorithm, which, for any instance I of Π1 with parameter k produces an equivalent instance I ′ of Π2 with parameter k′ such that there exists a computable function f such that k′ ≤ f(k) and the running time of the algorithm is f(k) · |I|O(1) . W[1] is a class of parameterized decision problems closed under parameterized reductions. W[1]-hard problems are considered unlikely to be in FPT [Downey and Fellows, 2013]. A para-NP-hard problem is NP-hard even for constant values of the parameter. We refer to [Cygan et al., 2015] for a detailed exposition of parameterized complexity.

3 Intractability for Parameter T

In this section we consider the parameterized complexity of MINIGL when parameterized by the target inverse geodesic length T . We show that MINIGL is NP-complete, even when T = 0, by observing that it is equivalent to the well-known NP-complete VERTEX COVER problem [Karp, 1972], where for a given graph G and integer k, the question is whether k vertices can be deleted from G to make the graph edgeless. Since MINIGL remains NP-complete for a constant value of T , MINIGL is para-NP-hard when parameterized by T .

Theorem 3.1. MINIGL is NP-complete and para-NP-hard for parameter T .

4 Intractability for Parameter k

Given the previous hardness result for general graphs, we consider MINIGL on special classes of graphs for which VERTEX COVER can be solved in polynomial time, namely split graphs and bipartite graphs. We also consider another natural parameter, namely the size of the solution k. We begin with a proof that for a split graph with vertex partition (K, I), there is an optimal solution for MINIGL containing only vertices from K. It can be proved by an exchange argument replacing a vertex from I by a vertex from K and analyzing the impact on the IGL.

Lemma 4.1. For each subset of vertices X ⊆ V (G) in a split graph G = (K, I, E), there is a subset of vertices Y ⊆ K with |Y | ≤ |X|, such that IGL(G- Y ) ≤ IGL(G-X).

We now consider MINIGL on split graphs and call this problem SPLIT-MINIGL. We show that SPLIT-MINIGL is NP-complete and W[1]-hard for parameter k. We provide a parameterized reduction from the CLIQUE problem on regular graphs, where, given a regular graph G and an integer k, the question is whether G has a clique of size k. The restriction of CLIQUE to regular graphs is known to be NP-complete and W[1]-hard for parameter k [Cai, 2008].

Theorem 4.2. SPLIT-MINIGL is NP-complete and W[1]-hard for parameter k.

Proof. For a CLIQUE instance (G = (V, E), k) with n = |V | and m = |E|, where G is d-regular with d > 2, we obtain a SPLIT-MINIGL instance (G′ , k, T) as follows. The vertex set of G′ consists of the clique K′ = V and the independent set I ′ = E. Set E(G′ ) = {x1x2 : x1, x2 ∈ V } ∪ {xe : x ∈ e ∈ E}. See Fig. 1b. We retain the value of k and set T = T ( k(k-1) 2 , kd-k(k -1), m+ k(k-1) 2 -kd), where

is the IGL of a graph obtained from G′ by deleting k vertices from K′ so that I ′ has βi vertices of degree i. We now show that (G′ , k, T ) is a Yes-instance for SPLIT-MINIGL iff (G, k) is a Yes-instance for CLIQUE.

Suppose (G′ , k, T) is a Yes-instance for SPLIT-MINIGL and there is a solution X′ ⊆ V (G′ ) with |X′ | = k. By Lemma 4.1 we may assume that X′ ⊆ K′ . Let G′′ = G′-X′ . Let αi denote the number of vertices in I ′ that have degree i in G′′ . We have, IGL(G′′ ) = T(α0, α1, α2). Let us now determine the values of α1 and α2 in terms of α0:

Notice that by (1) and (2), the value of IGL(G′′ ) = T(α0, α1, α2) decreases with increasing α0. In other words, the inverse geodesic length is minimized when the number of isolated vertices is maximized. We observe that IGL(G′′ ) ≤ T only if α0 = k(k-1) 2 . But this is the maximum number of vertices that can be isolated by deleting k vertices from G′ , meaning that X′ forms a clique of size k in G. Hence, (G, k) is a Yes-instance for CLIQUE.

Conversely, suppose that (G, k) is a Yes-instance for CLIQUE and there exists a solution X ⊆ V (G), with |X| = k, then, deleting X from G′ isolates k(k-1) 2 vertices in I ′ . Therefore, IGL(G′ - X) ≤ T. Thus, (G′ , k, T) is a Yes-instance for SPLIT-MINIGL.

We further consider MINIGL on bipartite graphs and call this problem BIPARTITE-MINIGL. We show that BIPARTITE-MINIGL remains NP-complete and W[1]-hard when parameterized by k. Again, we provide a parameterized reduction from CLIQUE on regular graphs.

Theorem 4.3. BIPARTITE-MINIGL is NP-complete and W[1]-hard for parameter k.

Proof. Consider an instance (G, k) of CLIQUE, where G is a d-regular graph, d > 2, with n vertices and m edges. We construct an instance (G′ , k, T) for BIPARTITE-MINIGL. We construct the vertex set V (G′ ) with a bipartition (A,B), where A = V (G) and B = B1 ∪ B2 with Bi = {ei : e ∈ E(G)}. The edge set of G′ is E(G′ ) = {xe1 : e1 ∈ B1, x ∈ e} ∪ {xe2 : x ∈ A, e2 ∈ B2}. In this way each vertex in A has degree d +m, each vertex in B1 has degree 2, and each vertex in B2 has degree n (see Fig. 1c). We retain the value of k and set T = T ( k·(k-1) 2 ), where

Since vertices in A have much higher degrees than vertices in B and they also occur on paths between vertices in B, one can show that for each subset S ⊆ V (G′ ), there is a subset S′ ⊆ A, such that IGL(G′ - S′ ) ≤ IGL(G′ - S). We now show that (G′ , k, T) is a Yes-instance for BIPARTITE-MINIGL iff (G, k) is a Yes-instance for CLIQUE.

Suppose that (G′ , k, T) is a Yes-instance for BIPARTITE-MINIGL and there is a solution X′ ⊆ A with |X′ | = k. Let G′′ = G′ -X′ and α0 be the number of isolated vertices in G′′ . Then, IGL(G′′ ) = T(α0). Note that by (3), the value of IGL(G′′ ) decreases with increasing α0.

In other words, minimizing IGL is equivalent to maximizing the number of isolated vertices. We have that IGL(G′′ ) ≤ T only if α0 = k·(k-1) 2 . But this is the maximum number of vertices that can be isolated by deleting k vertices from G′ . Thus, there are k·(k-1) 2 isolated vertices in B1 and X′ forms a clique in G. Hence, (G, k) is a Yes-instance for CLIQUE.

Conversely, suppose that (G, k) is a Yes-instance of the CLIQUE problem and there exists a solution X ⊆ V (G), with |X| = k. But then deleting X from A isolates k·(k-1) 2 vertices in B1. Therefore, IGL(G′ - X) ≤ T. Hence (G′ , k, T) is a Yes-instance for BIPARTITE-MINIGL.

5 Polynomial Kernel for Parameter k +T

Here we prove that MINIGL is FPT for parameter k + T by providing a polynomial-time preprocessing algorithm which produces an equivalent instance of MINIGL of size O(k2 + T). In the language of parameterized complexity, we design a kernel of size O(k2 +T ). The following reduction rules are applied in the order we state them here.

Reduction Rule 5.1 (Isolated Vertices). If there exists a vertex x ∈ V (G) such that |N(x)| = 0, then delete x.

For the next two reduction rules, let q := 2√ 9 16 + T - 3 2 , which is the positive solution for the equation T = q+ q(q-1) 4 . Reduction Rule 5.2 (High Degree Vertices). If there exists a vertex x ∈ V (G) such that |N(x)| > q + k, then remove x from G and set k := k - 1.

Reduction Rule 5.3 (Bounded Edge Set). If |E(G)| > T + k(q + k), then return NO.

The correctness proof for these rules is straightforward and we skip it here due to space constraints.

Theorem 5.4. MinIGL has a kernel of size O(k2 + T ).

Proof. Given an instance (G, k, T) of MINIGL by applying reduction rules 5.1-5.3 exhaustively, we obtain an instance (G′ , k′ , T ) where number of edges in G′ is at most T +k(q+ k) = O(T +k(√T +k)) = O(k2 +T ). Since degree of each vertex is at least 1, G′ has O(k2 + T) vertices.

6 FPT for Parameter Twin Cover Number

In this section we consider the twin cover number of the graph as a parameter. Although, the TWIN COVER problem (given a graph G and an integer k, does G have a twin cover of size at most k?) is NP-complete [Ganian, 2015], a smallest twin cover can be computed in time O(|E| + l · |V | + 1.2738l ), where l is the twin cover number [Ganian, 2015]. So, we may assume that the input contains a smallest twin cover of G.

6.1 Description of the Algorithm

Let (G, k, T ) be an instance of MINIGL and C be a smallest twin cover of G with |C| = l. Let Pc be a partition of V (G) \ C into a set of equivalence classes {P1, P2, . . . , Pq}, such that, for any two vertices u and v, if N(u) ∩ C = N(v) ∩ C, then u and v belong to the same equivalence class. This implies that |Pc| ≤ 2l , as there is at most one equivalence

Input

: A graph G, an integer k, a target IGL T , and a twin cover C of G

Parameter: l = |C|

Output

: "yes" if (G, k, T) is a Yes-instance for MINIGL, and "no" otherwise

• 1 Guess which subset C ′ ⊆ C to delete;
• 2 Define Pc for V (G) \ C;
• 3 Guess which equivalence classes to delete entirely;
• 4 Guess the number of vertices k′ ≤ k to delete from equivalence classes in P ∗ c ;
• 5 Greedily delete k′ vertices fromP ∗ c ;
• 6 Guess which vertices from the equivalence classes in Ps to delete;
• 7 if k ≤ l then
• 8 Guess the number of vertices to delete from each equivalence class in Pl and greedily delete these vertices;
• 9 else return no;
• 10 if IGL(G) ≤ T then return yes;
• 11 return no;

Algorithm 1: MINIGL parameterized by the size of a twin cover of the input graph.

class for each subset of C. Ganian [2015] observed that G[V (G) \ C] is a disjoint union of cliques. In particular, for each Pi ∈ Pc, G[Pi] is a disjoint union of cliques. Let the largest clique in Pi be denoted as Zmax(G[Pi]). Let {P ∗ c ,Ps,Pl} be a partitioning of the equivalence classes in Pc as follows: an equivalence class Pa ∈ Pc belongs to P ∗ c if there is no path from a vertex of Pa to a vertex in another equivalence class from Pc; an equivalence class Pb ∈ Pc \P ∗ c belongs to Ps, if |Pb| ≤ 2l2 + l; lastly, Pl = Pc \ (P ∗ c ∪Ps). Using these notations, we outline Algorithm 1.

In the description of the algorithm, when we state that the algorithm guesses an object, this means that the algorithm branches into all possible values that this object can take. In Step 1, the algorithm guesses which subset C ′ ⊆ C to delete, meaning that it branches into one subproblem for each C ′ ⊆ C and in this subproblem, all deletion sets containing C ′ but no other vertex from C are considered. Then, C ′ is included in the solution and k is decreased by |C ′ |. From this point onward, we set C := C \ C ′ and l := |C|. In Step 2, we define a set of equivalence classes Pc on V (G) \ C as described earlier. In Step 3, the algorithm guesses which equivalence classes to delete entirely. In Step 4, the algorithm guesses the number of vertices k′ that are deleted fromP ∗ c . In Step 5, the algorithm performs k′ iterations. In each iteration, for each equivalence class Pa ∈ P ∗ c , it picks an arbitrary vertex v ∈ Zmax(G[Pa]) and computes IGL(G - v). It then greedily deletes one of those vertices whose deletion decreases the IGL the most. In Step 6, for each vertex in every equivalence class in Ps, the algorithm guesses whether to include it in the solution. In Step 7, if the deletion budget exceeds the size of the remaining twin cover C then the algorithm returns "no", otherwise it performs Step 8. In Step 8, for each equivalence class Pi ∈ Pl, the algorithm guesses the number of vertices to be deleted from Pi. For each such guess, the corresponding number of vertices is iteratively and greedily deleted from the largest remaining clique Zmax(G[Pi]). In Step 10, the algorithm checks if the graph G obtained by deleting k vertices has the desired IGL. If so, it returns "yes" otherwise it returns "no".

6.2 Correctness

In this section we prove that the algorithm described in the previous section correctly solves MINIGL. Clearly, Steps 1-3 and 6 are exhaustive while Steps 4, 7, 10, and 11 are trivial. In Step 5 and 8, when the algorithm deletes a vertex from an equivalence class Pi, it greedily chooses a vertex from the largest clique Zmax(G[Pi]) in Pi. This greedy choice can be shown to be optimal by using the properties of twin covers.

Lemma 6.1. For a graph G, a twin cover C of G, an equivalence class Px ∈ Pc defined over V (G) \C (as defined in Section 6.1) and a pair of vertices x, y, where x ∈ Px and y ∈ Zmax(G[Px]), we have that IGL(G-y) ≤ IGL(G-x).

Apart from the greedy selection of vertices from each equivalence class in Pl, the rest of Step 8 is exhaustive. It remains to show that Step 9 is sound, i.e., if we reach this step with k > l, and there is a set of vertices S such that |S| ≤ k, S ∩ C = ∅ and IGL(G - S) ≤ T, then there is another set S∗ such that |S∗ | ≤ k and IGL(G- S∗ ) ≤ T, but S∗ ∩C ̸= ∅. Therefore, the current choice for C ′ can be ignored. Before presenting the formal argument we make an observation that will help us prove the correctness of Step 9.

Observation 6.2. In a connected graph with twin cover number l, any two vertices are at distance at most 2l.

Claim 6.3. Let G be the graph obtained by performing Steps 1 to 6 in Algorithm 1, with twin cover C and a set of equivalence classes Pl. If the algorithm reaches Step 9 with k > l, and there is a set of vertices S such that |S| = k, S ∩C = ∅ and IGL(G-S) ≤ T , then there is a set S∗ such that |S∗ | = k and IGL(G - S∗ ) ≤ T , but S∗ ∩ C ̸= ∅.

Proof. Let S ⊆ (V (G) \C) such that |S| = k and IGL(GS) ≤ T. Let G′ be a connected component of G with twin cover C ′ ⊆ C and a set of equivalence classes P ′ l ⊆ Pl such that |S∩V (G′ )| ≥ | ⋃Pi∈P ′ l N(Pi)|. It is easy to see that such a connected component G′ always exists, as k > l. Let P ′ l = {Q1,Q2, . . . ,Qq}, where q ≤ 2l and |Qi| ≥ |Qi+1|. Let S′ = V (G′ ) ∩ S. We show that if k > l, there exist a set S∗ with |S∗ | = |S′ |, such that IGL(G′ -S∗ ) ≤ IGL(G′ -S′ ) and S∗ ∩ C ′ ̸= ∅. Let r be the smallest index such that for Q = Q1 ∪ Q2 ∪ Q3 . . . ∪ Qr, |Q ∩ S′ | ≥ | ⋃ri=1 N(Qi)|. Since |S′ | ≥ |N(Q)|, we can always find such an index r. Let Pr = {Q1,Q2, . . . ,Qr}. We order the vertices in N(Q) in descending order of the size of their neighboring equivalence class (if a vertex is adjacent to more than one equivalence class we order it with respect to the largest equivalence class it is adjacent to, and ties are broken arbitrarily). Denote this ordering by π. For 1 ≤ i ≤ r, denote DQi = Qi ∩ S′ . For 1 ≤ i < r, let ki = |DQi | while kr = |N(Q)| - ∑r-1 i=1 ki. To obtain the set S∗ , we start from S′ and then replace each set DQi ⊆ S′ with a set of vertices DNi ⊆ N(Q) with |DNi | = ki. For each i from 1 to r, the vertices composing DNi are picked sequentially from N(Q) according to π. Accordingly, DNi ⊆ (N(Q1) ∪ N(Q2) ∪ . . . ∪ N(Qi)) and each vertex u ∈ N(Q) belongs to exactly one such set DNi . Figure 2 depicts G′ and highlights each DQi along with its corresponding DNi . When deleting a vertex set X from G′ , we say that the contribution of a vertex v ∈ X is ∑u∈X,u̸=v 1 2·d(u,v) + ∑u∈V (G′ )\X 1 d(u,v) . In other words, for a vertex pair (u, v), we attribute 1 d(u,v) if u /∈ X, but only half of that quantity if u ∈ X. Thus, the contributions of all vertices in X equals the decrease in IGL when X is deleted.

Let us now compare the mutually exclusive impact of deleting DQi and DNi . Note that no remaining equivalence class is deleted entirely, due to Step 3. In particular, this means that all vertices in C remain at the same distance.

First let us consider the impact of deleting the set of vertices DQi . We delete (|Qi| - 1) + (|Qi| - 2) + . . . + (|Qi| - ki) paths of length one that connect the vertices in DQi to each other and to the remaining vertices in Qi. Note that ∑ki j=1 (|Qi| - j) ≤ |DQi | · |Qi|. Moreover, we know that |N(DQi ) ∩ C| ≤ |N(Q)|. Therefore, by deleting DQi we delete at most |DQi | · |N(Q)| paths of length one that connect vertices in N(Q) to the vertices in DQi . Overall, the exclusive impact of deleting DQi is at most |DQi | · |Qi| +

|DQi | · (|N(Q)|). Alternatively, we consider deleting the set of vertices DNi ⊆ N(Q). Since each vertex in DNi has at least |Qi| neighbors in Q (given that DNi ⊆ (N(Q1) ∪ N(Q2) . . . ∪N(Qi)) and |Qi| ≥ |Qi+1|), by deleting the set of vertices DNi , we delete at least |DNi | · |Qi| paths of length one. By Observation 6.2 we know that for any pair of vertices u, v ∈ N(Q), d(u, v) ≤ 2l. Therefore, for each vertex x ∈ DNi , we attribute at least half of 1 2l to x for each vertex y ∈ N(Q)\{x}. Therefore, the contribution of DNi is at least |DNi |·(|N(Q)|-1) 4l for their distances to the vertices in N(Q). So far, for the deletion of DNi we have counted an exclusive impact of at least |DNi | · |Qi| + |DNi |·(|N(Q)|-1) 4l . Observe that G′ contains at least two equivalence classes (connected components with one equivalence class are handled in Step 5 of the algorithm). Since we replace each DQi by DNi and N(Q) = ⋃ri=1 DNi , we disconnect all the equivalence classes in Pr from each other and from V (G′ ) \ Q. We know that the distance between any two equivalence classes is at most 2l. Therefore, for a pair of equivalence classes (Qi, Qj) where Qj ∈ (Pl \ {Qi}), we delete |Qi| · |Qj| paths of length at most 2l. However |DQi | · |Qj| + |DQj | · |Qi| - |DQi | · |DQj | of these paths are also deleted when we delete DQi ∪DQj . Hence, the exclusive impact of deleting vertices in DNi is at least (|Qi|-|DQi |)·(|Qj|-|DQj |) 4l for these paths between equivalence classes. Therefore, in order to show that IGL(G′ -S∗ ) ≤ IGL(G′ -S′ ), it suffices to show that

We know that size of both equivalence classes |Qi|, |Qj| is at least 2l2 + l. Also, we know that |DQi | = |DNi | ≤ l and |DQj | ≤ l. Similarly, we know that |N(Q)| ≤ l. Thus, replacing the values in equation (4) we get that l3 ≥ 4l2-l+1 4 ., which holds for any l ≥ 1. This proves that IGL(G′ -S∗ ) ≤ IGL(G′ -S′ ). Moreover, |S∗ | = |S′ | and S∗ ∩C ′ ̸= ∅.

6.3 Running Time

By considering the number of choices in each guessing step, and computing the IGL of a graph using a polynomial-time algorithm solving ALL-PAIRS SHORTEST PATH [Thorup, 1999], one can upper bound the running time of the algorithm by 2l · 22l · nO(1) · 22l ·(2l2+l) · (l + 1)2l . More concisely, its running time is 2O(2l ·l2 ) · nO(1) .

Theorem 6.4. MINIGL is FPT when parameterized by the twin cover number.

7 Faster Algorithm for Parameter Vertex Cover Number

The previous result implies that MINIGL is FPT when parameterized by the vertex cover number of the input graph. Here, we give a faster algorithm for this parameter.

Theorem 7.1. MINIGL can be solved in time 2O(l2 ) · nO(1) , where l is the vertex cover number of the input graph.

Proof. Let (G, k, T) be an input for MINIGL. A smallest vertex cover S for G can be computed in 1.2738l · nO(1) time [Chen et al., 2010]. Let I = V (G) \ S and note that I is an independent set. Let Ic = {I1, I2, ..., Iq} be a set of equivalence classes partitioning I such that two vertices from I belong to the same equivalence class if they have the same neighborhood in C. Thus, q ≤ 2l . Note that if k ≥ l, we can choose X = S as IGL(G - S) = 0. Now we consider the case when k < l. First observe that for all u, v ∈ Ii, IGL(G - u) = IGL(G - v). Using this fact, we define a branching algorithm that branches into at most (2l + l) subinstances to choose a vertex from S or an equivalence class. In a subinstance, the algorithm deletes the chosen vertex from S or an arbitrary vertex from the chosen equivalence class, and k decreases by one. The resulting search tree has size at most (2l + l)k ≤ (2l + l)l .

8 FPT for Parameter ω + k

We now outline an algorithm for MINIGL parameterized by the neighborhood diversity and deletion budget combined. Although simple, it is of practical interest as it is never asymptotically slower than a brute-force nk+O(1) approach.

Theorem 8.1. MINIGL can be solved in time ωk · nO(1) , where ω is the neighborhood diversity of the input graph.

Proof. Let (G, k, T) be an instance of MINIGL and ω be the neighborhood diversity of G. Let Vd = {V1, V2, · · · , Vω} be the neighborhood partition of G. Let u, v ∈ Vi, by definition of neighborhood partition, N(u) = N(v), hence IGL(G - u) = IGL(G - v). Considering this observation, we define a branching algorithm that branches on each part Vi ∈ Vd and deletes a vertex arbitrarily from the selected part. Since we delete k vertices the branching tree has depth k. Consequently, the algorithm runs in time ωk · nO(1) .

9 Future Directions

Our results point to natural future directions. Besides vertex deletion as destructive action, other actions are of interest, e.g., removing edges or decreasing the weights of edges. Structural parameters such as treewidth, cliquewidth, and feedback vertex set number are also of interest, as well as approximation algorithms. But the most pressing question that we leave open is the complexity of MINIGL on trees.

Acknowledgements

Gaspers is the recipient of an Australian Research Council (ARC) Future Fellowship (FT140100048) and acknowledges support under the ARC's Discovery Projects funding scheme (DP150101134). Aziz is supported by a Julius Career Award.