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/

Zendy Plus

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

Zendy Tools

Zendy Open

Counting homomorphisms from a graph $H$ into another graph $G$ is afundamental problem of (parameterized) counting complexity theory. In thiswork, we study the case where \emph{both} graphs $H$ and $G$ stem from givenclasses of graphs: $H\in \mathcal{H}$ and $G\in \mathcal{G}$. By this, wecombine the structurally restricted version of this problem, with thelanguage-restricted version.  Our main result is a construction based on Kneser graphs that associatesevery problem $\tt P$ in $\#\mathsf{W[1]}$ with two classes of graphs$\mathcal{H}$ and $\mathcal{G}$ such that the problem $\tt P$ is\emph{equivalent} to the problem $\#{\tt HOM}(\mathcal{H}\to \mathcal{G})$ ofcounting homomorphisms from a graph in $\mathcal{H}$ to a graph in$\mathcal{G}$. In view of Ladner's seminal work on the existence of$\mathsf{NP}$-intermediate problems [J.ACM'75] and its adaptations to theparameterized setting, a classification of the class $\#\mathsf{W[1]}$ infixed-parameter tractable and $\#\mathsf{W[1]}$-complete cases is unlikely.Hence, obtaining a complete classification for the problem $\#{\ttHOM}(\mathcal{H}\to \mathcal{G})$ seems unlikely. Further, our proofs easilyadapt to $\mathsf{W[1]}$.  In search of complexity dichotomies, we hence turn to special graph classes.Those classes include line graphs, claw-free graphs, perfect graphs, andcombinations thereof, and $F$-colorable graphs for fixed graphs $F$: If theclass $\mathcal{G}$ is one of those classes and the class $\mathcal{H}$ isclosed under taking minors, then we establish explicit criteria for the class$\mathcal{H}$ that partition the family of problems $\#{\ttHOM}(\mathcal{H}\to\mathcal{G})$ into polynomial-time solvable and$\#\mathsf{W[1]}$-hard cases. In particular, we can drop the condition of$\mathcal{H}$ being minor-closed for $F$-colorable graphs.

Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory