EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1540. Semidefinite approximations for bicliques and biindependent pairs

Invited abstract in session TB-38: Advances in Complex and Real Semidefinite Programming, stream Conic Optimization: Theory, Algorithms, and Applications.

Tuesday, 10:30-12:00
Room: 34 (building: 306)

Authors (first author is the speaker)

1. Sven Polak
Tilburg University
2. Monique Laurent
Centrum Wiskunde & Informatica Amsterdam and Tilburg University
3. Luis Felipe Vargas
USI - SUPSI, Istituto Dalle Molle Studi sull’Intelligenza Artificiale (IDSIA)

Abstract

Let $G$ be a bipartite graph with vertex color classes $V_1$ and $V_2$. A
biindependent pair in $G$ is a pair $(A,B)$, where $A \subseteq V_1$, $B
\subseteq V_2$ and the union $A\cup B$ is an independent set. We consider the following three parameters $\alpha(G)$, $g(G)$ and $h(G)$, that are defined, respectively, as the maximum sum $|A|+|B|$, the maximum product $|A|\cdot |B|$ and the maximum ratio $(|A|\cdot|B|)/(|A|+|B|)$, taken over all biindependent pairs $(A,B)$ in $G$.

Similar parameters can be defined for bicliques in general graphs, which can however be reduced to the above parameters in bipartite graphs. While $\alpha(G)$ is easy to compute in bipartite graphs, Peeters (2003) showed that computing $g(G)$ is an NP-hard problem. The parameter $h(G)$ was introduced by Vallentin (2021). The parameters $g(G)$ and $h(G)$ have many applications, in particular, to bounding product-free subsets in finite groups, and the nonnegative rank of nonnegative matrices.

We investigate SDP upper bounds on $g(G)$ and $h(G)$, which can be seen as variations of the Lov\'asz $\vartheta$-number. We show links among them as well as with an earlier parameter by Haemers (2001), and we formulate closed-form eigenvalue bounds. We also show that computing $h(G)$ is NP-hard, by showing that it is NP-hard to determine if a bipartite graph has a biindependent pair (A,B) with |A|+|B|=\alpha(G) and |A|=|B|. We finally present a conjecture about the value of $h(G)$ on the hypercube graph.

Keywords

Status: accepted

Back to the list of papers