Computational complexity of covering three-vertex multigraphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10331737" target="_blank" >RIV/00216208:11320/16:10331737 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.tcs.2015.09.013" target="_blank" >http://dx.doi.org/10.1016/j.tcs.2015.09.013</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.tcs.2015.09.013" target="_blank" >10.1016/j.tcs.2015.09.013</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Computational complexity of covering three-vertex multigraphs

Popis výsledku v původním jazyce

A covering projection from a graph G onto a graph H is a mapping of the vertices of G onto the vertices of H such that, for every vertex v of G, the neighborhood of v is mapped bijectively onto the neighborhood of its image. Moreover, if G and H are multigraphs, then this local bijection has to preserve multiplicities of the neighbors as well. The notion of covering projection stems from topology, but has found applications in areas such as the theory of local computation and construction of highly symmetric graphs. It provides a restrictive variant of the constraint satisfaction problem with additional symmetry constraints on the behavior of the homomorphisms of the structures involved. We investigate the computational complexity of the problem of deciding the existence of a covering projection from an input graph G to a fixed target graph H. Among other partial results this problem has been shown NP-hard for simple regular graphs H of valency greater than 2, and a full characterization of computational complexity has been shown for target multigraphs with 2 vertices. We extend the previously known results to the ternary case, i.e., we give a full characterization of the computational complexity in the case of multigraphs with 3 vertices. We show that even in this case a P/NP-completeness dichotomy holds.

Název v anglickém jazyce

Computational complexity of covering three-vertex multigraphs

Popis výsledku anglicky

A covering projection from a graph G onto a graph H is a mapping of the vertices of G onto the vertices of H such that, for every vertex v of G, the neighborhood of v is mapped bijectively onto the neighborhood of its image. Moreover, if G and H are multigraphs, then this local bijection has to preserve multiplicities of the neighbors as well. The notion of covering projection stems from topology, but has found applications in areas such as the theory of local computation and construction of highly symmetric graphs. It provides a restrictive variant of the constraint satisfaction problem with additional symmetry constraints on the behavior of the homomorphisms of the structures involved. We investigate the computational complexity of the problem of deciding the existence of a covering projection from an input graph G to a fixed target graph H. Among other partial results this problem has been shown NP-hard for simple regular graphs H of valency greater than 2, and a full characterization of computational complexity has been shown for target multigraphs with 2 vertices. We extend the previously known results to the ternary case, i.e., we give a full characterization of the computational complexity in the case of multigraphs with 3 vertices. We show that even in this case a P/NP-completeness dichotomy holds.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2016

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

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Svazek periodika

609

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

14

Strana od-do

104-117

Kód UT WoS článku

000367488400008

EID výsledku v databázi Scopus

2-s2.0-84948844353