stability number of a graph

Semidefinite approximations for bicliques and biindependent pairs

  • Monique Laurent
  • Sven Polak
  • Luis Felipe Vargas
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , , , , , ,

    We investigate some graph parameters dealing with biindependent pairs $(A,B)$ in a bipartite graph $G=(V_1\cup V_2,E)$, i.e., pairs $(A,B)$ where $A\subseteq V_1$, $B\subseteq V_2$ and $A\cup B$ is independent. These parameters also allow to study bicliques in general graphs. When maximizing the cardinality $|A\cup B|$ one finds the stability number $\alpha(G)$, well-known to be polynomial-time … Read more

    Semidefinite Bounds for the Stability Number of a Graph via Sums of Squares of Polynomials

  • N. Gvozdenovic
  • Monique Laurent
    • Categories Graphs and Matroids, Semi-definite Programming Tags , ,

    Lov\’ asz and Schrijver [1991] have constructed semidefinite relaxations for the stable set polytope of a graph $G=(V,E)$ by a sequence of lift-and-project operations; their procedure finds the stable set polytope in at most $\alpha(G)$ steps, where $\alpha(G)$ is the stability number of $G$. Two other hierarchies of semidefinite bounds for the stability number have … Read more