On the average-case complexity of parameterized clique

DOI10.1016/J.TCS.2015.01.042MaRDI QIDQ2344729zbMATH OpenOpenAlexFDO

Authors Nikolaos Fountoulakis, Tobias Friedrich, Danny Hermelin

Publication date 18 May 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.6400

zbMATH Keywords

computational complexitycliqueparameterized complexityaverage-case

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: 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 ErdH{o}s-R'{e}nyi random graphs of arbitrary density. We also show that k-Clique is unlikely to admit neither of these analogs for some specific computable input distribution.

Recommendations

• The monotone complexity of \(k\)-clique on random graphs
• On the kernel size of clique cover reductions for random intersection graphs
• Parameterized clique on inhomogeneous random graphs
• Average polynomial time complexity of some NP-complete problems
• Efficient algorithms for clique problems

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 5529641 (Why is no real title available?)
• scientific article; zbMATH DE number 3574966 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• A New Algorithm for Generating All the Maximal Independent Sets
• A large deviation result on the number of small subgraphs of a random graph
• All natural NP-complete problems have average-case complete versions
• Average Case Complete Problems
• Average case completeness
• Computational Complexity
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Parameterized Clique on Scale-Free Networks
• Paths in graphs
• Reducibility among combinatorial problems
• The deletion method for upper tail estimates
• The monotone complexity of \(k\)-clique on random graphs

Cited in

(7)

• A Tight Upper Bound on the Number of Variables for Average-Case k-Clique on Ordered Graphs
• Parameterized clique on inhomogeneous random graphs
• Finding Induced Subgraphs in Scale-Free Inhomogeneous Random Graphs
• On the kernel size of clique cover reductions for random intersection graphs
• From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity (Tutorial)
• The monotone complexity of \(k\)-clique on random graphs
• Average polynomial time complexity of some NP-complete problems

This page was built for publication: On the average-case complexity of parameterized clique

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2344729)