Document Open Access Logo

Canonization for Bounded and Dihedral Color Classes in Choiceless Polynomial Time

Authors Moritz Lichter, Pascal Schweitzer

PDF
Thumbnail PDF

File

LIPIcs.CSL.2021.31.pdf
  • Filesize: 0.58 MB
  • 18 pages

Document Identifiers

Author Details

Moritz Lichter
  • TU Kaiserslautern, Germany
Pascal Schweitzer
  • TU Kaiserslautern, Germany

Funding

Received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (EngageS: agreement No. 820148).

Cite AsGet BibTex

Moritz Lichter and Pascal Schweitzer. Canonization for Bounded and Dihedral Color Classes in Choiceless Polynomial Time. In 29th EACSL Annual Conference on Computer Science Logic (CSL 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 183, pp. 31:1-31:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.CSL.2021.31

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Finite Model Theory
  • Theory of computation → Complexity theory and logic
Keywords
  • Choiceless polynomial time
  • canonization
  • relational structures
  • bounded color class size
  • dihedral groups

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. László Babai. Monte carlo algorithms in graph isomorphism testing. Technical Report D.M.S. No. 79-10, Université de Montréal, 1979. Google Scholar
  2. László Babai and Eugene M. Luks. Canonical labeling of graphs. In David S. Johnson, Ronald Fagin, Michael L. Fredman, David Harel, Richard M. Karp, Nancy A. Lynch, Christos H. Papadimitriou, Ronald L. Rivest, Walter L. Ruzzo, and Joel I. Seiferas, editors, Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA, pages 171-183. ACM, 1983. URL: https://doi.org/10.1145/800061.808746.
  3. Andreas Blass, Yuri Gurevich, and Saharon Shelah. Choiceless polynomial time. Ann. Pure Appl. Log., 100(1-3):141-187, 1999. URL: https://doi.org/10.1016/S0168-0072(99)00005-6.
  4. Jin-yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-410, 1992. URL: https://doi.org/10.1007/BF01305232.
  5. Ashok K. Chandra and David Harel. Structure and complexity of relational queries. J. Comput. Syst. Sci., 25(1):99-128, 1982. URL: https://doi.org/10.1016/0022-0000(82)90012-5.
  6. Anuj Dawar, David Richerby, and Benjamin Rossman. Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs. Ann. Pure Appl. Logic, 152(1-3):31-50, 2008. URL: https://doi.org/10.1016/j.apal.2007.11.011.
  7. Ronald Fagin. Generalized first-order spectra and polynomial-time recognizable sets. In Complexity of computation (Proc. SIAM-AMS Sympos. Appl. Math., New York, 1973), pages 43-73. SIAM-AMS Proc., Vol. VII, 1974. Google Scholar
  8. Merrick L. Furst, John E. Hopcroft, and Eugene M. Luks. Polynomial-time algorithms for permutation groups. In 21st Annual Symposium on Foundations of Computer Science, Syracuse, New York, USA, 13-15 October 1980, pages 36-41. IEEE Computer Society, 1980. URL: https://doi.org/10.1109/SFCS.1980.34.
  9. Erich Grädel and Martin Grohe. Is polynomial time choiceless? In Lev D. Beklemishev, Andreas Blass, Nachum Dershowitz, Bernd Finkbeiner, and Wolfram Schulte, editors, Fields of Logic and Computation II - Essays Dedicated to Yuri Gurevich on the Occasion of His 75th Birthday, volume 9300 of Lecture Notes in Computer Science, pages 193-209. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-23534-9_11.
  10. Martin Grohe. Isomorphism testing for embeddable graphs through definability. In F. Frances Yao and Eugene M. Luks, editors, Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 63-72. ACM, 2000. URL: https://doi.org/10.1145/335305.335313.
  11. Martin Grohe. The quest for a logic capturing PTIME. In Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science, LICS 2008, 24-27 June 2008, Pittsburgh, PA, USA, pages 267-271. IEEE Computer Society, 2008. URL: https://doi.org/10.1109/LICS.2008.11.
  12. Martin Grohe. Fixed-point definability and polynomial time on graphs with excluded minors. In Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, LICS 2010, 11-14 July 2010, Edinburgh, United Kingdom, pages 179-188. IEEE Computer Society, 2010. URL: https://doi.org/10.1109/LICS.2010.22.
  13. Martin Grohe. Descriptive Complexity, Canonization, and Definable Graph Structure Theory. Cambridge University Press, 2017. Google Scholar
  14. Martin Grohe and Julian Mariño. Definability and descriptive complexity on databases of bounded tree-width. In Catriel Beeri and Peter Buneman, editors, Database Theory - ICDT '99, 7th International Conference, Jerusalem, Israel, January 10-12, 1999, Proceedings, volume 1540 of Lecture Notes in Computer Science, pages 70-82. Springer, 1999. URL: https://doi.org/10.1007/3-540-49257-7_6.
  15. Martin Grohe and Daniel Neuen. Canonisation and definability for graphs of bounded rank width. In 34th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2019, Vancouver, BC, Canada, June 24-27, 2019, pages 1-13. IEEE, 2019. URL: https://doi.org/10.1109/LICS.2019.8785682.
  16. Martin Grohe, Pascal Schweitzer, and Daniel Wiebking. Deep Weisfeiler Leman, 2020. URL: http://arxiv.org/abs/arXiv:2003.10935.
  17. Yuri Gurevich. Logic and the challenge of computer science. In Egon Boerger, editor, Current Trends in Theoretical Computer Science, pages 1-57. Computer Science Press, 1988. Google Scholar
  18. Neil Immerman. Languages that capture complexity classes. SIAM J. Comput., 16(4):760-778, 1987. URL: https://doi.org/10.1137/0216051.
  19. Sandra Kiefer and Daniel Neuen. The power of the Weisfeiler-Leman algorithm to decompose graphs. In MFCS, volume 138 of LIPIcs, pages 45:1-45:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  20. Bastian Laubner. Capturing polynomial time on interval graphs. In Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, LICS 2010, 11-14 July 2010, Edinburgh, United Kingdom, pages 199-208. IEEE Computer Society, 2010. URL: https://doi.org/10.1109/LICS.2010.42.
  21. Moritz Lichter and Pascal Schweitzer. Canonization for bounded and dihedral color classes in choiceless polynomial time, 2020. URL: http://arxiv.org/abs/arXiv:2010.12182.
  22. Eugene M. Luks. Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comput. Syst. Sci., 25(1):42-65, 1982. Google Scholar
  23. Daniel Neuen and Pascal Schweitzer. Subgroups of 3-factor direct products. Tatra Mt. Math. Publ., 73:19-38, 2019. Google Scholar
  24. Martin Otto. Bounded variable logics and counting - a study in finite models, volume 9 of Lecture Notes in Logic. Springer, 1997. Google Scholar
  25. Wied Pakusa. Linear Equation Systems and the Search for a Logical Characterisation of Polynomial Time. PhD thesis, RWTH Aachen, 2015. Google Scholar
  26. Wied Pakusa, Svenja Schalthöfer, and Erkal Selman. Definability of Cai-Fürer-Immerman problems in choiceless polynomial time. In Jean-Marc Talbot and Laurent Regnier, editors, 25th EACSL Annual Conference on Computer Science Logic, CSL 2016, August 29 - September 1, 2016, Marseille, France, volume 62 of LIPIcs, pages 19:1-19:17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.CSL.2016.19.
  27. Benjamin Rossman. Choiceless computation and symmetry. In Andreas Blass, Nachum Dershowitz, and Wolfgang Reisig, editors, Fields of Logic and Computation, Essays Dedicated to Yuri Gurevich on the Occasion of His 70th Birthday, volume 6300 of Lecture Notes in Computer Science, pages 565-580. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-15025-8_28.
  28. Pascal Schweitzer and Daniel Wiebking. A unifying method for the design of algorithms canonizing combinatorial objects. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 1247-1258. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316338.
  29. Faried Abu Zaid, Erich Grädel, Martin Grohe, and Wied Pakusa. Choiceless polynomial time on structures with small abelian colour classes. In Erzsébet Csuhaj-Varjú, Martin Dietzfelbinger, and Zoltán Ésik, editors, Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part I, volume 8634 of Lecture Notes in Computer Science, pages 50-62. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-44522-8_5.
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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact