講演抄録/キーワード |
講演名 |
2007-05-25 14:30
Fixed-Parameter Tractability for Non-Crossing Spanning Trees ○Magnus Halldorsson(Univ. of Iceland)・Christian Knauer(Freie U.)・Andreas Spillner(U. East Anglia)・Takeshi Tokuyama(Tohoku U) COMP2007-15 |
抄録 |
(和) |
平面上に辺を曲線として描画されたグラフ(トポロジカルグラフ)
において,辺が交差しない全域部分木を計算する問題を考える.
非交差な全域部分木を持つかどうかの判定はNP困難問題であり,交差数を最小化する問題は
近似困難である事が知られている.本論文では、以下のような自然なパラメタに対し、
パラメトリック計算量(パラメタへの依存度を考慮する計算量)を考察する.
対象とするパラメタは,入力されるトポロジカルグラフにおける
交差辺対の数$k$,交差辺の数$\mu$,頂点集合の凸包の内点である頂点数$\iota$である.
まず,シンプルなバックトラック探索における改良された戦略を与え,$O^*(1.93^{k})$
時間の計算量を与える.これは理論的には大きな改善ではないが、バックトラック探索における
実装のガイドラインを与えるという価値を持つ.
次に,グラフのセパレータを用いたより洗練されたアルゴリズムにより計算量を改善する.
アルゴリズムの計算量はそれぞれのパラメタに対し,$O^*(2^{O(\sqrt{k})})$,
$O^*(\mu^{O(\mu^{2/3})})$, $O^*(\iota^{O(\sqrt{\iota})})$ となる.
また,3-SAT問題への帰着により,この問題に対して$O^*(2^{\sqrt{k}})$の計算量を改善するのは
3-SATに対する広く信じられている計算量の仮定の下では困難である事を示す. |
(英) |
We consider the problem of computing non-crossing spanning trees in
topological graphs. It is known that it is NP-hard to decide
whether a topological graph has a non-crossing spanning tree, and
that it is hard to approximate the minimum number of crossings in a
spanning tree.
We consider the parameterized complexities of the problem for the following
natural input parameters: the number $k$ of crossing edge pairs, the
number $\mu$ of crossing edges in the given graph, and the number
$\iota$ of vertices in the interior of the convex hull of the vertex
set. We start with an improved strategy of the simple search-tree
method to obtain an $O^*(1.93^{k})$ time algorithm. Although not a
major theoretical improvement, it provides a guideline for the
implementation of the search-tree method. We then give more sophisticated
algorithms based on graph separators, with a novel technique to ensure
connectivity.
The time complexities of our algorithms are $O^*(2^{O(\sqrt{k})})$,
$O^*(\mu^{O(\mu^{2/3})})$, and $O^*(\iota^{O(\sqrt{\iota})})$.
By giving a reduction from 3-SAT, we show that the $O^*(2^{\sqrt{k}})$
complexity is hard to improve under a hypothesis of the complexity of
3-SAT. |
キーワード |
(和) |
全域木 / 非交差グラフ / パラメトリック計算量 / / / / / |
(英) |
Minimum spanning tree / Noncrossing subgraph / Parametric complexity / / / / / |
文献情報 |
信学技報, vol. 107, no. 73, COMP2007-15, pp. 25-30, 2007年5月. |
資料番号 |
COMP2007-15 |
発行日 |
2007-05-18 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2007-15 |