Semidefinite Approximations for Bicliques and Bi-Independent Pairs

Monique Laurent (), Sven Polak () and Luis Felipe Vargas ()
Additional contact information
Monique Laurent: Centrum Wiskunde & Informatica (CWI), 1098 XG Amsterdam, Netherlands; and Tilburg University, 5037 AB Tilburg, Netherlands
Sven Polak: Centrum Wiskunde & Informatica (CWI), 1098 XG Amsterdam, Netherlands; and Tilburg University, 5037 AB Tilburg, Netherlands
Luis Felipe Vargas: Centrum Wiskunde & Informatica (CWI), 1098 XG Amsterdam, Netherlands; and Istituto Dalle Molle Studi sull’Intelligenza Artificiale (IDSIA), USI-SUPSI, CH-6962 Lugano-Viganello, Switzerland

Mathematics of Operations Research, 2025, vol. 50, issue 1, 537-572

Abstract: We investigate some graph parameters dealing with bi-independent pairs ( A , B ) in a bipartite graph G = ( V 1 ∪ V 2 , E ) , that is, pairs ( A , B ) where A ⊆ V 1 , B ⊆ V 2 , and A ∪ B are independent. These parameters also allow us to study bicliques in general graphs. When maximizing the cardinality | A ∪ B | , one finds the stability number α ( G ) , well-known to be polynomial-time computable. When maximizing the product | A | · | B | , one finds the parameter g ( G ), shown to be NP-hard by Peeters in 2003, and when maximizing the ratio | A | · | B | / | A ∪ B | , one finds h ( G ), introduced by Vallentin in 2020 for bounding product-free sets in finite groups. We show that h ( G ) is an NP-hard parameter and, as a crucial ingredient, that it is NP-complete to decide whether a bipartite graph G has a balanced maximum independent set. These hardness results motivate introducing semidefinite programming (SDP) bounds for g ( G ), h ( G ), and α bal ( G ) (the maximum cardinality of a balanced independent set). We show that these bounds can be seen as natural variations of the Lovász ϑ-number, a well-known semidefinite bound on α ( G ) . In addition, we formulate closed-form eigenvalue bounds, and we show relationships among them as well as with earlier spectral parameters by Hoffman and Haemers in 2001 and Vallentin in 2020.

Keywords: 05Cxx; 90C22; 90C23; 90C27; 90C60; independent set; biclique; bi-independent pair; Lovász theta number; semidefinite programming; polynomial optimization; eigenvalue bound; stability number of a graph; Hoffman’s ratio bound (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2023.0046 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:50:y:2025:i:1:p:537-572

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().