کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
437893 | 690204 | 2015 | 12 صفحه PDF | دانلود رایگان |
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.
Journal: Theoretical Computer Science - Volume 576, 20 April 2015, Pages 18–29