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

Given a pair of graphs $\textbf{A}$ and $\textbf{B}$, the problems ofdeciding whether there exists either a homomorphism or an isomorphism from$\textbf{A}$ to $\textbf{B}$ have received a lot of attention. While graphhomomorphism is known to be NP-complete, the complexity of the graphisomorphism problem is not fully understood. A well-known combinatorialheuristic for graph isomorphism is the Weisfeiler-Leman test together with itshigher order variants. On the other hand, both problems can be reformulated asinteger programs and various LP methods can be applied to obtain high-qualityrelaxations that can still be solved efficiently. We study so-called fractionalrelaxations of these programs in the more general context where $\textbf{A}$and $\textbf{B}$ are not graphs but arbitrary relational structures. We give acombinatorial characterization of the Sherali-Adams hierarchy applied to thehomomorphism problem in terms of fractional isomorphism. Collaterally, we alsoextend a number of known results from graph theory to give a characterizationof the notion of fractional isomorphism for relational structures in terms ofthe Weisfeiler-Leman test, equitable partitions, and counting homomorphismsfrom trees. As a result, we obtain a description of the families of CSPs thatare closed under Weisfeiler-Leman invariance in terms of their polymorphisms aswell as decidability by the first level of the Sherali-Adams hierarchy.

Fractional homomorphism, Weisfeiler-Leman invariance, and the Sherali-Adams hierarchy for the Constraint Satisfaction Problem