| 講演名 | 2010-12-03 最大支配問題 宮野 英次, 小野 廣隆, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | グラフにおける頂点/辺支配集合問題の新しい亜種について考える.ある頂点はその頂点自身と隣接点を支配すると言い,同様にある辺はその辺自身と隣接する辺を支配すると言う.グラフG=(V,E)と正整数kが与えられたとき,k-頂点(k-辺)支配問題(それぞれ以下k-MaxVD, k-MaxEDと呼ぶ)は高々サイズkの頂点の部分集合D_V⫅V(D_E⫅E)の中で,支配する頂点集合(また辺集合)のサイズを最大化するものを求める問題である.本論文では,まずこの問題に対して単純な貪欲アルゴリズムがk-MaxVD, k-MaxEDいずれに対しても近似比(1-1/e)を達成することを示す.次にP≠NPの条件下で,k-MaxVEに対してこの近似比が多項式時間アルゴリズムの最善であることを示す.さらにP≠NPの条件下で,k-MaxEDに対して1303/1304よりも良い近似比の多項式時間アルゴリズムが存在しないことを示す.一方,kがグラフの最小最大マッチングのサイズを超えないという条件下では,k-MaxEDに対して近似比3/4の多項式時間アルゴリズムが存在することを示す. |
| 抄録(英) | We consider new variants of the vertex/edge domination problems on graphs. A vertex is said to dominate itself and its all adjacent vertices, and similarly an edge is said to dominate itself and its all adjacent edges. Given an input graph G=(V,E) and an integer k, the k-VERTEX (k-EDGE) MAXIMUM DOMINATION (k-MaxVD and k-MaxED, respectively) is to find a subset D_V⫅V of vertices (resp., D_E⫅E of edges) with size at most k that maximizes the cardinality of dominated vertices (resp., edges). In this paper, we first show that a simple greedy strategy achieves an approximation ratio of (1-1/e) for both k-MaxVD and k-MaxED. Then, we show that this approximation ratio is the best possible for k-MaxVD unless P=NP. We also prove that, for any constant ε >0, there is no polynomial time 1303/1304+ε approximation algorithm for k-MaxED unless P=NP. However, if k is not larger than the size of the minimum maximal matching, k-MaxED is 3/4-approximable in polynomial time. |
| キーワード(和) | |
| キーワード(英) | maximum domination / vertex domination / edge domination / approximability / inapproximability |
| 資料番号 | COMP2010-46 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2010/11/26(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 最大支配問題 |
| サブタイトル（和） | |
| タイトル（英） | Maximum Domination Problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | / maximum domination |
| 第 1 著者 氏名（和/英） | 宮野 英次 / Eiji MIYANO |
| 第 1 著者 所属（和/英） | 九州工業大学大学院情報工学院システム創成情報工学系 Department of Systems Design and Informatics, Faculty of Computer Science and Systems Engineering, Kyushu Institute of Technology |
| 第 2 著者 氏名（和/英） | 小野 廣隆 / Hirotaka ONO |
| 第 2 著者 所属（和/英） | 九州大学大学院経済学研究院経済工学部門 Department of Economical Engineering, Faculty of Economics, Kyushu University |
| 発表年月日 | 2010-12-03 |
| 資料番号 | COMP2010-46 |
| 巻番号（vol） | vol.110 |
| 号番号（no） | 325 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |