DROPS

Document

Track B: Automata, Logic, Semantics, and Theory of Programming

DOI: 10.4230/LIPIcs.ICALP.2026.168

The Network Satisfaction Problem for Relation Algebras with at Most 4 Atoms

Authors: Manuel Bodirsky, Moritz Jahn, Simon Knäuer, Matěj Konečný, and Paul Winkler

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

Andréka and Maddux classified the relation algebras with at most 3 atoms, and in particular they showed that all of them are representable [Hajnal Andréka and Roger D. Maddux, 1994]. Hirsch and Cristiani showed that the network satisfaction problem (NSP) for each of these algebras is in P or NP-hard [Matteo Cristiani and Robin Hirsch, 2004]. The literature contains many results on representations of relation algebras; in particular, some relation algebras with four atoms are not representable. We extend the result of Cristiani and Hirsch to relation algebras with at most 4 atoms: the NSP is always either in P or NP-hard. To this end, we construct universal, fully universal, or even normal representations for these algebras, whenever possible.

Cite as

Manuel Bodirsky, Moritz Jahn, Simon Knäuer, Matěj Konečný, and Paul Winkler. The Network Satisfaction Problem for Relation Algebras with at Most 4 Atoms. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 168:1-168:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bodirsky_et_al:LIPIcs.ICALP.2026.168,
  author =	{Bodirsky, Manuel and Jahn, Moritz and Kn\"{a}uer, Simon and Kone\v{c}n\'{y}, Mat\v{e}j and Winkler, Paul},
  title =	{{The Network Satisfaction Problem for Relation Algebras with at Most 4 Atoms}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{168:1--168:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.168},
  URN =		{urn:nbn:de:0030-drops-265564},
  doi =		{10.4230/LIPIcs.ICALP.2026.168},
  annote =	{Keywords: Constraint Satisfaction, Computational Complexity, Relation Algebras, Network Satisfaction, Normal Representations, Polynomial-Time Algorithms}
}

@InProceedings{bodirsky_et_al:LIPIcs.ICALP.2026.168,
  author =	{Bodirsky, Manuel and Jahn, Moritz and Kn\"{a}uer, Simon and Kone\v{c}n\'{y}, Mat\v{e}j and Winkler, Paul},
  title =	{{The Network Satisfaction Problem for Relation Algebras with at Most 4 Atoms}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{168:1--168:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.168},
  URN =		{urn:nbn:de:0030-drops-265564},
  doi =		{10.4230/LIPIcs.ICALP.2026.168},
  annote =	{Keywords: Constraint Satisfaction, Computational Complexity, Relation Algebras, Network Satisfaction, Normal Representations, Polynomial-Time Algorithms}
}

Search Results

Documents authored by Jahn, Moritz

The Network Satisfaction Problem for Relation Algebras with at Most 4 Atoms

Abstract

Cite as

Thanks for your feedback!

Could not send message