On the average-case complexity of parameterized clique
On the average-case complexity of parameterized clique
复制标题
关于参数化团的平均情况复杂度
DOI：
10.1016/j.tcs.2015.01.042
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
D. Hermelin
中科院分区：
文献类型：
--
作者：
N. Fountoulakis;T. Friedrich;D. Hermelin
K-C问题是一个基本的组合问题，在经典复杂性理论和参数化复杂性理论中起着重要的作用。它是最著名的NP-完全和W [1]-完全问题之一。此外，自20世纪70年代以来，其平均情况复杂性分析已经创造了一个很长的研究线索。在这里，我们继续这条线的研究，通过研究的依赖性的平均情况下的复杂性的thek-Cyndrome问题的parameterk。为此，我们定义了两个自然的参数化类似物的有效的平均情况下的算法。然后我们证明了k-C_∞允许任意密度的Erdens-Rényi随机图的这两个类似。我们还表明，k-Cynth不太可能承认这些类似物的一些特定的可计算的输入分布。
Thek-Cliqueproblem is a fundamental combinatorial problem that plays a prominent role in classical as well as in parameterized complexity theory. It is among the most well-knownNP-complete andW[1]-complete problems. Moreover, its average-case complexity analysis has created a long thread of research already since the 1970s. Here, we continue this line of research by studying the dependence of the average-case complexity of thek-Cliqueproblem on the parameterk. To this end, we define two natural parameterized analogs of efficient average-case algorithms. We then show thatk-Cliqueadmits both analogues for Erdős–Rényi random graphs ofarbitrarydensity. We also show thatk-Cliqueis unlikely to admit either of these analogs for some specific computable input distribution.
登录
查看更多内容
DOI：
--
发表时间：
2004
期刊：
Comb.
影响因子：
--
作者：
S. Janson;A. Rucinski
通讯作者：
A. Rucinski
DOI：
10.1137/0215020
发表时间：
1986-02
期刊：
SIAM J. Comput.
影响因子：
--
作者：
L. Levin
通讯作者：
L. Levin
Die Landstände Vorderösterreichs 位于 15 号。
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
Hermann J. Schwarzweber
通讯作者：
Hermann J. Schwarzweber
无标度网络上的参数化团
DOI：
--
发表时间：
2012
期刊：
International Symposium on Algorithms and Computation
影响因子：
--
作者：
T. Friedrich;Anton Krohmer
通讯作者：
Anton Krohmer
DOI：
--
发表时间：
1996
期刊：
影响因子：
--
作者：
Albert
通讯作者：
Albert