3 Search Results for "Brandts, Alex"

Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.169
Complexity of Approximate Conflict-Free, Linearly-Ordered, and Nonmonochromatic Hypergraph Colourings

Authors: Tamio-Vesa Nakajima, Zephyr Verwimp, Marcin Wrochna, and Stanislav Živný

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Using the algebraic approach to promise constraint satisfaction problems, we establish complexity classifications of three natural variants of hypergraph colourings: standard nonmonochromatic colourings, conflict-free colourings, and linearly-ordered colourings. Firstly, we show that finding an 𝓁-colouring of a k-colourable r-uniform hypergraph is NP-hard for all constant 2 ≤ k ≤ 𝓁 and r ≥ 3. This provides a shorter proof of a celebrated result by Dinur et al. [FOCS'02/Combinatorica'05]. Secondly, we show that finding an 𝓁-conflict-free colouring of an r-uniform hypergraph that admits a k-conflict-free colouring is NP-hard for all constant 2 ≤ k ≤ 𝓁 and r ≥ 4, except for r = 4 and k = 2 (and any 𝓁); this case is solvable in polynomial time. The case of r = 3 is the standard nonmonochromatic colouring, and the case of r = 2 is the notoriously difficult open problem of approximate graph colouring. Thirdly, we show that finding an 𝓁-linearly-ordered colouring of an r-uniform hypergraph that admits a k-linearly-ordered colouring is NP-hard for all constant 3 ≤ k ≤ 𝓁 and r ≥ 4, thus improving on the results of Nakajima and Živný [ICALP'22/ACM TocT'23].
Cite as

Tamio-Vesa Nakajima, Zephyr Verwimp, Marcin Wrochna, and Stanislav Živný. Complexity of Approximate Conflict-Free, Linearly-Ordered, and Nonmonochromatic Hypergraph Colourings. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 169:1-169:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{nakajima_et_al:LIPIcs.ICALP.2025.169,
  author =	{Nakajima, Tamio-Vesa and Verwimp, Zephyr and Wrochna, Marcin and \v{Z}ivn\'{y}, Stanislav},
  title =	{{Complexity of Approximate Conflict-Free, Linearly-Ordered, and Nonmonochromatic Hypergraph Colourings}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{169:1--169:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.169},
  URN =		{urn:nbn:de:0030-drops-235460},
  doi =		{10.4230/LIPIcs.ICALP.2025.169},
  annote =	{Keywords: hypergraph colourings, conflict-free colourings, unique-maximum colourings, linearly-ordered colourings}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2021.121
Beyond PCSP(1-in-3, NAE)

Authors: Alex Brandts and Stanislav Živný

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
The promise constraint satisfaction problem (PCSP) is a recently introduced vast generalisation of the constraint satisfaction problem (CSP) that captures approximability of satisfiable instances. A PCSP instance comes with two forms of each constraint: a strict one and a weak one. Given the promise that a solution exists using the strict constraints, the task is to find a solution using the weak constraints. While there are by now several dichotomy results for fragments of PCSPs, they all consider (in some way) symmetric PCSPs. 1-in-3-SAT and Not-All-Equal-3-SAT are classic examples of Boolean symmetric (non-promise) CSPs. While both problems are NP-hard, Brakensiek and Guruswami showed [SODA'18] that given a satisfiable instance of 1-in-3-SAT one can find a solution to the corresponding instance of (weaker) Not-All-Equal-3-SAT. In other words, the PCSP template (𝟏-in-𝟑,NAE) is tractable. We focus on non-symmetric PCSPs. In particular, we study PCSP templates obtained from the Boolean template (𝐭-in-𝐤, NAE) by either adding tuples to 𝐭-in-𝐤 or removing tuples from NAE. For the former, we classify all templates as either tractable or not solvable by the currently strongest known algorithm for PCSPs, the combined basic LP and affine IP relaxation of Brakensiek and Guruswami [SODA'20]. For the latter, we classify all templates as either tractable or NP-hard.
Cite as

Alex Brandts and Stanislav Živný. Beyond PCSP(1-in-3, NAE). In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 121:1-121:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{brandts_et_al:LIPIcs.ICALP.2021.121,
  author =	{Brandts, Alex and \v{Z}ivn\'{y}, Stanislav},
  title =	{{Beyond PCSP(1-in-3, NAE)}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{121:1--121:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.121},
  URN =		{urn:nbn:de:0030-drops-141902},
  doi =		{10.4230/LIPIcs.ICALP.2021.121},
  annote =	{Keywords: promise constraint satisfaction, PCSP, polymorphisms, algebraic approach}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.17
The Complexity of Promise SAT on Non-Boolean Domains

Authors: Alex Brandts, Marcin Wrochna, and Stanislav Živný

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
While 3-SAT is NP-hard, 2-SAT is solvable in polynomial time. Austrin, Guruswami, and Håstad [FOCS'14/SICOMP'17] proved a result known as "(2+ε)-SAT is NP-hard". They showed that the problem of distinguishing k-CNF formulas that are g-satisfiable (i.e. some assignment satisfies at least g literals in every clause) from those that are not even 1-satisfiable is NP-hard if g/k < 1/2 and is in P otherwise. We study a generalisation of SAT on arbitrary finite domains, with clauses that are disjunctions of unary constraints, and establish analogous behaviour. Thus we give a dichotomy for a natural fragment of promise constraint satisfaction problems (PCSPs) on arbitrary finite domains.
Cite as

Alex Brandts, Marcin Wrochna, and Stanislav Živný. The Complexity of Promise SAT on Non-Boolean Domains. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 17:1-17:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{brandts_et_al:LIPIcs.ICALP.2020.17,
  author =	{Brandts, Alex and Wrochna, Marcin and \v{Z}ivn\'{y}, Stanislav},
  title =	{{The Complexity of Promise SAT on Non-Boolean Domains}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{17:1--17:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.17},
  URN =		{urn:nbn:de:0030-drops-124241},
  doi =		{10.4230/LIPIcs.ICALP.2020.17},
  annote =	{Keywords: promise constraint satisfaction, PCSP, polymorphisms, algebraic approach, label cover}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2021
  • 1 2020

  • Refine by Author
  • 3 Živný, Stanislav
  • 2 Brandts, Alex
  • 2 Wrochna, Marcin
  • 1 Nakajima, Tamio-Vesa
  • 1 Verwimp, Zephyr

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 3 Theory of computation → Constraint and logic programming
  • 3 Theory of computation → Problems, reductions and completeness
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 2 PCSP
  • 2 algebraic approach
  • 2 polymorphisms
  • 2 promise constraint satisfaction
  • 1 conflict-free colourings
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact