パラメータが問題に適していると言うときは?

私はパラメータ化された複雑さを研究しています。私は、頂点のカバー、フィードバック頂点のセットなどのような問題のためのパラメータ化されたアルゴリズムはほとんど見ていません。パラメータが「良いパラメータ」と呼ばれるときを判断するのは難しいです。私の良いパラメータの定義は明確ではありませんが、そのパラメータを使用してその問題のFPTアルゴリズムを考え出すことができれば、いくつかの重要なインスタンスのインスタンスを解決できます。

例:独立集合(I)と頂点カバー(V)を用いたグラフ問題のパラメータ化と、タイプ$ g(k)^ {f(I)}
textのFPTアルゴリズムを得る方法{ポリ}(n)$。それは問題の良いパラメータ化でしょうか。

質問:パラメータが問題に適していると言うときは?問題のために多くのパラメータを定義することができますが、ここで問題となるのはそれをどのように決定するかです。

ベストアンサー

私の意見では、これは実際にはパラメータ化されたアルゴリズムの主な質問の1つです。問題のパラメタリゼーションの「芸術」について議論するいくつかの記事がありますが、そのうちのいくつかを以下に挙げます。

簡単に言えば、問題の理想的なパラメータ$ k $は、2つのことを与えるはずです。

  1. パラメータ$ k $に対する固定パラメータの追跡は、$ k
    $に対する実行時間依存性が良好であるという問題があります。つまり、中程度の指数関数$ f $に対して、$ f(k) cdot n ^
    {O(1)} $時間で解くことができます。
  2. この問題の典型的な例では、$ k $の値は小さいです。

Most of research in parameterized algorithms focuses on the
first issue. The second issue is not really treated in a systematic
empirical fashion I’d say. That is, there are no comprehensive
studies measuring the value of parameters in real-world instances.
What people do to justify the study of particular parameters is to
systematically compare parameter values. For example, one
may say that a fixed-parameter algorithm for a parameter $k$ is
more useful than a fixed-parameter algorithm for parameter $ell$
if $ell>k$ in many instances and $ellge k$ in all instances.
Using these relations between parameter values one may navigate
through parameter space to obtain useful fixed-parameter
algorithms.

たとえば、入力グラフ$ G $のグラフ問題がパラメータ頂点カバー数$ mathrm
{vc}(G)$に対して固定的に扱いやすいことを示している場合は、固定パラメータで扱いやすいことを示すことができますすべてのグラフで$
mathrm {fvs}(G) le mathrm {vc}(G)$のためにパラメータフィードバック頂点集合数$
mathrm {fvs}このような場合、問題は、グラフが$ mathrm {tw}(G) le
mathrmであるので、問題が固定パラメータであることを示すことができますすべてのグラフで{fvs}(G)+ 1
$を計算します。

いくつかの参考文献:

  • Michael R. Fellows、Bart M. P. Jansen、Frances A. Rosamond:
    完全多変量アルゴリズムに向けて:パラメータ生態学と計算複雑性の解体。ユーロ。 J.Comb。
    34(3):541-566(2013)
  • Rolf Niedermeier: 多変量アルゴリズムと問題パラメータ化に関する考察。 STACS
    2010:17-32
  • Christian Komusiewicz、Rolf Niedermeier:
    パラメータ化されたアルゴリズムにおける新しい人種。 MFCS 2012:19-30

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です