FCPハミルトン閉路問題の計算困難性

• Item type: SIG Technical Reports(1)
• 公開日: 2024-08-29
• タイトル: FCPハミルトン閉路問題の計算困難性
• タイトル / 言語: en
• タイトル: Computational Complexity on FCP-Hamiltonian Cycle Problem
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: お茶の水女子大学
• 著者所属: お茶の水女子大学
• 著者所属(英): en
• 著者所属(英): Ochanomizu University
• 著者所属(英): en
• 著者所属(英): Ochanomizu University
• 著者名: 梅林, 果琳; 長尾, 篤樹
• 著者名(英): Karin, Umebayashi; Atsuki, Nagao
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 一般的な判定問題に対し，その解が含む情報を固定することで解を唯一にすることができるかを問う Fewest Clues Problem という枠組みがある．NP 完全問題の FCP バージョンは Σ2P という計算クラスに属すことが知られ，またいくつかの NP 完全問題の FCP バージョンが Σ2P 完全であることが知られている．本研究ではハミルトン閉路問題の FCP バージョンについての計算複雑性を解析し，FCP 1-in-3 SAT からの特殊な多項式時間帰着を用いることで Σ2P 完全であることを示した．またこの結果は入力グラフを二部平面グラフや 3-正則グラフ，split グラフ等に制限しても同様であることを示した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2024-AL-199, 号 3, p. 1-6, 発行日 2024-08-29
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会