Galaxy cutsets in graphs

Nicolas Sonnerat () and Adrian Vetta ()
Additional contact information
Nicolas Sonnerat: McGill University
Adrian Vetta: McGill University

Journal of Combinatorial Optimization, 2010, vol. 19, issue 3, No 9, 415-427

Abstract: 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.

Keywords: Graph connectivity; Star-cutsets; Complexity (search for similar items in EconPapers)
Date: 2010
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-009-9258-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:19:y:2010:i:3:d:10.1007_s10878-009-9258-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-009-9258-1

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().