Other formats:
BibTeX
LaTeX
RIS
@inproceedings{1763063,
author = {Foucaud, Florent and Hocquard, Hervé and Lajou, Dimitry and Mitsou, Valia and Pierron, Théo},
address = {Munich},
booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
doi = {http://dx.doi.org/10.4230/LIPIcs.IPEC.2019.15},
keywords = {edge-coloured graph;graph homomorphism;graph modification;signed graph},
howpublished = {elektronická verze "online"},
language = {eng},
location = {Munich},
isbn = {978-3-95977-129-0},
pages = {"15:1"-"15:16"},
publisher = {Dagstuhl},
title = {Parameterized complexity of edge-coloured and signed graph homomorphism problems},
year = {2019}
}
TY - JOUR
ID - 1763063
AU - Foucaud, Florent - Hocquard, Hervé - Lajou, Dimitry - Mitsou, Valia - Pierron, Théo
PY - 2019
TI - Parameterized complexity of edge-coloured and signed graph homomorphism problems
PB - Dagstuhl
CY - Munich
SN - 9783959771290
KW - edge-coloured graph;graph homomorphism;graph modification;signed graph
N2 - 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.
ER -
FOUCAUD, Florent, Hervé HOCQUARD, Dimitry LAJOU, Valia MITSOU and Théo PIERRON. Parameterized complexity of edge-coloured and signed graph homomorphism problems. Online. In \textit{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}. Munich: Dagstuhl, 2019, p.~''15:1''-''15:16'', 16 pp. ISBN~978-3-95977-129-0. Available from: https://dx.doi.org/10.4230/LIPIcs.IPEC.2019.15.
|
