W [1] – FPT時間近似アルゴリズムの問​​題

私はFPT時間で解決するのが難しいが、近似アルゴリズムを持っている問題を探しています。つまり、次のような問題があります。

R1。 W [1] -hard。

R2。 FPT時間で(好ましくは一定の)近似アルゴリズムを認める。

私がよく知っている問題は、グラフの長さ$ k $の単純なパスの数を数えることです。 #W [1] -hard$(1+ ε)$を認めますFPT時間における近似値(定数$ ε$の場合)

また興味深いのは、R1とR2を満たす問題と、

R3. There exists $epsilon>0$ such that the problem
is not $(1+epsilon)$ approximable in FPT time
(unless W[1]=FPT).

R1とR2、おそらくはR3を満たすその他の問題は何ですか?

ベストアンサー

指示された奇数サイクルトランスバーサル問題では、入力はグラフ$ G $であり、$ GS
$が奇数の長さの循環を持たないように最小セットの$ S $を見つけることです。パラメータ化されたバージョンでは、整数$ k
$が与えられ、最大$ k $の解が存在するかどうかが尋ねられます。

In this paper we prove that (R1) the problem is
W$[1]$-hard, (R2) that it admits a factor 2 approximation algorithm
in time $2^{k^{O(1)}}n^{O(1)}$, and that (R3’) assuming a
hypothesis somewhat stronger than $FPT neq W[1]$ that there exists
an $epsilon > 0$ such that the problem does not admit a
$(1+epsilon)$ approximation algorithm in time $f(k)n^{O(1)}$.

返信を残す

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