Average polynomial time complexity of some NP-complete problems

DOI10.1016/0304-3975(86)90031-9MaRDI QIDQ1091815zbMATH OpenOpenAlexFDO

Authors Phan Dinh Dieu, Le Cong Thanh, Le Tuan Hoa

Publication date 1986

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

Full work available at URL https://doi.org/10.1016/0304-3975(86)90031-9

zbMATH Keywords

average polynomial timeCLIQUE problemNP-complete problemRandom graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Review text

Random graphs with n vertices are considered such that any edge occurs independently swith the same probability p. It is proved that the CLIQUE problem can be solved in average polynomial time for these graphs when \(p=n^{-\epsilon}\), where \(\epsilon >0\) is a constant. Besides, the problem CLIQUE(N(n)) is considered for the graphs with a number of edges less than N(n). It is shown that this problem can also be solved in average polynomial time for any function \(0\leq N(n)\leq n^{2-\epsilon}\), where \(0<\epsilon <2\). Provided that \(N(n)\geq n^{\epsilon}\), the latter problem is NP-complete.

Recommendations

• A hard problem that is almost always easy
• The solution of some random NP-hard problems in polynomial expected time
• The monotone complexity of \(k\)-clique on random graphs
• An Average Case NP-complete Graph Colouring Problem
• On the average-case complexity of parameterized clique

Cites work

• A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
• A New Algorithm for Generating All the Maximal Independent Sets
• Asymptotic estimations of certain parameters of finite graphs and their applications
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Finding a Maximum Independent Set
• scientific article; zbMATH DE number 3690716 (Why is no real title available?)
• scientific article; zbMATH DE number 3770947 (Why is no real title available?)
• scientific article; zbMATH DE number 3480503 (Why is no real title available?)
• scientific article; zbMATH DE number 3482343 (Why is no real title available?)
• scientific article; zbMATH DE number 3568580 (Why is no real title available?)
• scientific article; zbMATH DE number 3574966 (Why is no real title available?)
• scientific article; zbMATH DE number 3590325 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On colouring random graphs
• On the average number of steps of the simplex method of linear programming
• The Worst and the Most Probable Performance of a Class of Set-Covering Algorithms

Cited in

(9)

• Polynomial-average-time satisfiability problems
• Average case completeness
• On the average-case complexity of parameterized clique
• The solution of some random NP-hard problems in polynomial expected time
• scientific article; zbMATH DE number 436075 (Why is no real title available?)
• scientific article; zbMATH DE number 1555929 (Why is no real title available?)
• On the average complexity of the $k$-level
• Sets computable in polynomial time on average
• A hard problem that is almost always easy

This page was built for publication: Average polynomial time complexity of some NP-complete problems

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