Forcing a unique minimum spanning tree and a unique shortest path
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915680040779776 |
|---|---|
| author | Gima, Tatsuya Kobayashi, Yasuaki Otachi, Yota Sato, Takumi |
| author_facet | Gima, Tatsuya Kobayashi, Yasuaki Otachi, Yota Sato, Takumi |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_24309 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Forcing a unique minimum spanning tree and a unique shortest path Gima, Tatsuya Kobayashi, Yasuaki Otachi, Yota Sato, Takumi Data Structures and Algorithms 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. |
| title | Forcing a unique minimum spanning tree and a unique shortest path |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2509.24309 |