On NP-hardness of the clique partition -- independence number gap recognition and related problems

DOI10.1016/j.disc.2006.01.004zbMath1091.05049OpenAlexW1986997293WikidataQ56874375 ScholiaQ56874375MaRDI QIDQ2368935

Stanislav Busygin, Dimitrii V. Pasechnik

Publication date: 28 April 2006

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

Full work available at URL: https://doi.org/10.1016/j.disc.2006.01.004

zbMATH Keywords

partial Latin squares completion

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Copositive programming motivated bounds on the stability and the chromatic numbers, Monopolar graphs: complexity of computing classical graph parameters, Chromatic Gallai identities operating on Lovász number

Cites Work

• The complexity of completing partial Latin squares
• The sandwich theorem
• Semidefinite programming in combinatorial optimization
• Approximation of the Stability Number of a Graph via Copositive Programming
• Cones of Matrices and Set-Functions and 0–1 Optimization
• On the Shannon capacity of a graph
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item