Graph Modification for Edge-Coloured and Signed Graph Homomorphism Problems: Parameterized and Classical Complexity

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F22%3A00128979" target="_blank" >RIV/00216224:14330/22:00128979 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/s00453-021-00918-4" target="_blank" >https://doi.org/10.1007/s00453-021-00918-4</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00453-021-00918-4" target="_blank" >10.1007/s00453-021-00918-4</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Graph Modification for Edge-Coloured and Signed Graph Homomorphism Problems: Parameterized and Classical Complexity

Popis výsledku v původním jazyce

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 VD-H- COLOURING, ED-H-COLOURING and SW-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 with at most two vertices, 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 P/NP-complete complexity dichotomy for all three VD-H-COLOURING, ED-H-COLOURING and SW-H-COLOURING problems. Then, we address their parameterized complexity. We show that all VD-H-COLOURING and ED-H-COLOURING problems for such H are FPT. This is in contrast with the fact that already for some H of order 3, unless P = NP, none of the three considered problems is in XP, since 3- COLOURING is NP-complete. We show that the situation is different for SW-H-CoLouRING: there are three 2-edge-coloured graphs H of order 2 for which SW-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, SW-H-COLOURING is FPT.

Název v anglickém jazyce

Graph Modification for Edge-Coloured and Signed Graph Homomorphism Problems: Parameterized and Classical Complexity

Popis výsledku anglicky

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 VD-H- COLOURING, ED-H-COLOURING and SW-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 with at most two vertices, 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 P/NP-complete complexity dichotomy for all three VD-H-COLOURING, ED-H-COLOURING and SW-H-COLOURING problems. Then, we address their parameterized complexity. We show that all VD-H-COLOURING and ED-H-COLOURING problems for such H are FPT. This is in contrast with the fact that already for some H of order 3, unless P = NP, none of the three considered problems is in XP, since 3- COLOURING is NP-complete. We show that the situation is different for SW-H-CoLouRING: there are three 2-edge-coloured graphs H of order 2 for which SW-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, SW-H-COLOURING is FPT.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2022

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Algorithmica

ISSN

0178-4617

e-ISSN

—

Svazek periodika

84

Číslo periodika v rámci svazku

5

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

30

Strana od-do

1183-1212

Kód UT WoS článku

000738510500001

EID výsledku v databázi Scopus

2-s2.0-85122318971