English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Let $G$ be a graph with $n$ vertices and $m$ edges. One of severalhierarchies towards the stability number of $G$ is the exact subgraph hierarchy(ESH). On the first level it computes the Lov\'{a}sz theta function$\vartheta(G)$ as semidefinite program (SDP) with a matrix variable of order$n+1$ and $n+m+1$ constraints. On the $k$-th level it adds all exact subgraphconstraints (ESC) for subgraphs of order $k$ to the SDP. An ESC ensures thatthe submatrix of the matrix variable corresponding to the subgraph is in thecorrect polytope. By including only some ESCs into the SDP the ESH can beexploited computationally.  In this paper we introduce a variant of the ESH that computes $\vartheta(G)$through an SDP with a matrix variable of order $n$ and $m+1$ constraints. Weshow that it makes sense to include the ESCs into this SDP and introduce thecompressed ESH (CESH) analogously to the ESH. Computationally the CESH seemsfavorable as the SDP is smaller. However, we prove that the bounds based on theESH are always at least as good as those of the CESH. In computationalexperiments sometimes they are significantly better.  We also introduce scaled ESCs (SESCs), which are a more natural way toinclude exactness constraints into the smaller SDP and we prove that includingan SESC is equivalent to including an ESC for every subgraph.

On different Versions of the Exact Subgraph Hierarchy for the Stable Set Problem