Network Satisfaction for Symmetric Relation Algebras with a Flexible Atom
Abstract
Robin Hirsch posed in 1996 the Really Big Complexity Problem: classify the computational complexity of the network satisfaction problem for all finite relation algebras A. We provide a complete classification for the case that A is symmetric and has a flexible atom; the problem is in this case NP-complete or in P. If a finite integral relation algebra has a flexible atom, then it has a normal representation B. We can then study the computational complexity of the network satisfaction problem of A using the universal-algebraic approach, via an analysis of the polymorphisms of B. We also use a Ramsey-type result of Nešetřil and Rödl and a complexity dichotomy result of Bulatov for conservative finite-domain constraint satisfaction problems.
Cite
Text
Bodirsky and Knäuer. "Network Satisfaction for Symmetric Relation Algebras with a Flexible Atom." AAAI Conference on Artificial Intelligence, 2021. doi:10.1609/AAAI.V35I7.16773Markdown
[Bodirsky and Knäuer. "Network Satisfaction for Symmetric Relation Algebras with a Flexible Atom." AAAI Conference on Artificial Intelligence, 2021.](https://mlanthology.org/aaai/2021/bodirsky2021aaai-network/) doi:10.1609/AAAI.V35I7.16773BibTeX
@inproceedings{bodirsky2021aaai-network,
title = {{Network Satisfaction for Symmetric Relation Algebras with a Flexible Atom}},
author = {Bodirsky, Manuel and Knäuer, Simon},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2021},
pages = {6218-6226},
doi = {10.1609/AAAI.V35I7.16773},
url = {https://mlanthology.org/aaai/2021/bodirsky2021aaai-network/}
}