License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2021.31
URN: urn:nbn:de:0030-drops-134650
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13465/
Go to the corresponding LIPIcs Volume Portal

Lichter, Moritz ; Schweitzer, Pascal

Canonization for Bounded and Dihedral Color Classes in Choiceless Polynomial Time

pdf-format:
LIPIcs-CSL-2021-31.pdf (0.6 MB)

Abstract

In the quest for a logic capturing Ptime the next natural classes of structures to consider are those with bounded color class size. We present a canonization procedure for graphs with dihedral color classes of bounded size in the logic of Choiceless Polynomial Time (CPT), which then captures Ptime on this class of structures. This is the first result of this form for non-abelian color classes.
The first step proposes a normal form which comprises a "rigid assemblage". This roughly means that the local automorphism groups form 2-injective 3-factor subdirect products. Structures with color classes of bounded size can be reduced canonization preservingly to normal form in CPT.
In the second step, we show that for graphs in normal form with dihedral color classes of bounded size, the canonization problem can be solved in CPT. We also show the same statement for general ternary structures in normal form if the dihedral groups are defined over odd domains.

BibTeX - Entry

@InProceedings{lichter_et_al:LIPIcs:2021:13465,
  author =	{Moritz Lichter and Pascal Schweitzer},
  title =	{{Canonization for Bounded and Dihedral Color Classes in Choiceless Polynomial Time}},
  booktitle =	{29th EACSL Annual Conference on Computer Science Logic (CSL 2021)},
  pages =	{31:1--31:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-175-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{183},
  editor =	{Christel Baier and Jean Goubault-Larrecq},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13465},
  URN =		{urn:nbn:de:0030-drops-134650},
  doi =		{10.4230/LIPIcs.CSL.2021.31},
  annote =	{Keywords: Choiceless polynomial time, canonization, relational structures, bounded color class size, dihedral groups}
}

Keywords: Choiceless polynomial time, canonization, relational structures, bounded color class size, dihedral groups
Collection: 29th EACSL Annual Conference on Computer Science Logic (CSL 2021)
Issue Date: 2021
Date of publication: 13.01.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI