Search Results

Documents authored by Grohe, Martin

Document
Complete Volume
DOI: 10.4230/LIPIcs.ICALP.2024
LIPIcs, Volume 297, ICALP 2024, Complete Volume

Authors: Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
LIPIcs, Volume 297, ICALP 2024, Complete Volume
Cite as

51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 1-2938, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Proceedings{bringmann_et_al:LIPIcs.ICALP.2024,
  title =	{{LIPIcs, Volume 297, ICALP 2024, Complete Volume}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{1--2938},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024},
  URN =		{urn:nbn:de:0030-drops-201424},
  doi =		{10.4230/LIPIcs.ICALP.2024},
  annote =	{Keywords: LIPIcs, Volume 297, ICALP 2024, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ICALP.2024.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 0:i-0:xl, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.ICALP.2024.0,
  author =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{0:i--0:xl},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.0},
  URN =		{urn:nbn:de:0030-drops-201437},
  doi =		{10.4230/LIPIcs.ICALP.2024.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.78
Isomorphism for Tournaments of Small Twin Width

Authors: Martin Grohe and Daniel Neuen

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We prove that isomorphism of tournaments of twin width at most k can be decided in time k^O(log k) n^O(1). This implies that the isomorphism problem for classes of tournaments of bounded or moderately growing twin width is in polynomial time. By comparison, there are classes of undirected graphs of bounded twin width that are isomorphism complete, that is, the isomorphism problem for the classes is as hard as the general graph isomorphism problem. Twin width is a graph parameter that has been introduced only recently (Bonnet et al., FOCS 2020), but has received a lot of attention in structural graph theory since then. On directed graphs, it is functionally smaller than clique width. We prove that on tournaments (but not on general directed graphs) it is also functionally smaller than directed tree width (and thus, the same also holds for cut width and directed path width). Hence, our result implies that tournament isomorphism testing is also fixed-parameter tractable when parameterized by any of these parameters. Our isomorphism algorithm heavily employs group-theoretic techniques. This seems to be necessary: as a second main result, we show that the combinatorial Weisfeiler-Leman algorithm does not decide isomorphism of tournaments of twin width at most 35 if its dimension is o(n). (Throughout this abstract, n is the order of the input graphs.)
Cite as

Martin Grohe and Daniel Neuen. Isomorphism for Tournaments of Small Twin Width. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 78:1-78:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{grohe_et_al:LIPIcs.ICALP.2024.78,
  author =	{Grohe, Martin and Neuen, Daniel},
  title =	{{Isomorphism for Tournaments of Small Twin Width}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{78:1--78:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.78},
  URN =		{urn:nbn:de:0030-drops-202216},
  doi =		{10.4230/LIPIcs.ICALP.2024.78},
  annote =	{Keywords: tournament isomorphism, twin width, fixed-parameter tractability, Weisfeiler-Leman algorithm}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2024.14
The Importance of Parameters in Database Queries

Authors: Martin Grohe, Benny Kimelfeld, Peter Lindner, and Christoph Standke

Published in: LIPIcs, Volume 290, 27th International Conference on Database Theory (ICDT 2024)

Abstract
We propose and study a framework for quantifying the importance of the choices of parameter values to the result of a query over a database. These parameters occur as constants in logical queries, such as conjunctive queries. In our framework, the importance of a parameter is its SHAP score. This score is a popular instantiation of the game-theoretic Shapley value to measuring the importance of feature values in machine learning models. We make the case for the rationale of using this score by explaining the intuition behind SHAP, and by showing that we arrive at this score in two different, apparently opposing, approaches to quantifying the contribution of a parameter. The application of the SHAP score requires two components in addition to the query and the database: (a) a probability distribution over the combinations of parameter values, and (b) a utility function that measures the similarity between the result for the original parameters and the result for hypothetical parameters. The main question addressed in the paper is the complexity of calculating the SHAP score for different distributions and similarity measures. We first address the case of probabilistically independent parameters. The problem is hard if we consider a fragment of queries that is hard to evaluate (as one would expect), and even for the fragment of acyclic conjunctive queries. In some cases, though, one can efficiently list all relevant parameter combinations, and then the SHAP score can be computed in polynomial time under reasonable general conditions. Also tractable is the case of full acyclic conjunctive queries for certain (natural) similarity functions. We extend our results to conjunctive queries with inequalities between variables and parameters. Finally, we discuss a simple approximation technique for the case of correlated parameters.
Cite as

Martin Grohe, Benny Kimelfeld, Peter Lindner, and Christoph Standke. The Importance of Parameters in Database Queries. In 27th International Conference on Database Theory (ICDT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 290, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{grohe_et_al:LIPIcs.ICDT.2024.14,
  author =	{Grohe, Martin and Kimelfeld, Benny and Lindner, Peter and Standke, Christoph},
  title =	{{The Importance of Parameters in Database Queries}},
  booktitle =	{27th International Conference on Database Theory (ICDT 2024)},
  pages =	{14:1--14:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-312-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{290},
  editor =	{Cormode, Graham and Shekelyan, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.14},
  URN =		{urn:nbn:de:0030-drops-197966},
  doi =		{10.4230/LIPIcs.ICDT.2024.14},
  annote =	{Keywords: SHAP score, query parameters, Shapley value}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2023.20
Probabilistic Query Evaluation with Bag Semantics

Authors: Martin Grohe, Peter Lindner, and Christoph Standke

Published in: LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023)

Abstract
We initiate the study of probabilistic query evaluation under bag semantics where tuples are allowed to be present with duplicates. We focus on self-join free conjunctive queries, and probabilistic databases where occurrences of different facts are independent, which is the natural generalization of tuple-independent probabilistic databases to the bag semantics setting. For set semantics, the data complexity of this problem is well understood, even for the more general class of unions of conjunctive queries: it is either in polynomial time, or #P-hard, depending on the query (Dalvi & Suciu, JACM 2012). Due to potentially unbounded multiplicities, the bag probabilistic databases we discuss are no longer finite objects, which requires a treatment of representation mechanisms. Moreover, the answer to a Boolean query is a probability distribution over non-negative integers, rather than a probability distribution over {true, false}. Therefore, we discuss two flavors of probabilistic query evaluation: computing expectations of answer tuple multiplicities, and computing the probability that a tuple is contained in the answer at most k times for some parameter k. Subject to mild technical assumptions on the representation systems, it turns out that expectations are easy to compute, even for unions of conjunctive queries. For query answer probabilities, we obtain a dichotomy between solvability in polynomial time and #P-hardness for self-join free conjunctive queries.
Cite as

Martin Grohe, Peter Lindner, and Christoph Standke. Probabilistic Query Evaluation with Bag Semantics. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{grohe_et_al:LIPIcs.ICDT.2023.20,
  author =	{Grohe, Martin and Lindner, Peter and Standke, Christoph},
  title =	{{Probabilistic Query Evaluation with Bag Semantics}},
  booktitle =	{26th International Conference on Database Theory (ICDT 2023)},
  pages =	{20:1--20:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-270-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{255},
  editor =	{Geerts, Floris and Vandevoort, Brecht},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.20},
  URN =		{urn:nbn:de:0030-drops-177636},
  doi =		{10.4230/LIPIcs.ICDT.2023.20},
  annote =	{Keywords: Probabilistic Query Evaluation, Probabilistic Databases, Bag Semantics}
}
Document
DOI: 10.4230/DagRep.12.5.112
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 22201)

Authors: Martin Grohe, Venkatesan Guruswami, Dániel Marx, and Stanislav Živný

Published in: Dagstuhl Reports, Volume 12, Issue 5 (2022)

Abstract
Constraint satisfaction has always played a central role in computational complexity theory; appropriate versions of CSPs are classical complete problems for most standard complexity classes. CSPs constitute a very rich and yet sufficiently manageable class of problems to give a good perspective on general computational phenomena. For instance, they help to understand which mathematical properties make a computational problem tractable (in a wide sense, e.g., polynomial-time solvable, non-trivially approximable, fixed-parameter tractable, or definable in a weak logic). In the last 15 years, research activity in this area has significantly intensified and hugely impressive progress was made. The Dagstuhl Seminar 22201 "The Constraint Satisfaction Problem: Complexity and Approximability" was aimed at bringing together researchers using all the different techniques in the study of the CSP so that they can share their insights obtained during the past four years. This report documents the material presented during the course of the seminar.
Cite as

Martin Grohe, Venkatesan Guruswami, Dániel Marx, and Stanislav Živný. The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 22201). In Dagstuhl Reports, Volume 12, Issue 5, pp. 112-130, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{grohe_et_al:DagRep.12.5.112,
  author =	{Grohe, Martin and Guruswami, Venkatesan and Marx, D\'{a}niel and \v{Z}ivn\'{y}, Stanislav},
  title =	{{The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 22201)}},
  pages =	{112--130},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{12},
  number =	{5},
  editor =	{Grohe, Martin and Guruswami, Venkatesan and Marx, D\'{a}niel and \v{Z}ivn\'{y}, Stanislav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.5.112},
  URN =		{urn:nbn:de:0030-drops-174453},
  doi =		{10.4230/DagRep.12.5.112},
  annote =	{Keywords: Constraint satisfaction problem (CSP); Computational complexity; Hardness of approximation; Universal algebra; Semidefinite programming}
}
Document
DOI: 10.4230/DagRep.12.3.141
Graph Embeddings: Theory meets Practice (Dagstuhl Seminar 22132)

Authors: Martin Grohe, Stephan Günnemann, Stefanie Jegelka, and Christopher Morris

Published in: Dagstuhl Reports, Volume 12, Issue 3 (2022)

Abstract
Vectorial representations of graphs and relational structures, so-called graph embeddings, make it possible to apply standard tools from data mining, machine learning, and statistics to the graph domain. In particular, graph embeddings aim to capture important information about, both, the graph structure and available side information as a vector, to enable downstream tasks such as classification, regression, or clustering. Starting from the 1960s in chemoinformatics, research in various communities has resulted in a plethora of approaches, often with recurring ideas. However, most of the field advancements are driven by intuition and empiricism, often tailored to a specific application domain. Until recently, the area has received little stimulus from theoretical computer science, graph theory, and learning theory. The Dagstuhl Seminar 22132 "Graph Embeddings: Theory meets Practice", was aimed to gather leading applied and theoretical researchers in graph embeddings and adjacent areas, such as graph isomorphism, bio- and chemoinformatics, and graph theory, to stimulate an increased exchange of ideas between these communities.
Cite as

Martin Grohe, Stephan Günnemann, Stefanie Jegelka, and Christopher Morris. Graph Embeddings: Theory meets Practice (Dagstuhl Seminar 22132). In Dagstuhl Reports, Volume 12, Issue 3, pp. 141-155, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{grohe_et_al:DagRep.12.3.141,
  author =	{Grohe, Martin and G\"{u}nnemann, Stephan and Jegelka, Stefanie and Morris, Christopher},
  title =	{{Graph Embeddings: Theory meets Practice (Dagstuhl Seminar 22132)}},
  pages =	{141--155},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{12},
  number =	{3},
  editor =	{Grohe, Martin and G\"{u}nnemann, Stephan and Jegelka, Stefanie and Morris, Christopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.3.141},
  URN =		{urn:nbn:de:0030-drops-172727},
  doi =		{10.4230/DagRep.12.3.141},
  annote =	{Keywords: Machine Learning For Graphs, GNNs, Graph Embedding}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.52
Graph Similarity Based on Matrix Norms

Authors: Timo Gervens and Martin Grohe

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
Quantifying the similarity between two graphs is a fundamental algorithmic problem at the heart of many data analysis tasks for graph-based data. In this paper, we study the computational complexity of a family of similarity measures based on quantifying the mismatch between the two graphs, that is, the "symmetric difference" of the graphs under an optimal alignment of the vertices. An important example is similarity based on graph edit distance. While edit distance calculates the "global" mismatch, that is, the number of edges in the symmetric difference, our main focus is on "local" measures calculating the maximum mismatch per vertex. Mathematically, our similarity measures are best expressed in terms of the adjacency matrices: the mismatch between graphs is expressed as the difference of their adjacency matrices (under an optimal alignment), and we measure it by applying some matrix norm. Roughly speaking, global measures like graph edit distance correspond to entrywise matrix norms like the Frobenius norm and local measures correspond to operator norms like the spectral norm. We prove a number of strong NP-hardness and inapproximability results even for very restricted graph classes such as bounded-degree trees.
Cite as

Timo Gervens and Martin Grohe. Graph Similarity Based on Matrix Norms. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gervens_et_al:LIPIcs.MFCS.2022.52,
  author =	{Gervens, Timo and Grohe, Martin},
  title =	{{Graph Similarity Based on Matrix Norms}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{52:1--52:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.52},
  URN =		{urn:nbn:de:0030-drops-168509},
  doi =		{10.4230/LIPIcs.MFCS.2022.52},
  annote =	{Keywords: graph similarity, approximate graph isomorphism, graph matching}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.70
Homomorphism Tensors and Linear Equations

Authors: Martin Grohe, Gaurav Rattan, and Tim Seppelt

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

Abstract
Lovász (1967) showed that two graphs G and H are isomorphic if and only if they are homomorphism indistinguishable over the class of all graphs, i.e. for every graph F, the number of homomorphisms from F to G equals the number of homomorphisms from F to H. Recently, homomorphism indistinguishability over restricted classes of graphs such as bounded treewidth, bounded treedepth and planar graphs, has emerged as a surprisingly powerful framework for capturing diverse equivalence relations on graphs arising from logical equivalence and algebraic equation systems. In this paper, we provide a unified algebraic framework for such results by examining the linear-algebraic and representation-theoretic structure of tensors counting homomorphisms from labelled graphs. The existence of certain linear transformations between such homomorphism tensor subspaces can be interpreted both as homomorphism indistinguishability over a graph class and as feasibility of an equational system. Following this framework, we obtain characterisations of homomorphism indistinguishability over several natural graph classes, namely trees of bounded degree, graphs of bounded pathwidth (answering a question of Dell et al. (2018)), and graphs of bounded treedepth.
Cite as

Martin Grohe, Gaurav Rattan, and Tim Seppelt. Homomorphism Tensors and Linear Equations. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 70:1-70:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{grohe_et_al:LIPIcs.ICALP.2022.70,
  author =	{Grohe, Martin and Rattan, Gaurav and Seppelt, Tim},
  title =	{{Homomorphism Tensors and Linear Equations}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{70:1--70:20},
  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.70},
  URN =		{urn:nbn:de:0030-drops-164113},
  doi =		{10.4230/LIPIcs.ICALP.2022.70},
  annote =	{Keywords: homomorphisms, labelled graphs, treewidth, pathwidth, treedepth, linear equations, Sherali-Adams relaxation, Wiegmann-Specht Theorem, Weisfeiler-Leman}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.MFCS.2021.2
A Deep Dive into the Weisfeiler-Leman Algorithm (Invited Talk)

Authors: Martin Grohe

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
The Weisfeiler-Leman algorithm is a well-known combinatorial graph isomorphism test going back to work of Weisfeiler and Leman in the late 1960s. The algorithm has a surprising number of seemingly unrelated characterisations in terms of logic, algebra, linear and semi-definite programming, and graph homomorphisms. Due to its simplicity and efficiency, it is an important subroutine of all modern graph isomorphism tools. In recent years, further applications in linear optimisation, probabilistic inference, and machine learning have surfaced. In my talk, I will introduce the Weisfeiler-Leman algorithm and some extensions. I will discuss its expressiveness and the various characterisations, and I will speak about its applications.
Cite as

Martin Grohe. A Deep Dive into the Weisfeiler-Leman Algorithm (Invited Talk). In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{grohe:LIPIcs.MFCS.2021.2,
  author =	{Grohe, Martin},
  title =	{{A Deep Dive into the Weisfeiler-Leman Algorithm}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.2},
  URN =		{urn:nbn:de:0030-drops-144429},
  doi =		{10.4230/LIPIcs.MFCS.2021.2},
  annote =	{Keywords: Weisfeiler-Leman algorithm, graph isomorphism, counting homomorphisms, finite variable logics}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2021.134
Logarithmic Weisfeiler-Leman Identifies All Planar Graphs

Authors: Martin Grohe and Sandra Kiefer

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
The Weisfeiler-Leman (WL) algorithm is a well-known combinatorial procedure for detecting symmetries in graphs and it is widely used in graph-isomorphism tests. It proceeds by iteratively refining a colouring of vertex tuples. The number of iterations needed to obtain the final output is crucial for the parallelisability of the algorithm. We show that there is a constant k such that every planar graph can be identified (that is, distinguished from every non-isomorphic graph) by the k-dimensional WL algorithm within a logarithmic number of iterations. This generalises a result due to Verbitsky (STACS 2007), who proved the same for 3-connected planar graphs. The number of iterations needed by the k-dimensional WL algorithm to identify a graph corresponds to the quantifier depth of a sentence that defines the graph in the (k+1)-variable fragment C^{k+1} of first-order logic with counting quantifiers. Thus, our result implies that every planar graph is definable with a C^{k+1}-sentence of logarithmic quantifier depth.
Cite as

Martin Grohe and Sandra Kiefer. Logarithmic Weisfeiler-Leman Identifies All Planar Graphs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 134:1-134:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{grohe_et_al:LIPIcs.ICALP.2021.134,
  author =	{Grohe, Martin and Kiefer, Sandra},
  title =	{{Logarithmic Weisfeiler-Leman Identifies All Planar Graphs}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{134:1--134:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.134},
  URN =		{urn:nbn:de:0030-drops-142035},
  doi =		{10.4230/LIPIcs.ICALP.2021.134},
  annote =	{Keywords: Weisfeiler-Leman algorithm, finite-variable logic, isomorphism testing, planar graphs, quantifier depth, iteration number}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2021.16
Database Repairing with Soft Functional Dependencies

Authors: Nofar Carmeli, Martin Grohe, Benny Kimelfeld, Ester Livshits, and Muhammad Tibi

Published in: LIPIcs, Volume 186, 24th International Conference on Database Theory (ICDT 2021)

Abstract
A common interpretation of soft constraints penalizes the database for every violation of every constraint, where the penalty is the cost (weight) of the constraint. A computational challenge is that of finding an optimal subset: a collection of database tuples that minimizes the total penalty when each tuple has a cost of being excluded. When the constraints are strict (i.e., have an infinite cost), this subset is a "cardinality repair" of an inconsistent database; in soft interpretations, this subset corresponds to a "most probable world" of a probabilistic database, a "most likely intention" of a probabilistic unclean database, and so on. Within the class of functional dependencies, the complexity of finding a cardinality repair is thoroughly understood. Yet, very little is known about the complexity of finding an optimal subset for the more general soft semantics. This paper makes a significant progress in this direction. In addition to general insights about the hardness and approximability of the problem, we present algorithms for two special cases: a single functional dependency, and a bipartite matching. The latter is the problem of finding an optimal "almost matching" of a bipartite graph where a penalty is paid for every lost edge and every violation of monogamy.
Cite as

Nofar Carmeli, Martin Grohe, Benny Kimelfeld, Ester Livshits, and Muhammad Tibi. Database Repairing with Soft Functional Dependencies. In 24th International Conference on Database Theory (ICDT 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 186, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{carmeli_et_al:LIPIcs.ICDT.2021.16,
  author =	{Carmeli, Nofar and Grohe, Martin and Kimelfeld, Benny and Livshits, Ester and Tibi, Muhammad},
  title =	{{Database Repairing with Soft Functional Dependencies}},
  booktitle =	{24th International Conference on Database Theory (ICDT 2021)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-179-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{186},
  editor =	{Yi, Ke and Wei, Zhewei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2021.16},
  URN =		{urn:nbn:de:0030-drops-137245},
  doi =		{10.4230/LIPIcs.ICDT.2021.16},
  annote =	{Keywords: Database inconsistency, database repairs, integrity constraints, soft constraints, functional dependencies}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2020.16
Infinite Probabilistic Databases

Authors: Martin Grohe and Peter Lindner

Published in: LIPIcs, Volume 155, 23rd International Conference on Database Theory (ICDT 2020)

Abstract
Probabilistic databases (PDBs) are used to model uncertainty in data in a quantitative way. In the standard formal framework, PDBs are finite probability spaces over relational database instances. It has been argued convincingly that this is not compatible with an open-world semantics (Ceylan et al., KR 2016) and with application scenarios that are modeled by continuous probability distributions (Dalvi et al., CACM 2009). We recently introduced a model of PDBs as infinite probability spaces that addresses these issues (Grohe and Lindner, PODS 2019). While that work was mainly concerned with countably infinite probability spaces, our focus here is on uncountable spaces. Such an extension is necessary to model typical continuous probability distributions that appear in many applications. However, an extension beyond countable probability spaces raises nontrivial foundational issues concerned with the measurability of events and queries and ultimately with the question whether queries have a well-defined semantics. It turns out that so-called finite point processes are the appropriate model from probability theory for dealing with probabilistic databases. This model allows us to construct suitable (uncountable) probability spaces of database instances in a systematic way. Our main technical results are measurability statements for relational algebra queries as well as aggregate queries and Datalog queries.
Cite as

Martin Grohe and Peter Lindner. Infinite Probabilistic Databases. In 23rd International Conference on Database Theory (ICDT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 155, pp. 16:1-16:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{grohe_et_al:LIPIcs.ICDT.2020.16,
  author =	{Grohe, Martin and Lindner, Peter},
  title =	{{Infinite Probabilistic Databases}},
  booktitle =	{23rd International Conference on Database Theory (ICDT 2020)},
  pages =	{16:1--16:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-139-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{155},
  editor =	{Lutz, Carsten and Jung, Jean Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2020.16},
  URN =		{urn:nbn:de:0030-drops-119400},
  doi =		{10.4230/LIPIcs.ICDT.2020.16},
  annote =	{Keywords: Probabilistic Databases, Possible Worlds Semantics, Query Measurability, Relational Algebra, Aggregate Queries}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2020.2
Weisfeiler and Leman’s Unlikely Journey from Graph Isomorphism to Neural Networks (Invited Talk)

Authors: Martin Grohe

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
The Weisfeiler-Leman algorithm is a well-known combinatorial graph isomorphism test going back to work of Weisfeiler and Leman in the late 1960s. The algorithm has a surprising number of seemingly unrelated characterisations in terms of logic, algebra, linear and semi-definite programming, and graph homomorphisms. Due to its simplicity and efficiency, it is an important subroutine of all modern graph isomorphism tools. In recent years, further applications in linear optimisation, probabilistic inference, and machine learning have surfaced. In the first part of my talk, I will give an introduction to the Weisfeiler-Leman algorithm and its various characterisations. In the second part I will speak about its applications, in particular about recent work relating the algorithm to graph neural networks.
Cite as

Martin Grohe. Weisfeiler and Leman’s Unlikely Journey from Graph Isomorphism to Neural Networks (Invited Talk). In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{grohe:LIPIcs.STACS.2020.2,
  author =	{Grohe, Martin},
  title =	{{Weisfeiler and Leman’s Unlikely Journey from Graph Isomorphism to Neural Networks}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.2},
  URN =		{urn:nbn:de:0030-drops-118634},
  doi =		{10.4230/LIPIcs.STACS.2020.2},
  annote =	{Keywords: Weisfeiler adn Leman algorithm, Graph isomorphism, Neural network, logic, algebra, linear and semi-definite programming}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.54
The Complexity of Homomorphism Indistinguishability

Authors: Jan Böker, Yijia Chen, Martin Grohe, and Gaurav Rattan

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
For every graph class {F}, let HomInd({F}) be the problem of deciding whether two given graphs are homomorphism-indistinguishable over {F}, i.e., for every graph F in {F}, the number hom(F, G) of homomorphisms from F to G equals the corresponding number hom(F, H) for H. For several natural graph classes (such as paths, trees, bounded treewidth graphs), homomorphism-indistinguishability over the class has an efficient structural characterization, resulting in polynomial time solvability [H. Dell et al., 2018]. In particular, it is known that two non-isomorphic graphs are homomorphism-indistinguishable over the class {T}_k of graphs of treewidth k if and only if they are not distinguished by k-dimensional Weisfeiler-Leman algorithm, a central heuristic for isomorphism testing: this characterization implies a polynomial time algorithm for HomInd({T}_k), for every fixed k in N. In this paper, we show that there is a polynomial-time-decidable class {F} of undirected graphs of bounded treewidth such that HomInd({F}) is undecidable. Our second hardness result concerns the class {K} of complete graphs. We show that HomInd({K}) is co-NP-hard, and in fact, we show completeness for the class C_=P (under P-time Turing reductions). On the algorithmic side, we show that HomInd({P}) can be solved in polynomial time for the class {P} of directed paths. We end with a brief study of two variants of the HomInd({F}) problem: (a) the problem of lexographic-comparison of homomorphism numbers of two graphs, and (b) the problem of computing certain distance-measures (defined via homomorphism numbers) between two graphs.
Cite as

Jan Böker, Yijia Chen, Martin Grohe, and Gaurav Rattan. The Complexity of Homomorphism Indistinguishability. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 54:1-54:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{boker_et_al:LIPIcs.MFCS.2019.54,
  author =	{B\"{o}ker, Jan and Chen, Yijia and Grohe, Martin and Rattan, Gaurav},
  title =	{{The Complexity of Homomorphism Indistinguishability}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{54:1--54:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.54},
  URN =		{urn:nbn:de:0030-drops-109980},
  doi =		{10.4230/LIPIcs.MFCS.2019.54},
  annote =	{Keywords: graph homomorphism numbers, counting complexity, treewidth}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICALP.2019.2
Symmetry and Similarity (Invited Talk)

Authors: Martin Grohe

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
Deciding if two graphs are isomorphic, or equivalently, computing the symmetries of a graph, is a fundamental algorithmic problem. It has many interesting applications, and it is one of the few natural problems in the class NP whose complexity status is still unresolved. Three years ago, Babai (STOC 2016) gave a quasi-polynomial time isomorphism algorithm. Despite of this breakthrough, the question for a polynomial algorithm remains wide open. Related to the isomorphism problem is the problem of determining the similarity between graphs. Variations of this problems are known as robust graph isomorphism or graph matching (the latter in the machine learning and computer vision literature). This problem is significantly harder than the isomorphism problem, both from a complexity theoretical and from a practical point of view, but for many applications it is the more relevant problem. My talk will be a survey of recent progress on the isomorphism and on the similarity problem. I will focus on generic algorithmic strategies (as opposed to algorithms tailored towards specific graph classes) that have proved to be useful and interesting in various context, both theoretical and practical.
Cite as

Martin Grohe. Symmetry and Similarity (Invited Talk). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{grohe:LIPIcs.ICALP.2019.2,
  author =	{Grohe, Martin},
  title =	{{Symmetry and Similarity}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.2},
  URN =		{urn:nbn:de:0030-drops-105787},
  doi =		{10.4230/LIPIcs.ICALP.2019.2},
  annote =	{Keywords: Graph Isomorphism, Graph Similarity, Graph Matching}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2019.117
A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus (Track B: Automata, Logic, Semantics, and Theory of Programming)

Authors: Martin Grohe and Sandra Kiefer

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
The Weisfeiler-Leman (WL) dimension of a graph is a measure for the inherent descriptive complexity of the graph. While originally derived from a combinatorial graph isomorphism test called the Weisfeiler-Leman algorithm, the WL dimension can also be characterised in terms of the number of variables that is required to describe the graph up to isomorphism in first-order logic with counting quantifiers. It is known that the WL dimension is upper-bounded for all graphs that exclude some fixed graph as a minor [M. Grohe, 2017]. However, the bounds that can be derived from this general result are astronomic. Only recently, it was proved that the WL dimension of planar graphs is at most 3 [S. Kiefer et al., 2017]. In this paper, we prove that the WL dimension of graphs embeddable in a surface of Euler genus g is at most 4g+3. For the WL dimension of graphs embeddable in an orientable surface of Euler genus g, our approach yields an upper bound of 2g + 3.
Cite as

Martin Grohe and Sandra Kiefer. A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus (Track B: Automata, Logic, Semantics, and Theory of Programming). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 117:1-117:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{grohe_et_al:LIPIcs.ICALP.2019.117,
  author =	{Grohe, Martin and Kiefer, Sandra},
  title =	{{A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{117:1--117:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.117},
  URN =		{urn:nbn:de:0030-drops-106931},
  doi =		{10.4230/LIPIcs.ICALP.2019.117},
  annote =	{Keywords: Weisfeiler-Leman algorithm, finite-variable logic, isomorphism testing, planar graphs, bounded genus}
}
Document
DOI: 10.4230/DagRep.8.6.1
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 18231)

Authors: Martin Grohe, Venkatesan Guruswami, and Stanislav Zivny

Published in: Dagstuhl Reports, Volume 8, Issue 6 (2019)

Abstract
Constraint satisfaction has always played a central role in computational complexity theory; appropriate versions of CSPs are classical complete problems for most standard complexity classes. CSPs constitute a very rich and yet sufficiently manageable class of problems to give a good perspective on general computational phenomena. For instance, they help to understand which mathematical properties make a computational problem tractable (in a wide sense, e.g., polynomial-time solvable, non-trivially approximable, fixed-parameter tractable, or definable in a weak logic). In the last decade, research activity in this area has significantly intensified and hugely impressive progress was made. The Dagstuhl Seminar 18231 "The Constraint Satisfaction Problem: Complexity and Approximability" was aimed at bringing together researchers using all the different techniques in the study of the CSP so that they can share their insights obtained during the past three years. This report documents the material presented during the course of the seminar.
Cite as

Martin Grohe, Venkatesan Guruswami, and Stanislav Zivny. The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 18231). In Dagstuhl Reports, Volume 8, Issue 6, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{grohe_et_al:DagRep.8.6.1,
  author =	{Grohe, Martin and Guruswami, Venkatesan and Zivny, Stanislav},
  title =	{{The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 18231)}},
  pages =	{1--18},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2018},
  volume =	{8},
  number =	{6},
  editor =	{Grohe, Martin and Guruswami, Venkatesan and Zivny, Stanislav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.8.6.1},
  URN =		{urn:nbn:de:0030-drops-100251},
  doi =		{10.4230/DagRep.8.6.1},
  annote =	{Keywords: Constraint satisfaction problem (CSP); Computational complexity; CSP dichotomy conjecture; Hardness of approximation; Unique games conjecture; Parameterised complexity; Descriptive complexity; Universal algebra; Logic; Semidefinite programming}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.20
Graph Similarity and Approximate Isomorphism

Authors: Martin Grohe, Gaurav Rattan, and Gerhard J. Woeginger

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
The graph similarity problem, also known as approximate graph isomorphism or graph matching problem, has been extensively studied in the machine learning community, but has not received much attention in the algorithms community: Given two graphs G,H of the same order n with adjacency matrices A_G,A_H, a well-studied measure of similarity is the Frobenius distance dist(G,H):=min_{pi}|A_G^{pi}-A_H|_F, where pi ranges over all permutations of the vertex set of G, where A_G^pi denotes the matrix obtained from A_G by permuting rows and columns according to pi, and where |M |_F is the Frobenius norm of a matrix M. The (weighted) graph similarity problem, denoted by GSim (WSim), is the problem of computing this distance for two graphs of same order. This problem is closely related to the notoriously hard quadratic assignment problem (QAP), which is known to be NP-hard even for severely restricted cases. It is known that GSim (WSim) is NP-hard; we strengthen this hardness result by showing that the problem remains NP-hard even for the class of trees. Identifying the boundary of tractability for WSim is best done in the framework of linear algebra. We show that WSim is NP-hard as long as one of the matrices has unbounded rank or negative eigenvalues: hence, the realm of tractability is restricted to positive semi-definite matrices of bounded rank. Our main result is a polynomial time algorithm for the special case where the associated (weighted) adjacency graph for one of the matrices has a bounded number of twin equivalence classes. The key parameter underlying our algorithm is the clustering number of a graph; this parameter arises in context of the spectral graph drawing machinery.
Cite as

Martin Grohe, Gaurav Rattan, and Gerhard J. Woeginger. Graph Similarity and Approximate Isomorphism. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 20:1-20:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{grohe_et_al:LIPIcs.MFCS.2018.20,
  author =	{Grohe, Martin and Rattan, Gaurav and Woeginger, Gerhard J.},
  title =	{{Graph Similarity and Approximate Isomorphism}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{20:1--20:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.20},
  URN =		{urn:nbn:de:0030-drops-96021},
  doi =		{10.4230/LIPIcs.MFCS.2018.20},
  annote =	{Keywords: Graph Similarity, Quadratic Assignment Problem, Approximate Graph Isomorphism}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.40
Lovász Meets Weisfeiler and Leman

Authors: Holger Dell, Martin Grohe, and Gaurav Rattan

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
In this paper, we relate a beautiful theory by Lovász with a popular heuristic algorithm for the graph isomorphism problem, namely the color refinement algorithm and its k-dimensional generalization known as the Weisfeiler-Leman algorithm. We prove that two graphs G and H are indistinguishable by the color refinement algorithm if and only if, for all trees T, the number Hom(T,G) of homomorphisms from T to G equals the corresponding number Hom(T,H) for H. There is a natural system of linear equations whose nonnegative integer solutions correspond to the isomorphisms between two graphs. The nonnegative real solutions to this system are called fractional isomorphisms, and two graphs are fractionally isomorphic if and only if the color refinement algorithm cannot distinguish them (Tinhofer 1986, 1991). We show that, if we drop the nonnegativity constraints, that is, if we look for arbitrary real solutions, then a solution to the linear system exists if and only if, for all t, the two graphs have the same number of length-t walks. We lift the results for trees to an equivalence between numbers of homomorphisms from graphs of tree width k, the k-dimensional Weisfeiler-Leman algorithm, and the level-k Sherali-Adams relaxation of our linear program. We also obtain a partial result for graphs of bounded path width and solutions to our system where we drop the nonnegativity constraints. A consequence of our results is a quasi-linear time algorithm to decide whether, for two given graphs G and H, there is a tree T with Hom(T,G)!=Hom(T,H).
Cite as

Holger Dell, Martin Grohe, and Gaurav Rattan. Lovász Meets Weisfeiler and Leman. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 40:1-40:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dell_et_al:LIPIcs.ICALP.2018.40,
  author =	{Dell, Holger and Grohe, Martin and Rattan, Gaurav},
  title =	{{Lov\'{a}sz Meets Weisfeiler and Leman}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{40:1--40:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.40},
  URN =		{urn:nbn:de:0030-drops-90444},
  doi =		{10.4230/LIPIcs.ICALP.2018.40},
  annote =	{Keywords: graph isomorphism, graph homomorphism numbers, tree width}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.67
An Improved Isomorphism Test for Bounded-Tree-Width Graphs

Authors: Martin Grohe, Daniel Neuen, Pascal Schweitzer, and Daniel Wiebking

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We give a new fpt algorithm testing isomorphism of n-vertex graphs of tree width k in time 2^{k polylog(k)} poly n, improving the fpt algorithm due to Lokshtanov, Pilipczuk, Pilipczuk, and Saurabh (FOCS 2014), which runs in time 2^{O(k^5 log k)}poly n. Based on an improved version of the isomorphism-invariant graph decomposition technique introduced by Lokshtanov et al., we prove restrictions on the structure of the automorphism groups of graphs of tree width k. Our algorithm then makes heavy use of the group theoretic techniques introduced by Luks (JCSS 1982) in his isomorphism test for bounded degree graphs and Babai (STOC 2016) in his quasipolynomial isomorphism test. In fact, we even use Babai's algorithm as a black box in one place. We give a second algorithm which, at the price of a slightly worse run time 2^{O(k^2 log k)}poly n, avoids the use of Babai's algorithm and, more importantly, has the additional benefit that it can also be used as a canonization algorithm.
Cite as

Martin Grohe, Daniel Neuen, Pascal Schweitzer, and Daniel Wiebking. An Improved Isomorphism Test for Bounded-Tree-Width Graphs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 67:1-67:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{grohe_et_al:LIPIcs.ICALP.2018.67,
  author =	{Grohe, Martin and Neuen, Daniel and Schweitzer, Pascal and Wiebking, Daniel},
  title =	{{An Improved Isomorphism Test for Bounded-Tree-Width Graphs}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{67:1--67:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.67},
  URN =		{urn:nbn:de:0030-drops-90714},
  doi =		{10.4230/LIPIcs.ICALP.2018.67},
  annote =	{Keywords: graph isomorphism, graph canonization, tree width, decompositions}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.8
Quasi-4-Connected Components

Authors: Martin Grohe

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We introduce a new decomposition of a graphs into quasi-4-connected components, where we call a graph quasi-4-connected if it is 3-connected and it only has separations of order 3 that separate a single vertex from the rest of the graph. Moreover, we give a cubic time algorithm computing the decomposition of a given graph. Our decomposition into quasi-4-connected components refines the well-known decompositions of graphs into biconnected and triconnected components. We relate our decomposition to Robertson and Seymour's theory of tangles by establishing a correspondence between the quasi-4-connected components of a graph and its tangles of order 4.
Cite as

Martin Grohe. Quasi-4-Connected Components. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{grohe:LIPIcs.ICALP.2016.8,
  author =	{Grohe, Martin},
  title =	{{Quasi-4-Connected Components}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{8:1--8:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.8},
  URN =		{urn:nbn:de:0030-drops-62740},
  doi =		{10.4230/LIPIcs.ICALP.2016.8},
  annote =	{Keywords: decompositions, connectivity, tangles}
}
Document
DOI: 10.4230/DagRep.5.4.98
Theory and Practice of SAT Solving (Dagstuhl Seminar 15171)

Authors: Armin Biere, Vijay Ganesh, Martin Grohe, Jakob Nordström, and Ryan Williams

Published in: Dagstuhl Reports, Volume 5, Issue 4 (2015)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 15171 "Theory and Practice of SAT Solving". The purpose of this workshop was to explore one of the most significant problems in all of computer science, namely that of computing whether formulas in propositional logic are satisfiable or not. This problem is believed to be intractable in general (by the theory of NP-completeness). However, the last two decades have seen dramatic developments in algorithmic techniques, and today so-called SAT solvers are routinely and successfully used to solve large-scale real-world instances in a wide range of application areas. A surprising aspect of this development is that the best current SAT solvers are still to a large extent based on methods from the early 1960s, which can often handle formulas with millions of variables but may also get hopelessly stuck on formulas with just a few hundred variables. The fundamental question of when SAT solvers perform well or badly, and what underlying mathematical properties of the formulas influence SAT solver performance, remains very poorly understood. Another intriguing aspect is that much stronger mathematical methods of reasoning about propositional logic formulas are known today, in particular methods based on algebra and geometry, and these methods would seem to have great potential based on theoretical studies. However, attempts at harnessing the power of such methods have conspicuously failed to deliver any significant improvements in practical performance. This workshop gathered leading researchers in applied and theoretical areas of SAT and computational complexity to stimulate an increased exchange of ideas between these two communities. We see great opportunities for fruitful interplay between theoretical and applied research in this area, and believe that this workshop showed beyond doubt that a more vigorous interaction between the two has potential for major long-term impact in computer science, as well for applications in industry.
Cite as

Armin Biere, Vijay Ganesh, Martin Grohe, Jakob Nordström, and Ryan Williams. Theory and Practice of SAT Solving (Dagstuhl Seminar 15171). In Dagstuhl Reports, Volume 5, Issue 4, pp. 98-122, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{biere_et_al:DagRep.5.4.98,
  author =	{Biere, Armin and Ganesh, Vijay and Grohe, Martin and Nordstr\"{o}m, Jakob and Williams, Ryan},
  title =	{{Theory and Practice of SAT Solving (Dagstuhl Seminar 15171)}},
  pages =	{98--122},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{5},
  number =	{4},
  editor =	{Biere, Armin and Ganesh, Vijay and Grohe, Martin and Nordstr\"{o}m, Jakob and Williams, Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.4.98},
  URN =		{urn:nbn:de:0030-drops-53520},
  doi =		{10.4230/DagRep.5.4.98},
  annote =	{Keywords: SAT, Boolean SAT solvers, SAT solving, conflict-driven clause learning, Gr\"{o}bner bases, pseudo-Boolean solvers, proof complexity, computational complexity, parameterized complexity}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.FSTTCS.2014.31
Colour Refinement: A Simple Partitioning Algorithm with Applications From Graph Isomorphism Testing to Machine Learning (Invited Talk)

Authors: Martin Grohe

Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)

Abstract
Colour refinement is a simple algorithm that partitions the vertices of a graph according their "iterated degree sequence." It has very efficient implementations, running in quasilinear time, and a surprisingly wide range of applications. The algorithm has been designed in the context of graph isomorphism testing, and it is used an important subroutine in almost all practical graph isomorphism tools. Somewhat surprisingly, other applications in machine learning, probabilistic inference, and linear programming have surfaced recently. In the first part of my talk, I will introduce the basic algorithm as well as higher dimensional extensions known as the k-dimensional Weisfeiler-Lehman algorithm. I will also discuss an unexpected connection between colour refinement and a natural linear programming approach to graph isomorphism testing. In the second part of my talk, I will discuss various applications of colour refinement.
Cite as

Martin Grohe. Colour Refinement: A Simple Partitioning Algorithm with Applications From Graph Isomorphism Testing to Machine Learning (Invited Talk). In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, p. 31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{grohe:LIPIcs.FSTTCS.2014.31,
  author =	{Grohe, Martin},
  title =	{{Colour Refinement: A Simple Partitioning Algorithm with Applications From Graph Isomorphism Testing to Machine Learning}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{31--31},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Raman, Venkatesh and Suresh, S. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.31},
  URN =		{urn:nbn:de:0030-drops-48290},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.31},
  annote =	{Keywords: Color Refinement, Graph Isomorphism, Machine Learning}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.FSTTCS.2013.21
Characterisations of Nowhere Dense Graphs (Invited Talk)

Authors: Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

Abstract
Nowhere dense classes of graphs were introduced by Nesetril and Ossona de Mendez as a model for "sparsity" in graphs. It turns out that nowhere dense classes of graphs can be characterised in many different ways and have been shown to be equivalent to other concepts studied in areas such as (finite) model theory. Therefore, the concept of nowhere density seems to capture a natural property of graph classes generalising for example classes of graphs which exclude a fixed minor, have bounded degree or bounded local tree-width. In this paper we give a self-contained introduction to the concept of nowhere dense classes of graphs focussing on the various ways in which they can be characterised. We also briefly sketch algorithmic applications these characterisations have found in the literature.
Cite as

Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Characterisations of Nowhere Dense Graphs (Invited Talk). In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 21-40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{grohe_et_al:LIPIcs.FSTTCS.2013.21,
  author =	{Grohe, Martin and Kreutzer, Stephan and Siebertz, Sebastian},
  title =	{{Characterisations of Nowhere Dense Graphs}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{21--40},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Seth, Anil and Vishnoi, Nisheeth K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.21},
  URN =		{urn:nbn:de:0030-drops-44029},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.21},
  annote =	{Keywords: Graph Algorithms, Algorithmic Graph Structure Theory, Finite Model Theory, Nowhere Dense Classes of Graphs}
}
Document
DOI: 10.4230/LIPIcs.CSL.2012.289
Pebble Games and Linear Equations

Authors: Martin Grohe and Martin Otto

Published in: LIPIcs, Volume 16, Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (2012)

Abstract
We give a new, simplified and detailed account of the correspondence between levels of the Sherali-Adams relaxation of graph isomorphism and levels of pebble-game equivalence with counting (higher-dimensional Weisfeiler-Lehman colour refinement). The correspondence between basic colour refinement and fractional isomorphism, due to Ramana, Scheinerman and Ullman, is re-interpreted as the base level of Sherali-Adams and generalised to higher levels in this sense by Atserias and Maneva, who prove that the two resulting hierarchies interleave. In carrying this analysis further, we here give (a) a precise characterisation of the level-k Sherali-Adams relaxation in terms of a modified counting pebble game; (b) a variant of the Sherali-Adams levels that precisely match the k-pebble counting game; (c) a proof that the interleaving between these two hierarchies is strict. We also investigate the variation based on boolean arithmetic instead of real/rational arithmetic and obtain analogous correspondences and separations for plain k-pebble equivalence (without counting). Our results are driven by considerably simplified accounts of the underlying combinatorics and linear algebra.
Cite as

Martin Grohe and Martin Otto. Pebble Games and Linear Equations. In Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 16, pp. 289-304, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{grohe_et_al:LIPIcs.CSL.2012.289,
  author =	{Grohe, Martin and Otto, Martin},
  title =	{{Pebble Games and Linear Equations}},
  booktitle =	{Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL},
  pages =	{289--304},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-42-2},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{16},
  editor =	{C\'{e}gielski, Patrick and Durand, Arnaud},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2012.289},
  URN =		{urn:nbn:de:0030-drops-36790},
  doi =		{10.4230/LIPIcs.CSL.2012.289},
  annote =	{Keywords: Finite model theory, finite variable logics, graph isomorphism, Weisfeiler- Lehman algorithm, linear programming, Sherali–Adams hierarchy}
}
Document
DOI: 10.4230/LIPIcs.CSL.2011.277
L-Recursion and a new Logic for Logarithmic Space

Authors: Martin Grohe, Berit Grußien, André Hernich, and Bastian Laubner

Published in: LIPIcs, Volume 12, Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (2011)

Abstract
We extend first-order logic with counting by a new operator that allows it to formalise a limited form of recursion which can be evaluated in logarithmic space. The resulting logic LREC has a data complexity in LOGSPACE, and it defines LOGSPACE-complete problems like deterministic reachability and Boolean formula evaluation. We prove that LREC is strictly more expressive than deterministic transitive closure logic with counting and incomparable in expressive power with symmetric transitive closure logic STC and transitive closure logic (with or without counting). LREC is strictly contained in fixed-point logic with counting FPC. We also study an extension LREC= of LREC that has nicer closure properties and is more expressive than both LREC and STC, but is still contained in FPC and has a data complexity in LOGSPACE. Our main results are that LREC captures LOGSPACE on the class of directed trees and that LREC= captures LOGSPACE on the class of interval graphs.
Cite as

Martin Grohe, Berit Grußien, André Hernich, and Bastian Laubner. L-Recursion and a new Logic for Logarithmic Space. In Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 12, pp. 277-291, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{grohe_et_al:LIPIcs.CSL.2011.277,
  author =	{Grohe, Martin and Gru{\ss}ien, Berit and Hernich, Andr\'{e} and Laubner, Bastian},
  title =	{{L-Recursion and a new Logic for Logarithmic Space}},
  booktitle =	{Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL},
  pages =	{277--291},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-32-3},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{12},
  editor =	{Bezem, Marc},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2011.277},
  URN =		{urn:nbn:de:0030-drops-32373},
  doi =		{10.4230/LIPIcs.CSL.2011.277},
  annote =	{Keywords: descriptive complexity, logarithmic space, fixed-point logics}
}
Document
DOI: 10.4230/DagRep.1.3.42
Computational Complexity of Discrete Problems (Dagstuhl Seminar 11121)

Authors: Martin Grohe, Michal Koucky, Rüdiger Reischik, and Dieter van Melkebeek

Published in: Dagstuhl Reports, Volume 1, Issue 3 (2011)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 11121 ``Computational Complexity of Discrete Problems''. The first section gives an overview of the topics covered and the organization of the meeting. Section~2 lists the talks given in chronological order. The last section contains the abstracts of the talks.
Cite as

Martin Grohe, Michal Koucky, Rüdiger Reischik, and Dieter van Melkebeek. Computational Complexity of Discrete Problems (Dagstuhl Seminar 11121). In Dagstuhl Reports, Volume 1, Issue 3, pp. 42-66, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@Article{grohe_et_al:DagRep.1.3.42,
  author =	{Grohe, Martin and Koucky, Michal and Reischik, R\"{u}diger and van Melkebeek, Dieter},
  title =	{{Computational Complexity of Discrete Problems (Dagstuhl Seminar 11121)}},
  pages =	{42--66},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2011},
  volume =	{1},
  number =	{3},
  editor =	{Grohe, Martin and Koucky, Michal and Reischik, R\"{u}diger and van Melkebeek, Dieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.3.42},
  URN =		{urn:nbn:de:0030-drops-31935},
  doi =		{10.4230/DagRep.1.3.42},
  annote =	{Keywords: Discrete problems, computational complexity, Turing machines, Boolean circuits, quantum computing, communication and query complexity, extractors, pseudorandomness, derandomization, approximation, coding cryptography, algorithmic learning}
}
Document
DOI: 10.4230/DagSemProc.09441.1
09441 Abstracts Collection – The Constraint Satisfaction Problem: Complexity and Approximability

Authors: Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, and Andrei Krokhin

Published in: Dagstuhl Seminar Proceedings, Volume 9441, The Constraint Satisfaction Problem: Complexity and Approximability (2010)

Abstract
From 25th to 30th October 2009, the Dagstuhl Seminar 09441 ``The Constraint Satisfaction Problem: Complexity and Approximability'' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, and Andrei Krokhin. 09441 Abstracts Collection – The Constraint Satisfaction Problem: Complexity and Approximability. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Seminar Proceedings, Volume 9441, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{bulatov_et_al:DagSemProc.09441.1,
  author =	{Bulatov, Andrei A. and Grohe, Martin and Kolaitis, Phokion G. and Krokhin, Andrei},
  title =	{{09441 Abstracts Collection – The Constraint Satisfaction Problem: Complexity and Approximability}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9441},
  editor =	{Andrei A. Bulatov and Martin Grohe and Phokion G. Kolaitis and Andrei Krokhin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09441.1},
  URN =		{urn:nbn:de:0030-drops-23710},
  doi =		{10.4230/DagSemProc.09441.1},
  annote =	{Keywords: Constraint satisfaction problem (CSP), satisfiability, computational complexity, CSP dichotomy conjecture, hardness of approximation, unique games conjecture, universal algebra, logic}
}
Document
DOI: 10.4230/DagSemProc.09441.2
09441 Executive Summary – The Constraint Satisfaction Problem: Complexity and Approximability

Authors: Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, and Andrei Krokhin

Published in: Dagstuhl Seminar Proceedings, Volume 9441, The Constraint Satisfaction Problem: Complexity and Approximability (2010)

Abstract
The seminar brought together forty researchers from di®erent highly advanced areas of constraint satisfaction and with complementary ex- pertise (logical, algebraic, combinatorial, probabilistic aspects). The list of participants contained both senior and junior researchers and a small number of advanced graduate students.
Cite as

Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, and Andrei Krokhin. 09441 Executive Summary – The Constraint Satisfaction Problem: Complexity and Approximability. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Seminar Proceedings, Volume 9441, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{bulatov_et_al:DagSemProc.09441.2,
  author =	{Bulatov, Andrei A. and Grohe, Martin and Kolaitis, Phokion G. and Krokhin, Andrei},
  title =	{{09441 Executive Summary – The Constraint Satisfaction Problem: Complexity and Approximability}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9441},
  editor =	{Andrei A. Bulatov and Martin Grohe and Phokion G. Kolaitis and Andrei Krokhin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09441.2},
  URN =		{urn:nbn:de:0030-drops-23706},
  doi =		{10.4230/DagSemProc.09441.2},
  annote =	{Keywords: Constraint satisfaction problem (CSP), satisfiability, computational complexity, CSP dichotomy conjecture, hardness of approximation, unique games conjecture, universal algebra, logic}
}
Document
DOI: 10.4230/LIPIcs.STACS.2009.1838
Enumerating Homomorphisms

Authors: Andrei A. Bulatov, Victor Dalmau, Martin Grohe, and Daniel Marx

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
The homomorphism problem for relational structures is an abstract way of formulating constraint satisfaction problems (CSP) and various problems in database theory. The decision version of the homomorphism problem received a lot of attention in literature; in particular, the way the graph-theoretical structure of the variables and constraints influences the complexity of the problem is intensively studied. Here we study the problem of enumerating all the solutions with polynomial delay from a similar point of view. It turns out that the enumeration problem behaves very differently from the decision version. We give evidence that it is unlikely that a characterization result similar to the decision version can be obtained. Nevertheless, we show nontrivial cases where enumeration can be done with polynomial delay.
Cite as

Andrei A. Bulatov, Victor Dalmau, Martin Grohe, and Daniel Marx. Enumerating Homomorphisms. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 231-242, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{bulatov_et_al:LIPIcs.STACS.2009.1838,
  author =	{Bulatov, Andrei A. and Dalmau, Victor and Grohe, Martin and Marx, Daniel},
  title =	{{Enumerating Homomorphisms}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{231--242},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1838},
  URN =		{urn:nbn:de:0030-drops-18385},
  doi =		{10.4230/LIPIcs.STACS.2009.1838},
  annote =	{Keywords: }
}
Document
DOI: 10.4230/LIPIcs.STACS.2009.1821
A Complexity Dichotomy for Partition Functions with Mixed Signs

Authors: Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, and Marc Thurley

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
\emph{Partition functions}, also known as \emph{homomorphism functions}, form a rich family of graph invariants that contain combinatorial invariants such as the number of $k$-colourings or the number of independent sets of a graph and also the partition functions of certain ``spin glass'' models of statistical physics such as the Ising model. Building on earlier work by Dyer and Greenhill (2000) and Bulatov and Grohe (2005), we completely classify the computational complexity of partition functions. Our main result is a dichotomy theorem stating that every partition function is either computable in polynomial time or \#P-complete. Partition functions are described by symmetric matrices with real entries, and we prove that it is decidable in polynomial time in terms of the matrix whether a given partition function is in polynomial time or \#P-complete. While in general it is very complicated to give an explicit algebraic or combinatorial description of the tractable cases, for partition functions described by a Hadamard matrices --- these turn out to be central in our proofs --- we obtain a simple algebraic tractability criterion, which says that the tractable cases are those ``representable'' by a quadratic polynomial over the field $\ensuremath{\mathbb{F}_2}$.
Cite as

Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, and Marc Thurley. A Complexity Dichotomy for Partition Functions with Mixed Signs. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 493-504, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{goldberg_et_al:LIPIcs.STACS.2009.1821,
  author =	{Goldberg, Leslie Ann and Grohe, Martin and Jerrum, Mark and Thurley, Marc},
  title =	{{A Complexity Dichotomy for Partition Functions with Mixed Signs}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{493--504},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1821},
  URN =		{urn:nbn:de:0030-drops-18217},
  doi =		{10.4230/LIPIcs.STACS.2009.1821},
  annote =	{Keywords: Computational complexity}
}
Document
DOI: 10.4230/DagSemProc.06401.5
Constraint Satisfaction with Succinctly Specified Relations

Authors: Hubie Chen and Martin Grohe

Published in: Dagstuhl Seminar Proceedings, Volume 6401, Complexity of Constraints (2006)

Abstract
The general intractability of the constraint satisfaction problem has motivated the study of the complexity of restricted cases of this problem. Thus far, the literature has primarily considered the formulation of the CSP where constraint relations are given explicitly. We initiate the systematic study of CSP complexity with succinctly specified constraint relations. This is joint work with Hubie Chen.
Cite as

Hubie Chen and Martin Grohe. Constraint Satisfaction with Succinctly Specified Relations. In Complexity of Constraints. Dagstuhl Seminar Proceedings, Volume 6401, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:DagSemProc.06401.5,
  author =	{Chen, Hubie and Grohe, Martin},
  title =	{{Constraint Satisfaction with Succinctly Specified Relations}},
  booktitle =	{Complexity of Constraints},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6401},
  editor =	{Nadia Creignou and Phokion Kolaitis and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06401.5},
  URN =		{urn:nbn:de:0030-drops-8022},
  doi =		{10.4230/DagSemProc.06401.5},
  annote =	{Keywords: Constraint satisfaction, complexity, succinct representations}
}
Document
DOI: 10.4230/DagSemProc.05301.1
05301 Abstracts Collection – Exact Algorithms and Fixed-Parameter Tractability

Authors: Rod Downey, Martin Grohe, and Gerhard Woeginger

Published in: Dagstuhl Seminar Proceedings, Volume 5301, Exact Algorithms and Fixed-Parameter Tractability (2006)

Abstract
From 24.07.05 to 29.07.05, the Dagstuhl Seminar 05301 ``Exact Algorithms and Fixed-Parameter Tractability'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. This is a collection of abstracts of the presentations given during the seminar.
Cite as

Rod Downey, Martin Grohe, and Gerhard Woeginger. 05301 Abstracts Collection – Exact Algorithms and Fixed-Parameter Tractability. In Exact Algorithms and Fixed-Parameter Tractability. Dagstuhl Seminar Proceedings, Volume 5301, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{downey_et_al:DagSemProc.05301.1,
  author =	{Downey, Rod and Grohe, Martin and Woeginger, Gerhard},
  title =	{{05301 Abstracts Collection – Exact Algorithms and Fixed-Parameter Tractability}},
  booktitle =	{Exact Algorithms and Fixed-Parameter Tractability},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5301},
  editor =	{Rod Downey and Martin Grohe and Gerhard Woeginger},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05301.1},
  URN =		{urn:nbn:de:0030-drops-4405},
  doi =		{10.4230/DagSemProc.05301.1},
  annote =	{Keywords: Fixed-parameter tractability, parameterized complexity, exact algorithms}
}
Document
DOI: 10.4230/DagSemProc.05301.2
05301 Summary – Exact Algorithms and Fixed-Parameter Tractability

Authors: Rod Downey, Martin Grohe, and Gerhard Woeginger

Published in: Dagstuhl Seminar Proceedings, Volume 5301, Exact Algorithms and Fixed-Parameter Tractability (2006)

Abstract
Summary of the Dagstuhl Seminar held 24. July - 29. July 2005.
Cite as

Rod Downey, Martin Grohe, and Gerhard Woeginger. 05301 Summary – Exact Algorithms and Fixed-Parameter Tractability. In Exact Algorithms and Fixed-Parameter Tractability. Dagstuhl Seminar Proceedings, Volume 5301, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{downey_et_al:DagSemProc.05301.2,
  author =	{Downey, Rod and Grohe, Martin and Woeginger, Gerhard},
  title =	{{05301 Summary – Exact Algorithms and Fixed-Parameter Tractability}},
  booktitle =	{Exact Algorithms and Fixed-Parameter Tractability},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5301},
  editor =	{Rod Downey and Martin Grohe and Gerhard Woeginger},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05301.2},
  URN =		{urn:nbn:de:0030-drops-4396},
  doi =		{10.4230/DagSemProc.05301.2},
  annote =	{Keywords: Fixed-parameter tractability, parameterized complexity, exact algorithms}
}
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