Complexity of finding unique optimal cut sets in network problems
On the Complexity of Forcing and Anti-Forcing Minimum Cuts
Data Structures and Algorithms
Summary
This paper looks at how hard it is to find small groups of elements that force a unique best solution in certain cut problems on networks. A forcing set forces the best solution to include certain elements, while an anti-forcing set forces it to exclude them. The authors study these questions for two classic network cut problems, determining which cases can be solved efficiently and which are hard (NP-complete). Their results clarify when it’s possible to quickly find these special sets and when it’s computationally difficult.
What this means in practice
- •For network reliability engineers: Determine minimal critical components that uniquely determine the weakest points in a communication network.
- •For security analysts: Identify minimal sets of defenses that uniquely secure against particular network vulnerabilities by forcing or excluding certain network cuts.
A theory result. No direct application yet.
Authors
Tatsuya Gima, Yasuaki Kobayashi, Hiraku Morimoto, Yota Otachi
Abstract
For an instance of a combinatorial optimization problem, a \emph{forcing set} is a set of elements such that there is a unique optimal solution including it. Symmetrically, an \emph{anti-forcing set} is a set of elements such that there is a unique optimal solution excluding it. In this paper, we study the problems of computing smallest forcing and anti-forcing sets for two classical cut problems, \textsc{Global Min Cut} and \textsc{Min $s$--$t$ Cut}. We also consider variants in which the optimal cut to be uniquely determined is given as input. For each of these problems, we either give a polynomial-time algorithm or prove \NP-completeness.