QCSP on reflexive tournaments

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

doi:10.4230/LIPIcs.ESA.2021.58

QCSP on reflexive tournaments

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

^*Corresponding author for this work

School of Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

Abstract

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

Original language	English
Title of host publication	29th Annual European Symposium on Algorithms, ESA 2021
Editors	Petra Mutzel, Rasmus Pagh, Grzegorz Herman
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)	9783959772044
DOIs	https://doi.org/10.4230/LIPIcs.ESA.2021.58
Publication status	Published - 1 Sept 2021
Event	29th Annual European Symposium on Algorithms, ESA 2021 - Vitual, Lisbon, Portugal Duration: 6 Sept 2021 → 8 Sept 2021

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	204
ISSN (Print)	1868-8969

Conference

Conference	29th Annual European Symposium on Algorithms, ESA 2021
Country/Territory	Portugal
City	Vitual, Lisbon
Period	6/09/21 → 8/09/21

Bibliographical note

Funding Information:
Stanislav Živný: 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.

Funding Information:
Funding Stanislav Živný: 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.

Publisher Copyright:
© Benoît Larose, Petar Marković, Barnaby Martin, Daniël Paulusma, Siani Smith, and Stanislav Živný; licensed under Creative Commons License CC-BY 4.0

Keywords

Algorithmic graph theory
Computational complexity
Constraint satisfaction
Quantified constraints
Universal algebra

Access to Document

10.4230/LIPIcs.ESA.2021.58

Handle.net

Persistent link

Cite this

Larose, B., Marković, P., Martin, B., Paulusma, D., Smith, S., & Živný, S. (2021). QCSP on reflexive tournaments. In P. Mutzel, R. Pagh, & G. Herman (Eds.), 29th Annual European Symposium on Algorithms, ESA 2021 Article 58 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 204). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ESA.2021.58

@inproceedings{5e2998ebce53448fbb708694c79fd55f,

title = "QCSP on reflexive tournaments",

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

keywords = "Algorithmic graph theory, Computational complexity, Constraint satisfaction, Quantified constraints, Universal algebra",

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

note = "Funding Information: Stanislav {\v Z}ivn{\'y}: 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. Funding Information: Funding Stanislav {\v Z}ivn{\'y}: 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. Publisher Copyright: {\textcopyright} Beno{\^i}t Larose, Petar Markovi{\'c}, Barnaby Martin, Dani{\"e}l Paulusma, Siani Smith, and Stanislav {\v Z}ivn{\'y}; licensed under Creative Commons License CC-BY 4.0; 29th Annual European Symposium on Algorithms, ESA 2021 ; Conference date: 06-09-2021 Through 08-09-2021",

year = "2021",

month = sep,

day = "1",

doi = "10.4230/LIPIcs.ESA.2021.58",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "Petra Mutzel and Rasmus Pagh and Grzegorz Herman",

booktitle = "29th Annual European Symposium on Algorithms, ESA 2021",

}

Larose, B, Marković, P, Martin, B, Paulusma, D, Smith, S & Živný, S 2021, QCSP on reflexive tournaments. in P Mutzel, R Pagh & G Herman (eds), 29th Annual European Symposium on Algorithms, ESA 2021., 58, Leibniz International Proceedings in Informatics, LIPIcs, vol. 204, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 29th Annual European Symposium on Algorithms, ESA 2021, Vitual, Lisbon, Portugal, 6/09/21. https://doi.org/10.4230/LIPIcs.ESA.2021.58

QCSP on reflexive tournaments. / Larose, Benoît; Marković, Petar; Martin, Barnaby et al.
29th Annual European Symposium on Algorithms, ESA 2021. ed. / Petra Mutzel; Rasmus Pagh; Grzegorz Herman. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2021. 58 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 204).

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

TY - GEN

T1 - QCSP on reflexive tournaments

AU - Larose, Benoît

AU - Marković, Petar

AU - Martin, Barnaby

AU - Paulusma, Daniël

AU - Smith, Siani

AU - Živný, Stanislav

N1 - Funding Information: Stanislav Živný: 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. Funding Information: Funding Stanislav Živný: 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. Publisher Copyright: © Benoît Larose, Petar Marković, Barnaby Martin, Daniël Paulusma, Siani Smith, and Stanislav Živný; licensed under Creative Commons License CC-BY 4.0

PY - 2021/9/1

Y1 - 2021/9/1

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

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

KW - Algorithmic graph theory

KW - Computational complexity

KW - Constraint satisfaction

KW - Quantified constraints

KW - Universal algebra

UR - http://www.scopus.com/inward/record.url?scp=85115092882&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ESA.2021.58

DO - 10.4230/LIPIcs.ESA.2021.58

M3 - Conference Contribution (Conference Proceeding)

AN - SCOPUS:85115092882

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 29th Annual European Symposium on Algorithms, ESA 2021

A2 - Mutzel, Petra

A2 - Pagh, Rasmus

A2 - Herman, Grzegorz

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 29th Annual European Symposium on Algorithms, ESA 2021

Y2 - 6 September 2021 through 8 September 2021

ER -

QCSP on reflexive tournaments

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Handle.net

Other files and links

Fingerprint

Cite this