文献

J-GLOBAL ID：202002285038057398   整理番号：20A0649311

有界独立集合サイズのグラフ上の部分集合フィードバック頂点集合【JST・京大機械翻訳】

Subset feedback vertex set on graphs of bounded independent set size

著者 (2件)： Papadopoulos Charis (Department of Mathematics, University of Ioannina, Greece) ,  Tzimas Spyridon (Department of Mathematics, University of Ioannina, Greece)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 814  ページ： 177-188  発行年： 2020年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： (加重)サブセットFeedback Vertex Set問題は,頂点集合の頂点を含む全てのサイクルを交差する最小(重み)サイズの頂点集合に対する古典的なFeedback Vertex Set問題の一般化である。サブセットFeedback Vertex SetとFeedback Vertex Setは分割グラフ上で異なる計算複雑性を示すが,類似の特性化はグラフの他のクラスでは知られていない。2つの問題の間の複雑性差異の理解に向けて,構造的グラフパラメータの重要性を研究することは自然である。ここでは,Wighted Feedback Vertex Setを多項式時間で解くことができることが知られている有界独立集合数のグラフを考察した。最大独立集合のサイズαに関して,二分切断結果を提供した。特に,Weighted Subset Feedback Vertex Setはα≦3のグラフに対して多項式時間で解くことができるが,α≧4のグラフに対して問題はNP困難であることを証明した。さらに,実行時間nO(α)を有するアルゴリズムを与えることにより,有界独立集合数のグラフ上の多項式時間において,(非加重)サブセットFeedback Set問題を解くことができることを示した。これらの結果を補完するために,著者らのアイデアが有界独立集合サイズのグラフ上の他の端末集合問題にどのように拡張できるかを実証した。ノード多方向カットは,任意の2つの端末を接続するすべての経路を交差する最小サイズの頂点集合を求める端末集合問題である。サブセットFeedback Vertex Setに対する著者らの発見に基づいて,ノードが重みづけされ,そして/または端末が与えられた独立集合数のあらゆる値に対して,ノードが重みづけられているその変種と同様に,ノードの複雑さを設定した。Copyright 2020 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *端末装置 ,  アルゴリズム ,  計算量 ,  NP困難 ,  キャラクタリゼーション ,  硬度
準シソーラス用語： 実行時間 ,  多項式時間 ,  複雑性 ,  *フィードバック頂点集合 ,  *有界 , 【Automatic Indexing@JST】

著者キーワード (6件)： 部分集合フィードバック頂点集合 ,  ノード多方向カット ,  多項式時間アルゴリズム ,  NP完全性 ,  W[1]-硬度 ,  有界独立集合サイズのグラフ

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (6件)： 有界 ,  集合 ,  サイズ ,  グラフ ,  部分集合 ,  フィードバック頂点集合