License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2019.15
URN: urn:nbn:de:0030-drops-114765
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11476/
Foucaud, Florent ;
Hocquard, Hervé ;
Lajou, Dimitri ;
Mitsou, Valia ;
Pierron, Théo
Parameterized Complexity of Edge-Coloured and Signed Graph Homomorphism Problems
Abstract
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.
BibTeX - Entry
@InProceedings{foucaud_et_al:LIPIcs:2019:11476,
author = {Florent Foucaud and Herv{\'e} Hocquard and Dimitri Lajou and Valia Mitsou and Th{\'e}o Pierron},
title = {{Parameterized Complexity of Edge-Coloured and Signed Graph Homomorphism Problems}},
booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
pages = {15:1--15:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-129-0},
ISSN = {1868-8969},
year = {2019},
volume = {148},
editor = {Bart M. P. Jansen and Jan Arne Telle},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11476},
URN = {urn:nbn:de:0030-drops-114765},
doi = {10.4230/LIPIcs.IPEC.2019.15},
annote = {Keywords: Graph homomorphism, Graph modification, Edge-coloured graph, Signed graph}
}
|
Keywords: |
|
Graph homomorphism, Graph modification, Edge-coloured graph, Signed graph |
|
Collection: |
|
14th International Symposium on Parameterized and Exact Computation (IPEC 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
04.12.2019 |
