Graph fragmentation problem: analysis and synthesis

• DOI: http://doi.org/10.1111/itor.12562
• Author: Franco Robledo,Graciela Ferreira,Juan Piccini,Pablo Romero,Manuel Aprile,Natalia Castro
• Date: 01 January 2019
• Published date: 01 January 2019

Intl. Trans. in Op. Res. 26 (2019) 41–53

DOI: 10.1111/itor.12562

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Graph fragmentation problem: analysis and synthesis

Manuel Aprilea,∗, Natalia Castrob, Graciela Ferreirab, Juan Piccinib,

Franco Robledoband Pablo Romerob

aDISOPT, ´

Ecole Polytechnique F´

ed´

erale de Lausanne, Station 8, CH-1015, Lausanne, Switzerland

bLaboratorio de Probabilidad y Estad´

ıstica, Facultad de Ingenier´

ıa, Universidad de la Rep´

ublica,

Julio Herrera y Reissig 565, PC 11300, Montevideo, Uruguay

E-mail: manuel.aprile@epfl.ch [Aprile]; ncastro@fing.edu.uy[Castro]; gferreira@fing.edu.uy [Ferreira];

piccini@fing.edu.uy [Piccini]; frobledo@fing.edu.uy [Robledo]; promero@fing.edu.uy [Romero]

Received 7 October 2017; receivedin revised form 4 April 2018; accepted 30 April 2018

Abstract

Vulnerability metrics play a key role in the understanding of cascading failures and target/random attacks to

a network. The graph fragmentation problem (GFP) is the result of a worst-caseanalysis of a random attack.

We can choose a fixed number of individuals for protection, and a nonprotected target node immediately

destroys all reachable nodes. The goal is to minimize the expected numberof destroyed nodes in the network.

In this paper,we address the GFP by several approaches: metaheuristics,approximation algorithms, polytime

methods for specific instances, and exact methods for small instances. The computational complexity of

the GFP is included in our analysis, where we formally prove that the corresponding decision version of

the problem is NP-complete. Furthermore, a strong inapproximability result holds: there is no polynomial

approximation algorithm with factor lower than 5/3, unless P=NP. This promotes the study of specific

instances of the problem fortractability and/or exact methods in exponential time. As a synthesis, wepropose

new vulnerability/connectivitymetrics and an interplay with game theory using a closely related combinatorial

problem called component order connectivity.

Keywords: vulnerability metrics; graph fragmentation problem; computational complexity; approximation algorithms;

metaheuristics; game theory

1. Introduction

Modern connectivity theory is largely concerned with social networks analysis, disaster manage-

ment, and business models in telecomunications. In the classical literature, we find minimum-cost

k-node-connected spanning topologies as a reference network design model (Monma et al., 1990;

Stoer, 1993). This is a notion of survivability under a fixed number of component failures of a

∗Corresponding author.

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.