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

We study the complexity of graph modification problems with respect tohomomorphism-based colouring properties of edge-coloured graphs. A homomorphismfrom edge-coloured graph $G$ to edge-coloured graph $H$ is a vertex-mappingfrom $G$ to $H$ that preserves adjacencies and edge-colours. We consider theproperty of having a homomorphism to a fixed edge-coloured graph $H$. Thequestion we are interested in is: given an edge-coloured graph $G$, can weperform $k$ graph operations so that the resulting graph admits a homomorphismto $H$? The operations we consider are vertex-deletion, edge-deletion andswitching (an operation that permutes the colours of the edges incident to agiven vertex). Switching plays an important role in the theory of signedgraphs, that are 2-edge-coloured graphs whose colours are the signs $+$ and$-$. We denote the corresponding problems (parameterized by $k$) byVD-$H$-COLOURING, ED-$H$-COLOURING and SW-$H$-COLOURING. These problemsgeneralise $H$-COLOURING (to decide if an input graph admits a homomorphism toa fixed target $H$).  Our main focus is when $H$ is an edge-coloured graph with at most twovertices, a case that is already interesting as it includes problems such asVERTEX COVER, ODD CYCLE RANSVERSAL and EDGE BIPARTIZATION. For such a graph$H$, we give a P/NP-c complexity dichotomy for VD-$H$-COLOURING,ED-$H$-COLOURING and SW-$H$-COLOURING. We then address their parameterizedcomplexity. We show that VD-$H$-COLOURING and ED-$H$-COLOURING for all such $H$are FPT. In contrast, already for some $H$ of order 3, unless P=NP, none of thethree problems is in XP, since 3-COLOURING is NP-c. We show thatSW-$H$-COLOURING is different: there are three 2-edge-coloured graphs $H$ oforder 2 for which SW-$H$-COLOURING is W-hard, and assuming the ETH, admits noalgorithm in time $f(k)n^{o(k)}$. For the other cases, SW-$H$-COLOURING is FPT.

Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity