Hardness of Network Satisfaction for Relation Algebras with Normal\n Representations

2019/12/18 by Manuel Bodirsky, Bodirsky, Manuel, Simon Knäuer +1 · 1 citation
Computer Science · #Advanced Algebra and Logic #Advanced Graph Theory Research #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Logic in Computer Science (cs.LO) #Rings and Algebras (math.RA)

paper · pdf · doi:10.48550/arxiv.1912.08482

openalex publication_date 2019/12/18 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28

Abstract

We study the computational complexity of the general network satisfaction\nproblem for a finite relation algebra A with a normal representation B. If\nB contains a non-trivial equivalence relation with a finite number of\nequivalence classes, then the network satisfaction problem for A is NP-hard.\nAs a second result, we prove hardness if B has domain size at least three and\ncontains no non-trivial equivalence relations but a symmetric atom a with a\nforbidden triple (a,a,a), that is, a not\≤ a \∘ a. We illustrate how\nto apply our conditions on two small relation algebras.\n

Cited by

• The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms

Related

• The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms
• Network Satisfaction Problems Solved by k-Consistency
• Circular Chromatic Numbers, Balanceability, Relation Algebras, and Network Satisfaction Problems
• Graphs of relational structures: restricted types
• NP-completeness in the gossip monoid