Skip to main navigation Skip to search Skip to main content

Semidefinite approximations for bicliques and biindependent pairs

Research output: Contribution to journal › Article › Scientific › peer-review

44 Downloads (Pure)

Abstract

We investigate some graph parameters dealing with bi-independent pairs (A, B) in a bipartite graph G=(V1∪V2,E), that is, pairs (A, B) where A⊆V1, B⊆V2, 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.
Original languageEnglish
Pages (from-to)537-572
JournalMathematics of Operations Research
Volume50
Issue number1
DOIs
Publication statusPublished - Feb 2025

Keywords

  • independent set
  • biclique
  • bi-independent pair
  • Lovasz theta number
  • semidefinite programming
  • polynomial optimization
  • eigenvalue bound
  • stability number of a graph
  • Hoffman's ratio bound

Fingerprint

Dive into the research topics of 'Semidefinite approximations for bicliques and biindependent pairs'. Together they form a unique fingerprint.

Cite this