Galaxy cutsets in graphs

Abstract

Given a network G=(V,E), we say that a subset of vertices S⊆V has radius r if it is spanned by a tree of depth at most r. We are interested in determining whether G has a cutset that can be written as the union of k sets of radius r. This generalizes the notion of k-vertex connectivity, since in the special case r=0, a set spanned by a tree of depth at most r is a single vertex.

Our motivation for considering this problem is that it constitutes a simple model for virus-like malicious attacks on G: An attack occurs at a subset of k vertices and begins to spread through the network. Any vertex within distance r of one of the initially attacked vertices may become infected. Thus an attack corresponds to a subset of vertices that is spanned by k trees of depth at most r. The question we focus on is whether a given network has a cutset of this particular form.

The main results of this paper are the following. If r=1, an attack corresponds to a subset of vertices which is the union of at most k stars. We call such a set a galaxy of order k. We show that it is NP-hard to determine whether a given network contains a cutset which is a galaxy of order k, if k is part of the input. This is in stark contrast to the case r=0, since testing whether a graph is k-vertex connected can be done in polynomial time, using standard maxflow-mincut type results.

On the positive side, testing whether a graph can be disconnected by a single attack (i.e. k=1) can be done efficiently for any r. Such an attack corresponds to a single set of vertices spanned by a tree of depth at most r. We present an O(rnm) algorithm that determines if a given network contains such a set as a cutset.