支配的なセットの最大カバレッジバージョン

Question

支配的な設定の問題は次のとおりです。

$ n $ vertexグラフ $ g=（v、e）$ 、Aを見つけるspan class="math-container"> $ s（\ subseteq v）$ $ | n [s] | $ が正確に< SPAN CLASS="math-container"> $ n $ 。 $$ n [s]：={x~ | \ text {$ X $または$ X $の近隣$ S $} \} \} $} $

私の質問は、次の（新しい問題）が文献に明確な名前を持つかどうか、そして最も適切な名前であるべきであれば、そうでなければそうであるならば。

新しい問題： $ n $ 頂点グラフ $ g=（v、 e）$ とinteger $ k $ 、set $ s（\ subeteq v）$ < sype $ k $ のサイズの/ span $ | n [s] | $ が最大化されます。< / P>

2番目の問題については、私が文学で見た名前のいくつかは最大グラフカバレッジです。部分カバレッジk prosight-set（ただし、同じ名前も他のコンテキストでも使用されます）。

Answer 1

$ k $ 頂点を最大化するための頂点を選択する問題は、予算上の支配集合の問題問題として知られています。 。問題やその接続された変種は、少なくともLamprou、Sigalis、Zissimopoulos [1]とKhuller、PurohitとSarpatwar [2]によって研究されています[2]。また、最近のNarayanaswamyとVijayAragunathan [3]。

---

[1] Lamprou、Ioannis、Ioannis Sigalas、およびVassilis Zissimopoulos。 「予算に接続された支配と予算縁の頂点支配を改善しました。」 Arxiv Preprint Arxiv：1907.06576（2019）。

[2] Khuller、Samir、Manish Purohit、およびKanthi K. Sarpatwar。 「最適な近隣の分析：予算と部分的に接続された優勢設定の問題のためのアルゴリズム」離散アルゴリズムに対する25回目のACM - SIAMシンポジウムの議事録。産業および応用数学協会、2014年

[3] Narayanaswamy、N. S.、R.VijayAragunathan。 「不確実なグラフにおけるパラメータ化された最適化 - 調査といくつかの結果」アルゴリズム13.1（2020）：3。