1 Search Results for "Brewster, Richard"

Document

DOI: 10.4230/LIPIcs.MFCS.2020.20

List Homomorphism Problems for Signed Graphs

Authors: Jan Bok, Richard Brewster, Tomás Feder, Pavol Hell, and Nikola Jedličková

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract

We consider homomorphisms of signed graphs from a computational perspective. In particular, we study the list homomorphism problem seeking a homomorphism of an input signed graph (G,σ), equipped with lists L(v) ⊆ V(H), v ∈ V(G), of allowed images, to a fixed target signed graph (H,π). The complexity of the similar homomorphism problem without lists (corresponding to all lists being L(v) = V(H)) has been previously classified by Brewster and Siggers, but the list version remains open and appears difficult. Both versions (with lists or without lists) can be formulated as constraint satisfaction problems, and hence enjoy the algebraic dichotomy classification recently verified by Bulatov and Zhuk. By contrast, we seek a combinatorial classification for the list version, akin to the combinatorial classification for the version without lists completed by Brewster and Siggers. We illustrate the possible complications by classifying the complexity of the list homomorphism problem when H is a (reflexive or irreflexive) signed tree. It turns out that the problems are polynomial-time solvable for certain caterpillar-like trees, and are NP-complete otherwise. The tools we develop will be useful for classifications of other classes of signed graphs, and we mention some follow-up research of this kind; those classifications are surprisingly complex.

Cite as

Jan Bok, Richard Brewster, Tomás Feder, Pavol Hell, and Nikola Jedličková. List Homomorphism Problems for Signed Graphs. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bok_et_al:LIPIcs.MFCS.2020.20,
  author =	{Bok, Jan and Brewster, Richard and Feder, Tom\'{a}s and Hell, Pavol and Jedli\v{c}kov\'{a}, Nikola},
  title =	{{List Homomorphism Problems for Signed Graphs}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.20},
  URN =		{urn:nbn:de:0030-drops-126886},
  doi =		{10.4230/LIPIcs.MFCS.2020.20},
  annote =	{Keywords: complexity, dichotomy, graph homomorphism, signed graph}
}

Refine by Author
1 Bok, Jan
1 Brewster, Richard
1 Feder, Tomás
1 Hell, Pavol
1 Jedličková, Nikola

Refine by Classification
1 Mathematics of computing → Graph theory

Refine by Keyword
1 complexity
1 dichotomy
1 graph homomorphism
1 signed graph

Refine by Type
1 document

Refine by Publication Year
1 2020

1 Search Results for "Brewster, Richard"

List Homomorphism Problems for Signed Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message