2023/02/17 by Laurent, Monique, Polak, Sven, Vargas, Luis Felipe · 1 citation
#05Cxx #90C22 #90C23 #90C27 #90C60 #Combinatorics (math.CO) #FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2302.08886
We investigate some graph parameters dealing with biindependent pairs (A,B) in a bipartite graph G=(V1∪ V2,E), i.e., pairs (A,B) where A⊆ V1, B⊆ V2 and A∪ B is independent. These parameters also allow 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 (2003), and when maximizing the ratio |A|⋅ |B|/|A∪ B| one finds 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 α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, Haemers (2001) and Vallentin (2020).