Foucaud, Florent ;
Hocquard, Hervé ;
Lajou, Dimitri ;
Mitsou, Valia ;
Pierron, Théo
Parameterized Complexity of EdgeColoured and Signed Graph Homomorphism Problems
Abstract
We study the complexity of graph modification problems with respect to homomorphismbased colouring properties of edgecoloured graphs. A homomorphism from an edgecoloured graph G to an edgecoloured graph H is a vertexmapping from G to H that preserves adjacencies and edgecolours. We consider the property of having a homomorphism to a fixed edgecoloured graph H, which generalises the classic vertexcolourability property. The question we are interested in is the following: given an edgecoloured graph G, can we perform k graph operations so that the resulting graph admits a homomorphism to H? The operations we consider are vertexdeletion, edgedeletion 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 2edgecoloured graphs whose colours are the signs + and . We denote the corresponding problems (parameterized by k) by Vertex DeletionHColouring, Edge DeletionHColouring and SwitchingHColouring. These problems generalise the extensively studied HColouring problem (where one has to decide if an input graph admits a homomorphism to a fixed target H). For 2edgecoloured H, it is known that HColouring already captures the complexity of all fixedtarget Constraint Satisfaction Problems.
Our main focus is on the case where H is an edgecoloured 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/NPcomplete complexity dichotomy for all three Vertex DeletionHColouring, Edge DeletionHColouring and SwitchingHColouring problems. Then, we address their parameterized complexity. We show that all Vertex DeletionHColouring and Edge DeletionHColouring 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 3Colouring is NPcomplete. We show that the situation is different for SwitchingHColouring: there are three 2edgecoloured graphs H of order 2 for which SwitchingHColouring 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, SwitchingHColouring 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 EdgeColoured and Signed Graph Homomorphism Problems}},
booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
pages = {15:115:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771290},
ISSN = {18688969},
year = {2019},
volume = {148},
editor = {Bart M. P. Jansen and Jan Arne Telle},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11476},
URN = {urn:nbn:de:0030drops114765},
doi = {10.4230/LIPIcs.IPEC.2019.15},
annote = {Keywords: Graph homomorphism, Graph modification, Edgecoloured graph, Signed graph}
}
04.12.2019
Keywords: 

Graph homomorphism, Graph modification, Edgecoloured graph, Signed graph 
Seminar: 

14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Issue date: 

2019 
Date of publication: 

04.12.2019 