On the average-case complexity of parameterized clique

DOI10.1016/J.TCS.2015.01.042zbMATH Open1312.68100arXiv1410.6400OpenAlexW2043610021MaRDI QIDQ2344729FDOQ2344729

Authors: Nikolaos Fountoulakis, Tobias Friedrich, Danny Hermelin 

Publication date: 18 May 2015

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

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.

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

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

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)

Cites Work

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

Cited In (7)

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

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)