\(\)
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).
Article
View Semidefinite approximations for bicliques and biindependent pairs