QCSP on Reflexive Tournaments

Benoît Larose; Barnaby Martin; Petar Marković; Daniël Paulusma; Siani Smith; Stanislav Živný

doi:10.1145/3508069

QCSP on Reflexive Tournaments

Benoît Larose, Barnaby Martin, Petar Marković, Daniël Paulusma, Siani Smith, Stanislav Živný

School of Mathematics

Research output: Contribution to journal › Article (Academic Journal) › peer-review

2 Citations (Scopus)

Abstract

We give a complexity dichotomy for the Quantified Constraint Satisfaction Problem when is a reflexive tournament. It is well known that reflexive tournaments can be split into a sequence of strongly connected components so that there exists an edge from every vertex of to every vertex of if and only if . We prove that if has both its initial and final strongly connected component (possibly equal) of size 1, then is in and otherwise is -hard.

Original language	English
Article number	14
Journal	ACM Transactions on Computational Logic
Volume	23
Issue number	3
DOIs	https://doi.org/10.1145/3508069
Publication status	Published - Jul 2022

Bibliographical note

Funding Information:
Benoît Larose, Petar Markovic, Barnaby Martin, Daniël Paulusma, Siani Smith, and Stanislav Zivný. 2021. QCSP on reflexive tournaments. In 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), Vol. 204. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 58:1–58:15. Petar Marković was supported by the Ministry of Education, Science and Technological Development of the Republic of Serbia (Grant No. 451-03-68/2002-14/200125). Stanislav Zivny was supported by a Royal Society University Research Fellowship. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 714532). The paper reflects only the authors’ views and not the views of the ERC or the European Commission. The European Union is not liable for any use that may be made of the information contained therein. Authors’ addresses: B. Larose, LaCIM, Université du Québec à Montréal, Case Postale. 8888, succursale Centre-ville, Mon-tréal, Québec H3C 3P8, Canada; email: [email protected]; B. Martin, D. Paulusma, and S. Smith, Department of Computer Science, Durham University, South Road, Durham, Dh1 3LE, UK; emails: [email protected], {daniel.paulusma, siani.smith}@durham.ac.uk; P. Marković, Department of Mathematics and Informatics, University of Novi Sad, Dositeja Obradović Square 4, 21000 Novi Sad, Serbia; email: [email protected]; S. Živný, Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, Oxford, OX1 3QD, UK; email: [email protected]. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. © 2022 Association for Computing Machinery. 1529-3785/2022/04-ART14 $15.00 https://doi.org/10.1145/3508069

Publisher Copyright:
© 2022 Association for Computing Machinery.

Keywords

computational complexity
constraint satisfaction
graph theorem
logic
Quantified constraints

Access to Document

10.1145/3508069

Handle.net

Persistent link

Cite this

@article{141d9938f2034ffe999967d6c2969bb9,

title = "QCSP on Reflexive Tournaments",

abstract = "We give a complexity dichotomy for the Quantified Constraint Satisfaction Problem when is a reflexive tournament. It is well known that reflexive tournaments can be split into a sequence of strongly connected components so that there exists an edge from every vertex of to every vertex of if and only if . We prove that if has both its initial and final strongly connected component (possibly equal) of size 1, then is in and otherwise is -hard.",

keywords = "computational complexity, constraint satisfaction, graph theorem, logic, Quantified constraints",

author = "Beno{\^i}t Larose and Barnaby Martin and Petar Markovi{\'c} and Dani{\"e}l Paulusma and Siani Smith and Stanislav {\v Z}ivn{\'y}",

note = "Funding Information: Beno{\^i}t Larose, Petar Markovic, Barnaby Martin, Dani{\"e}l Paulusma, Siani Smith, and Stanislav Zivn{\'y}. 2021. QCSP on reflexive tournaments. In 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), Vol. 204. Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik, 58:1–58:15. Petar Markovi{\'c} was supported by the Ministry of Education, Science and Technological Development of the Republic of Serbia (Grant No. 451-03-68/2002-14/200125). Stanislav Zivny was supported by a Royal Society University Research Fellowship. This project has received funding from the European Research Council (ERC) under the European Union{\textquoteright}s Horizon 2020 research and innovation programme (grant agreement No 714532). The paper reflects only the authors{\textquoteright} views and not the views of the ERC or the European Commission. The European Union is not liable for any use that may be made of the information contained therein. Authors{\textquoteright} addresses: B. Larose, LaCIM, Universit{\'e} du Qu{\'e}bec {\`a} Montr{\'e}al, Case Postale. 8888, succursale Centre-ville, Mon-tr{\'e}al, Qu{\'e}bec H3C 3P8, Canada; email: [email protected]; B. Martin, D. Paulusma, and S. Smith, Department of Computer Science, Durham University, South Road, Durham, Dh1 3LE, UK; emails: [email protected], \{daniel.paulusma, siani.smith\}@durham.ac.uk; P. Markovi{\'c}, Department of Mathematics and Informatics, University of Novi Sad, Dositeja Obradovi{\'c} Square 4, 21000 Novi Sad, Serbia; email: [email protected]; S. {\v Z}ivn{\'y}, Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, Oxford, OX1 3QD, UK; email: [email protected]. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. {\textcopyright} 2022 Association for Computing Machinery. 1529-3785/2022/04-ART14 \$15.00 https://doi.org/10.1145/3508069 Publisher Copyright: {\textcopyright} 2022 Association for Computing Machinery.",

year = "2022",

month = jul,

doi = "10.1145/3508069",

language = "English",

volume = "23",

journal = "ACM Transactions on Computational Logic",

issn = "1529-3785",

publisher = "Association for Computing Machinery",

number = "3",

}

TY - JOUR

T1 - QCSP on Reflexive Tournaments

AU - Larose, Benoît

AU - Martin, Barnaby

AU - Marković, Petar

AU - Paulusma, Daniël

AU - Smith, Siani

AU - Živný, Stanislav

N1 - Funding Information: Benoît Larose, Petar Markovic, Barnaby Martin, Daniël Paulusma, Siani Smith, and Stanislav Zivný. 2021. QCSP on reflexive tournaments. In 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), Vol. 204. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 58:1–58:15. Petar Marković was supported by the Ministry of Education, Science and Technological Development of the Republic of Serbia (Grant No. 451-03-68/2002-14/200125). Stanislav Zivny was supported by a Royal Society University Research Fellowship. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 714532). The paper reflects only the authors’ views and not the views of the ERC or the European Commission. The European Union is not liable for any use that may be made of the information contained therein. Authors’ addresses: B. Larose, LaCIM, Université du Québec à Montréal, Case Postale. 8888, succursale Centre-ville, Mon-tréal, Québec H3C 3P8, Canada; email: [email protected]; B. Martin, D. Paulusma, and S. Smith, Department of Computer Science, Durham University, South Road, Durham, Dh1 3LE, UK; emails: [email protected], {daniel.paulusma, siani.smith}@durham.ac.uk; P. Marković, Department of Mathematics and Informatics, University of Novi Sad, Dositeja Obradović Square 4, 21000 Novi Sad, Serbia; email: [email protected]; S. Živný, Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, Oxford, OX1 3QD, UK; email: [email protected]. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. © 2022 Association for Computing Machinery. 1529-3785/2022/04-ART14 $15.00 https://doi.org/10.1145/3508069 Publisher Copyright: © 2022 Association for Computing Machinery.

PY - 2022/7

Y1 - 2022/7

N2 - We give a complexity dichotomy for the Quantified Constraint Satisfaction Problem when is a reflexive tournament. It is well known that reflexive tournaments can be split into a sequence of strongly connected components so that there exists an edge from every vertex of to every vertex of if and only if . We prove that if has both its initial and final strongly connected component (possibly equal) of size 1, then is in and otherwise is -hard.

AB - We give a complexity dichotomy for the Quantified Constraint Satisfaction Problem when is a reflexive tournament. It is well known that reflexive tournaments can be split into a sequence of strongly connected components so that there exists an edge from every vertex of to every vertex of if and only if . We prove that if has both its initial and final strongly connected component (possibly equal) of size 1, then is in and otherwise is -hard.

KW - computational complexity

KW - constraint satisfaction

KW - graph theorem

KW - logic

KW - Quantified constraints

UR - https://www.scopus.com/pages/publications/85135073960

U2 - 10.1145/3508069

DO - 10.1145/3508069

M3 - Article (Academic Journal)

AN - SCOPUS:85135073960

SN - 1529-3785

VL - 23

JO - ACM Transactions on Computational Logic

JF - ACM Transactions on Computational Logic

IS - 3

M1 - 14

ER -

QCSP on Reflexive Tournaments

Abstract

Bibliographical note

Keywords

Access to Document

Handle.net

Other files and links

Fingerprint

Cite this