1 Search Results for "Nakajima, Tamio-Vesa"

Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2022.128
Linearly Ordered Colourings of Hypergraphs

Authors: Tamio-Vesa Nakajima and Stanislav Živný

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
A linearly ordered (LO) k-colouring of an r-uniform hypergraph assigns an integer from {1, …, k} to every vertex so that, in every edge, the (multi)set of colours has a unique maximum. Equivalently, for r = 3, if two vertices in an edge are assigned the same colour, then the third vertex is assigned a larger colour (as opposed to a different colour, as in classic non-monochromatic colouring). Barto, Battistelli, and Berg [STACS'21] studied LO colourings on 3-uniform hypergraphs in the context of promise constraint satisfaction problems (PCSPs). We show two results. First, given a 3-uniform hypergraph that admits an LO 2-colouring, one can find in polynomial time an LO k-colouring with k = O(√{nlog log n}/log n), where n is the number of vertices of the input hypergraph. This is established by building on ideas from algorithms designed for approximate graph colourings. Second, given an r-uniform hypergraph that admits an LO 2-colouring, we establish NP-hardness of finding an LO 3-colouring for every constant uniformity r ≥ 5. In fact, we determine the precise relationship of polymorphism minions for all uniformities r ≥ 3, which reveals a key difference between r = 3,4 and r ≥ 5 and which may be of independent interest. Using the algebraic approach to PCSPs, we actually show a more general result establishing NP-hardness of finding an LO (k+1)-colouring for LO k-colourable r-uniform hypergraphs for k ≥ 2 and r ≥ 5.
Cite as

Tamio-Vesa Nakajima and Stanislav Živný. Linearly Ordered Colourings of Hypergraphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 128:1-128:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{nakajima_et_al:LIPIcs.ICALP.2022.128,
  author =	{Nakajima, Tamio-Vesa and \v{Z}ivn\'{y}, Stanislav},
  title =	{{Linearly Ordered Colourings of Hypergraphs}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{128:1--128:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.128},
  URN =		{urn:nbn:de:0030-drops-164692},
  doi =		{10.4230/LIPIcs.ICALP.2022.128},
  annote =	{Keywords: hypegraph colourings, promise constraint satisfaction, PCSP, polymorphisms, minions, algebraic approach}
}
  • Refine by Author
  • 1 Nakajima, Tamio-Vesa
  • 1 Živný, Stanislav

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

  • Refine by Keyword
  • 1 PCSP
  • 1 algebraic approach
  • 1 hypegraph colourings
  • 1 minions
  • 1 polymorphisms
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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