Semidefinite approximations for bicliques and biindependent pairs


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 number |A|+|B| of vertices one finds the stability number  \alpha(G), well-known to be polynomial-time computable. When the size is the product |A|\cdot |B| one  finds the parameter g(G), shown to be NP-hard by Peeters (2003), and when the size is the ratio (|A|\cdot |B|) / (|A|+|B|) one finds the parameter h(G), introduced by Vallentin (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 bounds for g(G), h(G), and \alpha_bal(G) (the maximum cardinality of a balanced independent set). We show that these bounds can be seen as natural variations of the Lov\'asz  \theta-number, a well-known semidefinite bound on \alpha(G) (equal to it for G bipartite). In addition we formulate closed-form eigenvalue bounds, which coincide with the semidefinite bounds for vertex- and edge-transitive graphs, and we show relationships among them as well as with earlier spectral parameters by Hoffman, Haemers (2001) and Vallentin (2020).



View Semidefinite approximations for bicliques and biindependent pairs