Parameterized complexity of edge-coloured and signed graph homomorphism problems
share
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.
READ FULL TEXT