TY - JOUR
T1 - On the average-case complexity of parameterized clique
AU - Fountoulakis, Nikolaos
AU - Friedrich, Tobias
AU - Hermelin, Danny
PY - 2015/2/19
Y1 - 2015/2/19
N2 - The k-Clique problem 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-known NP-complete and W[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 the k-Clique problem on the parameter k. To this end, we define two natural parameterized analogs of efficient average-case algorithms. We then show that k-Clique admits both analogues for Erdős–Rényi random graphs of arbitrary density. We also show that k-Clique is unlikely to admit either of these analogs for some specific computable input distribution.
AB - The k-Clique problem 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-known NP-complete and W[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 the k-Clique problem on the parameter k. To this end, we define two natural parameterized analogs of efficient average-case algorithms. We then show that k-Clique admits both analogues for Erdős–Rényi random graphs of arbitrary density. We also show that k-Clique is unlikely to admit either of these analogs for some specific computable input distribution.
U2 - 10.1016/j.tcs.2015.01.042
DO - 10.1016/j.tcs.2015.01.042
M3 - Article
SN - 0304-3975
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -