Expected complexity of graph partitioning problems

DOI10.1016/0166-218X(94)00103-KzbMath0830.68101OpenAlexW2062307640WikidataQ57568010 ScholiaQ57568010MaRDI QIDQ1346695

Luděk Kučera

Publication date: 10 April 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(94)00103-k

zbMATH Keywords

time complexitygraph partitioning problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15)

Related Items

Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis ⋮ Optimal detection of sparse principal components in high dimension ⋮ A simple spectral algorithm for recovering planted partitions ⋮ The Ehrenfeucht-Fraïssé Method and the Planted Clique Conjecture ⋮ Some lower bounds in parameterized \(\mathrm{AC}^{0}\) ⋮ Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation ⋮ A note on edge-based graph partitioning and its linear algebraic structure ⋮ A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem ⋮ Comment on ``Hypothesis testing by convex optimization ⋮ The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs ⋮ The forgetfulness of balls and bins ⋮ Finding Hidden Cliques in Linear Time with High Probability ⋮ The complexity of explicit constructions ⋮ Recovering nonuniform planted partitions via iterated projection ⋮ On the hardness of designing public signals ⋮ Finding a planted clique by adaptive probing ⋮ Exact recovery in the hypergraph stochastic block model: a spectral algorithm ⋮ Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio ⋮ The Complexity of Public-Key Cryptography ⋮ Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning ⋮ Computational barriers in minimax submatrix detection

Cites Work

• Unnamed Item
• Unnamed Item
• Graphs with small chromatic numbers are easy to color
• The solution of some random NP-hard problems in polynomial expected time
• Almost all k-colorable graphs are easy to color
• The greedy coloring is a bad probabilistic algorithm
• On colouring random graphs
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• The chromatic number of random graphs