{"ID":2863316,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.24309","arxiv_id":"2509.24309","title":"Forcing a unique minimum spanning tree and a unique shortest path","abstract":"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 would be harder than their classical counterparts: the decision version of finding a minimum forcing set for perfect matchings is NP-complete [Adams et al., Discret. Math. 2004] and that of finding a minimum forcing set for satisfying assignments for 3CNF formulas is $Σ_2^{\\mathrm{P}}$-complete [Hatami-Maserrat, DAM 2005]. In this paper, we investigate the complexity of the problems 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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2509.24309","url_pdf":"https://arxiv.org/pdf/2509.24309v2","authors":"[\"Tatsuya Gima\",\"Yasuaki Kobayashi\",\"Yota Otachi\",\"Takumi Sato\"]","published":"2025-09-29T05:45:50Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}