On the average-case complexity of parameterized clique

DOI10.1016/j.tcs.2015.01.042zbMath1312.68100arXiv1410.6400OpenAlexW2043610021MaRDI QIDQ2344729

Danny Hermelin, Nikolaos Fountoulakis, Tobias Friedrich

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

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

Related Items

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), Parameterized clique on inhomogeneous random graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• All natural NP-complete problems have average-case complete versions
• Average case completeness
• The deletion method for upper tail estimates
• On the Choice Number of Random Hypergraphs
• Average Case Complete Problems
• A New Algorithm for Generating All the Maximal Independent Sets
• Paths in graphs
• Parameterized Clique on Scale-Free Networks
• Reducibility among Combinatorial Problems
• The Monotone Complexity of $k$-Clique on Random Graphs
• Computational Complexity