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.

Creative Commons BY 4.0

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

• Thais Bardini Idalino (Federal University of Santa Catarina, BR) [dblp]
• Curtis Bright (University of Windsor, CA) [dblp]
• Jan De Beule (Free University of Brussels, BE) [dblp]
• Alena Ernst (Universität Paderborn, DE)
• Tuvi Etzion (Technion - Haifa, IL) [dblp]
• Marcus Greferath (University College Dublin, IE) [dblp]
• Daniel Heinlein (Aalto University, FI) [dblp]
• Delaram Kahrobaei (City University of New York, US) [dblp]
• Petteri Kaski (Aalto University, FI) [dblp]
• Sandra Kiefer (University of Oxford, GB) [dblp]
• Michael Kiermaier (Universität Bayreuth, DE) [dblp]
• Ilias S. Kotsireas (Wilfrid Laurier University - Waterloo, CA) [dblp]
• Vedran Krcadinac (University of Zagreb, HR) [dblp]
• Aleksandr Krotov (Innopolis University, RU)
• Denis Krotov (Sobolev Institute of Mathematics - Novosibirsk, RU) [dblp]
• Sascha Kurz (Universität Bayreuth, DE) [dblp]
• Pekka Lampio (Aalto University, FI) [dblp]
• Brendan McKay (Australian National University - Acton, AU) [dblp]
• Lucia Moura (University of Ottawa, CA) [dblp]
• Gábor P. Nagy (Budapest University of Technology & Economics, HU) [dblp]
• Anamari Nakic (University of Zagreb, HR) [dblp]
• Eamonn O'Brien (University of Auckland, NZ) [dblp]
• Patric Östergård (Aalto University, FI) [dblp]
• Mario Osvin Pavcevic (University of Zagreb, HR) [dblp]
• David Pike (Memorial University of Newfoundland - St. John's, CA) [dblp]
• Adolfo Piperno (Sapienza University of Rome, IT) [dblp]
• Gordon Royle (The University of Western Australia - Crawley, AU) [dblp]
• Manfred Scheucher (TU Berlin, DE) [dblp]
• Pascal Schweitzer (TU Darmstadt, DE) [dblp]
• Leonard H. Soicher (Queen Mary University of London, GB) [dblp]
• Brett Stevens (Carleton University - Ottawa, CA) [dblp]
• Leo Storme (Ghent University, BE) [dblp]
• Ana Sumberac (University of Rijeka, HR)
• Edwin van Dam (Tilburg University, NL) [dblp]
• Ian M. Wanless (Monash University - Clayton, AU) [dblp]
• Alfred Wassermann (Universität Bayreuth, DE) [dblp]
• Charlene Weiß (Universität Paderborn, DE)