Hoffman’s ratio bound – Optimization Online

Semidefinite approximations for bicliques and biindependent pairs

Published: 2023/03/01

Combinatorial Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming biclique, biindependent pair, eigenvalue bound, Hoffman's ratio bound, independent set, lovasz theta number, polynomial optimization, semidefinite programming, stability number of a graph

\(\) We investigate some graph parameters asking to maximize the size of biindependent pairs (A,B) in a bipartite graph G = (V1 \cup V2;E), where A\subseteq V1, B \subseteq V2 and A \cup B is independent. These parameters also allow to study bicliques in general graphs (via bipartite double graphs). When the size is the … Read more