D 2019

Parameterized complexity of edge-coloured and signed graph homomorphism problems

FOUCAUD, Florent, Hervé HOCQUARD, Dimitry LAJOU, Valia MITSOU, Théo PIERRON et. al.

Basic information

Original name

Parameterized complexity of edge-coloured and signed graph homomorphism problems

Authors

FOUCAUD, Florent, Hervé HOCQUARD, Dimitry LAJOU, Valia MITSOU and Théo PIERRON (250 France, guarantor, belonging to the institution)

Edition

Munich, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019), p. "15:1"-"15:16", 16 pp. 2019

Publisher

Dagstuhl

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United States of America

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

electronic version available online

RIV identification code

RIV/00216224:14330/19:00118539

Organization unit

Faculty of Informatics

ISBN

978-3-95977-129-0

ISSN

DOI

Keywords in English

edge-coloured graph;graph homomorphism;graph modification;signed graph

Tags

Tags

International impact, Reviewed
Změněno: 5/11/2021 14:58, RNDr. Pavel Šmerk, Ph.D.

Abstract

V originále

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.