2025/09/29 by Tatsuya Gima, Gima, Tatsuya, Andreas Grigorjew +11
#cs.DS
paper · pdf · doi:10.48550/arxiv.2509.24309
A forcing set S in a combinatorial problem is a set of elements such that there is a unique solution that contains all the elements in S. An anti-forcing set is the symmetric concept: a set S of elements is called an anti-forcing set if there is a unique solution disjoint from S. There are extensive studies on the computational complexity of finding a minimum forcing set in various combinatorial problems, and the known results indicate that many problems are harder than their classical counterparts: the decision version of finding a minimum forcing set for perfect matchings is NP-complete [Adams et al., Discrete Mathematics, 2004], and that of finding a minimum forcing set for satisfying assignments for 3CNF formulas is Σ2P-complete [Hatami-Maserrat, Discrete Applied Mathematics, 2005]. In this paper, we investigate the complexity of finding minimum forcing and anti-forcing sets for the shortest s-t path problem and the minimum-weight spanning tree problem. We show that, unlike the aforementioned results, these problems are tractable, with the exception of the decision version of finding a minimum anti-forcing set for shortest s-t paths, which is NP-complete. To complement this intractability result, we design fixed-parameter tractable algorithms for finding a minimum anti-forcing set for shortest s-t paths.