TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 23161

Pushing the Limits of Computational Combinatorial Constructions

( Apr 16 – Apr 21, 2023 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/23161

Organizers

Contact

Shared Documents


Schedule

Summary

Objectives of the seminar

In this Dagstuhl Seminar, the focus was on computational methods for challenging problems in combinatorial construction. This seminar brought together researchers with different expertise: those with a deep understanding of combinatorial objects and experts in algorithm design and high-performance computing. Participants identified important problems for codes, graphs, and designs; and discussed state-of-the-art methods for challenging problems in constructing combinatorial objects. Additionally, the seminar brought together experts on combinatorial algorithms and representatives from different scientific communities developing practical techniques for attacking general hard problems, for example, in the framework of SAT solving, integer linear programming, and optimization.

General overview of the research topic

In discrete mathematics, construction and classification of structures are core problems. Computational methods have been essential in settling important mathematical questions, such as the proof of the four color theorem (Apel and Haken, 1976) and the nonexistence of projective planes of order 10 (Lam et al., 1989). Isomorph-free exhaustive searches are quite challenging with the number of nonequivalent objects often growing exponentially with the input size. For example, the classification of Steiner triple systems of order 19 (Kaski and Östergard, 2004) involved producing a list of more than 11 billion such objects. Vast exhaustive searches are also used to establish negative results, as in the non-existence of 16-clue Sudoku puzzles (McGuire et al., 2012), celebrated by the media due to its connection with the famous puzzle. Many of the central problems, even subproblems, are (NP-)hard, but with improved algorithms and general approaches, it is still possible to handle instances with not too small parameters.

Structure of the seminar

  • Curtis Bright (University of Windsor, CA): SAT + Isomorph-free Generation ...and the Quest for the Minimum Kochen–Specker System
  • Daniel Heinlein (Aalto University, FI): Enumerating Steiner Triple Systems: Counting STS(21)s
  • Vedran Krcadinac (University of Zagreb, HR): On higher-dimensional designs
  • Pascal Schweitzer (TU Darmstadt, DE): Automorphisms, Isomorphisms, and Canonization: recent developments

In the first two days of the seminar six leading experts gave 30 minute tutorials and provided input on the current limits of the area:

  • Brendan McKay (Australian National University - Acton, AU): SURGE : A fact open-source chemical graph generator
  • Gordon Royle (The University of Western Australia - Crawley, AU): Three stories about computational combinatorics
  • Manfred Scheucher (TU Berlin, DE): Using SAT Solvers in Combinatorics and Geometry
  • Brett Stevens (Carleton University - Ottawa, CA): Thoughts on Computational Design Theory
  • Leo Storme (Ghent University, BE): Computational methods in finite geometry
  • Ian M. Wanless (Monash University - Clayton, AU): Open problems on orthogonal(ish) arrays

In the remaining time participants were partitioned into five working groups, brainstorming and exchanging ideas:

  • Improving reliability and usability of computational projects
  • SAT working group
  • Isomorphism Solvers
  • Design theory working group
  • Tactical decompositions working group
Copyright Lucia Moura, Anamari Nakic, Patric Östergård, and Alfred Wassermann

Motivation

In discrete mathematics, construction and classification of structures are core problems. Computational methods have been essential in settling important mathematical questions, such as the proof of the four color theorem (Apel and Haken, 1976) and the nonexistence of projective planes of order 10 (Lam et al., 1989). Isomorph-free exhaustive searches are quite challenging with the number of nonequivalent objects often growing exponentially with the input size. For example, the classification of Steiner triple systems of order 19 (Kaski and Östergård, 2004) involved producing a list of more than 11 billion such objects. Vast exhaustive searches are also used to establish negative results, as in the non-existence of 16-clue Sudoku puzzles (McGuire et al., 2012), celebrated by the media due to its connection with the famous puzzle. Many of the central problems, even subproblems, are (NP-)hard, but with improved algorithms and general approaches, it is still possible to handle instances with not too small parameters.

In this Dagstuhl seminar, we will focus on computational methods for challenging problems in combinatorial construction . This includes algorithms for construction of combinatorial objects with prescribed symmetry, for isomorph-free exhaustive generation, and for combinatorial search. Examples of specific algorithmic techniques are tactical decomposition, the Kramer-Mesner method, algebraic methods, graph isomorphism software, isomorph-free generation, clique-finding methods, heuristic search, and combinatorial optimization. There will be an emphasis on problems involving graphs, designs and codes , also including topics in related fields such as finite geometry, graph decomposition, Hadamard matrices, Latin squares, and q-analogs of designs and codes. Examples of specific cases to consider are the existence problems for q-analogs of the Fano plane and projective planes with an order that is not a prime power.

This seminar aims to bring together researchers with different expertise: those with a deep understanding of combinatorial objects and experts in algorithms design and high-performance computing. Participants will discuss and work to improve on state-of-the-art methods for challenging problems in constructing combinatorial objects and highlight important open problems to attack. Additionally, the seminar aims to bring together experts on combinatorial algorithms and representatives from different scientific communities developing practical techniques for attacking general hard problems, for example, in the framework of satisfiability, integer linear programming, and optimization. The contribution of scholars working in high-performance computing and experts on relevant computer architectures (such as GPUs) will also be valuable. The goal of this seminar is to provide a creative impulse towards new research in the topic. All participants will get the chance to report on their experience, either in plenary short talks or in working group panels. Dealing with finite discrete problems, which can always be solved in finite time, success is about algorithms and computational resources. This venue will give opportunity to the researchers also to discuss the challenges found when they did not succeed, and it could be catalytic for advances in the field. A short-term goal of the seminar is to exchange information and initiate new collaborative research on the themes of the seminar. We hope the workshop will generate new ideas, new problems, new collaborations and new breakthroughs, with significant impact in the upcoming years.

Copyright Lucia Moura, Anamari Nakic, Patric Östergård, and Alfred Wassermann

Participants

Classification
  • Data Structures and Algorithms
  • Discrete Mathematics
  • Mathematical Software

Keywords
  • combinatorial algorithms
  • subspace designs
  • finite geometries
  • automorphism groups