Abstract / Description of output
Motivated by applications in network epidemiology, we consider the problem
of determining whether it is possible to delete at most k edges from a given input
graph (of small treewidth) so that the resulting graph avoids a set F of forbidden
subgraphs; of particular interest is the problem of determining whether it is possible to delete at most k edges so that the resulting graph has no connected component of more than h vertices, as this bounds the worst-case size of an epidemic. While even this special case of the problem is NP-complete in general (even when h = 3), we provide evidence that many of the real-world networks of interest are likely to have small treewidth, and we describe an algorithm which solves the general problem in time 2O(|F|wr )n on an input graph having n vertices and whose treewidth is bounded by a fixed constant w, if each of the subgraphs we wish to avoid has at most r vertices.
For the special case in which we wish only to ensure that no component has more
than h vertices, we improve on this to give an algorithm running in time O((wh)2wn),
which we have implemented and tested on real datasets based on cattle movements.
of determining whether it is possible to delete at most k edges from a given input
graph (of small treewidth) so that the resulting graph avoids a set F of forbidden
subgraphs; of particular interest is the problem of determining whether it is possible to delete at most k edges so that the resulting graph has no connected component of more than h vertices, as this bounds the worst-case size of an epidemic. While even this special case of the problem is NP-complete in general (even when h = 3), we provide evidence that many of the real-world networks of interest are likely to have small treewidth, and we describe an algorithm which solves the general problem in time 2O(|F|wr )n on an input graph having n vertices and whose treewidth is bounded by a fixed constant w, if each of the subgraphs we wish to avoid has at most r vertices.
For the special case in which we wish only to ensure that no component has more
than h vertices, we improve on this to give an algorithm running in time O((wh)2wn),
which we have implemented and tested on real datasets based on cattle movements.
Original language | English |
---|---|
Pages (from-to) | 1857–1889 |
Number of pages | 12 |
Journal | Algorithmica |
Volume | 80 |
Issue number | 6 |
Early online date | 20 Apr 2017 |
DOIs | |
Publication status | Published - Jun 2018 |