2026-07-23T10:34:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11476 2024-03-06T10:48:07Z ddc:004 open_access

Parameterized Complexity of Edge-Coloured and Signed Graph Homomorphism Problems Foucaud, Florent Hocquard, Hervé Lajou, Dimitri Mitsou, Valia Pierron, Théo Graph homomorphism Graph modification Edge-coloured graph Signed graph We study the complexity of graph modification problems with respect to homomorphism-based colouring 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, which generalises the classic vertex-colourability property. The question we are interested in is the following: given an edge-coloured graph G, can we perform k graph operations so that the resulting graph admits 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 the signs + and -. We denote the corresponding problems (parameterized by k) by Vertex Deletion-H-Colouring, Edge Deletion-H-Colouring and Switching-H-Colouring. These problems generalise the extensively studied H-Colouring problem (where one has to decide if an input graph admits a homomorphism to a fixed target H). For 2-edge-coloured H, it is known that H-Colouring already captures the complexity of all fixed-target Constraint Satisfaction Problems. Our main focus is on the case where H is an edge-coloured graph of order at most 2, a case that is already interesting since it includes standard problems such as Vertex Cover, Odd Cycle Transversal and Edge Bipartization. For such a graph H, we give a PTime/NP-complete complexity dichotomy for all three Vertex Deletion-H-Colouring, Edge Deletion-H-Colouring and Switching-H-Colouring 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 PTime = NP, none of the three considered problems is in XP, since 3-Colouring is NP-complete. We show that the situation is different for Switching-H-Colouring: there are three 2-edge-coloured graphs H of order 2 for which Switching-H-Colouring is W[1]-hard, and assuming the ETH, admits no algorithm in time f(k)n^{o(k)} for inputs of size n and for any computable function f. For the other cases, Switching-H-Colouring is FPT. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Florent Foucaud and Hervé Hocquard and Dimitri Lajou and Valia Mitsou and Théo Pierron 2019 Is Part Of LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2019.15 urn:nbn:de:0030-drops-114765 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.15 eng https://creativecommons.org/licenses/by/3.0/legalcode