Conference item icon

Conference item

QCSP on reflexive tournaments

Abstract:
We give a complexity dichotomy for the Quantified Constraint Satisfaction Problem QCSP(H) when H is a reflexive 22 tournament. It is well-known that reflexive tournaments can be split into a sequence of strongly connected 23 components H1, . . . , Hn so that there exists an edge from every vertex of Hi to every vertex of Hj if and only if 24 i < j. We prove that if H has both its initial and final strongly connected component (possibly equal) of size 1, 25 then QCSP(H) is in NL and otherwise QCSP(H) is NP-hard.
Publication status:
Accepted
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.4230/LIPIcs.ESA.2021.58

Authors


More from this funder
Name:
Royal Society
Grant:
URF\R\180000
More from this funder
Name:
European Commission
Grant:
714532
Publisher:
Schloss Dagstuhl
Host title:
Proceedings of the European Symposium on Algorithms (ESA)
Volume:
204
Issue:
2021
Pages:
58:1--58:15
Publication date:
2021-08-31
Acceptance date:
2021-06-23
Event title:
29th Annual European Symposium on Algorithms (ESA 2021)
Event location:
Lisbon, Portugal
Event website:
http://algo2021.tecnico.ulisboa.pt/ESA2021/
Event start date:
2021-09-06
Event end date:
2021-09-08
DOI:
ISSN:
1868-8969
ISBN:
978-3-95977-204-4
Language:
English
Keywords:
Pubs id:
1183170
Local pid:
pubs:1183170
Deposit date:
2021-06-23

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP