Parameterized complexity of edge-coloured and signed graph
homomorphism problems

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.

Základní údaje

Originální název

Parameterized complexity of edge-coloured and signed graph homomorphism problems

Autoři

FOUCAUD, Florent; Hervé HOCQUARD; Dimitry LAJOU; Valia MITSOU a Théo PIERRON

Vydání

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

Nakladatel

Dagstuhl

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

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

Forma vydání

elektronická verze "online"

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/19:00118539

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-129-0

ISSN

DOI

https://doi.org/10.4230/LIPIcs.IPEC.2019.15

EID Scopus

2-s2.0-85077439671

Klíčová slova anglicky

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

Štítky

core_B, firank_B

Příznaky

Mezinárodní význam, Recenzováno

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

Anotace

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.

Citovat

FOUCAUD, Florent; Hervé HOCQUARD; Dimitry LAJOU; Valia MITSOU a Théo PIERRON. Parameterized complexity of edge-coloured and signed graph homomorphism problems. Online. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Munich: Dagstuhl, 2019, s. "15:1"-"15:16", 16 s. ISBN 978-3-95977-129-0. Dostupné z: https://doi.org/10.4230/LIPIcs.IPEC.2019.15.

@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 = {https://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  - CONF
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 a 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, s.~''15:1''-''15:16'', 16 s. ISBN~978-3-95977-129-0. Dostupné z: https://doi.org/10.4230/LIPIcs.IPEC.2019.15.

Přehled o publikaci