2026-05-19T10:36:18Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00238530 2025-01-19T08:32:19Z 1164:2592:11452:11708

FCPハミルトン閉路問題の計算困難性 Computational Complexity on FCP-Hamiltonian Cycle Problem 梅林, 果琳 長尾, 篤樹 Karin, Umebayashi Atsuki, Nagao 一般的な判定問題に対し，その解が含む情報を固定することで解を唯一にすることができるかを問う Fewest Clues Problem という枠組みがある．NP 完全問題の FCP バージョンは Σ2P という計算クラスに属すことが知られ，またいくつかの NP 完全問題の FCP バージョンが Σ2P 完全であることが知られている．本研究ではハミルトン閉路問題の FCP バージョンについての計算複雑性を解析し，FCP 1-in-3 SAT からの特殊な多項式時間帰着を用いることで Σ2P 完全であることを示した．またこの結果は入力グラフを二部平面グラフや 3-正則グラフ，split グラフ等に制限しても同様であることを示した． In the framework known as the Fewest Clues Problem (FCP), the task is to determine whether the solution to a decision problem can be made having unique solution by fixing certain pieces of information. It is known that the FCP versions of NP-complete problems belong to the complexity class Σ2P, and some FCP versions of NP-complete problems are known to be Σ2P-complete. In this study, we analyze the computational complexity of the FCP version of the Hamiltonian Cycle Problem. And we show that it is Σ2P-complete by utilizing a special polynomial-time reduction from the FCP 1-in-3 SAT problem. Furthermore, we show that this result holds even when the input graph is restricted to bipartite graphs, 3-regular graphs, or split graphs. 情報処理学会 2024-08-29 jpn technical report https://ipsj.ixsq.nii.ac.jp/records/238530 2188-8566 AN1009593X 研究報告アルゴリズム（AL） 2024-AL-199 3 1 6 https://ipsj.ixsq.nii.ac.jp/record/238530/files/IPSJ-AL24199003.pdf application/pdf 1.0 MB