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:
-
-
(Preview, Version of record, 741.4KB, Terms of use)
-
- Publisher copy:
- 10.4230/LIPIcs.ESA.2021.58
Authors
- 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
- Copyright holder:
- Larose et al.
- Copyright date:
- 2021
- Rights statement:
- © Benoît Larose, Petar Marković, Barnaby Martin, Daniël Paulusma, Siani Smith, and Stanislav Živný; licensed under Creative Commons License CC-BY 4.0.
- Notes:
- This paper was presented at the 29th Annual European Symposium on Algorithms (ESA 2021), 6th-8th September 2021, Lisbon, Portugal.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record