Parameterized complexity of edge-coloured and signed graph homomorphism problems

Abstract

We study the complexity of graph modification problems for homomorphism-based properties of edge-coloured graphs. A homomorphism from an edge-coloured graph \(G\) to an edge-coloured graph \(H\) is a vertex-mapping from \(G\) to \(H\) that preserves adjacencies and edge-colours. We consider the property of having a homomorphism to a fixed edge-coloured graph \(H\). Given an edge-coloured graph \(G\), can we perform \(k\) graph operations so that the resulting graph has a homomorphism to \(H\)? The operations we consider are vertex-deletion, edge-deletion and switching (an operation that permutes the colours of the edges incident to a given vertex). Switching plays an important role in the theory of signed graphs, that are \(2\)-edge-coloured graphs whose colours are \(+\) and \(-\). We denote the corresponding problems (parameterized by \(k\)) by VERTEX DELETION \(H\)-COLOURING, EDGE DELETION \(H\)-COLOURING and SWITCHING \(H\)-COLOURING. These generalise \(H\)-COLOURING (where one has to decide if an input graph admits a homomorphism to \(H\)). Our main focus is when \(H\) has order at most \(2\), a case that includes standard problems such as VERTEX COVER, ODD CYCLE TRANSVERSAL and EDGE BIPARTIZATION. For such a graph \(H\), we give a P/NP-complete complexity dichotomy for all three studied problems. Then, we address their parameterized complexity. We show that all VERTEX DELETION \(H\)-COLOURING and EDGE DELETION \(H\)-COLOURING problems for such \(H\) are FPT. This is in contrast with the fact that already for some \(H\) of order~\(3\), unless P=NP, none of the three considered problems is in XP. We show that the situation is different for SWITCHING \(H\)-COLOURING: there are three \(2\)-edge-coloured graphs \(H\) of order \(2\) for which this is W-hard, and assuming the ETH, admits no algorithm in time \(f(k)n^{o(k)}\) for inputs of size \(n\). For the other cases, SWITCHING \(H\)-COLOURING is FPT.