グラフの問題の仮想的な複雑さに関する共通の洞察

いくつかのグラフの問題の仮説的硬度という2つの例が出てきました。仮説的硬度は、いくつかの推測を反論することは、それぞれのグラフ問題のNP完全性を暗示することを意味する。例えば、
Barnetteの推測では、すべての3連結3次平面バイパータイトグラフはハミルトニアンであると述べています。推測を反駁することは、ハミルトニアンサイクル問題のNP完全性を暗示すると、
FederとSubiは証明した推測のクラスのグラフ上にある。

Tutte’s 5-flow Conjecture states that every
bridgeless graph has a nowhere-zero 5-flow. Kochol showed that if
the conjecture is false, then the problem of determining whether a
cubic graph admits a nowhere-zero 5-flow is
NP-complete
.

対応するグラフの問題の仮説NP完全性を説明する上の推測についての共通の洞察はありますか?上記の意味で仮想的な複雑さの他の例はありますか?

P.S.これは、答えを得ずに
MathoverFlow
に掲載されました。

ベストアンサー

あなたの質問の2番目の部分について2つの参照があります。

The paper [1] addresses certain types of colorability of sparse
graphs with given girth $g$. For every fixed $g$, they show that
the associated decision problem is either trivial (every graph in
the class has a coloring) or NP-complete. But determining which is
the threshold value of $g$ remains a difficult open problem!
Edit: One of the considered problems is related to Jaeger’s
conjecture, that every planar graph of girth $4k$ admits a
homomorphism to $C_{2k+1}$. It is shown in [1] that any
counterexample directly provides a hardness proof. (A similar
conjecture by Klostermeyer and Zhang exists for the odd-girth.) For
the other problems considered in [1], there is no official
conjecture, but for any guess about the correct threshold value $g$
that one can make, if proved false by a counterexample, the latter
directly implies a corresponding hardness proof.

上記の論文の紹介では、SAT [2]についての以下の興味深い結果も述べられている。すべての$ k
$に対して、$(k、f(k))$ – SAT(すなわち、各変数が$ f(k) )$ times)は簡単ですが、$(k、f(k)+1)$
– SATはNP完全です。 ($ f(k)$の正確な値は不明のようですが、いくらかの見積もりがあります)。

[1] L. Esperet, M. Montassier, P. Ochem and A. Pinlou. A
complexity dichotomy for the coloring of sparse graphs. Journal of
Graph Theory 73:85-102, 2012. link + PDF on an author’s website

[2] J. Kratochvil, P. Savicky and Zs. Tuza. One more
occurrence of variables makes satisfiability jump from trivial to
NP-complete. SIAM Journal on Computing 22:203-210, 1993. link

返信を残す

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