Search Results

Documents authored by Rattan, Gaurav

Document
DOI: 10.4230/LIPIcs.CP.2024.3
The Complexity of Symmetry Breaking Beyond Lex-Leader

Authors: Markus Anders, Sofia Brenner, and Gaurav Rattan

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract
Symmetry breaking is a widely popular approach to enhance solvers in constraint programming, such as those for SAT or MIP. Symmetry breaking predicates (SBPs) typically impose an order on variables and single out the lexicographic leader (lex-leader) in each orbit of assignments. Although it is NP-hard to find complete lex-leader SBPs, incomplete lex-leader SBPs are widely used in practice. In this paper, we investigate the complexity of computing complete SBPs, lex-leader or otherwise, for SAT. Our main result proves a natural barrier for efficiently computing SBPs: efficient certification of graph non-isomorphism. Our results explain the difficulty of obtaining short SBPs for important CP problems, such as matrix-models with row-column symmetries and graph generation problems. Our results hold even when SBPs are allowed to introduce additional variables. We show polynomial upper bounds for breaking certain symmetry groups, namely automorphism groups of trees and wreath products of groups with efficient SBPs.
Cite as

Markus Anders, Sofia Brenner, and Gaurav Rattan. The Complexity of Symmetry Breaking Beyond Lex-Leader. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 3:1-3:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{anders_et_al:LIPIcs.CP.2024.3,
  author =	{Anders, Markus and Brenner, Sofia and Rattan, Gaurav},
  title =	{{The Complexity of Symmetry Breaking Beyond Lex-Leader}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{3:1--3:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.3},
  URN =		{urn:nbn:de:0030-drops-206881},
  doi =		{10.4230/LIPIcs.CP.2024.3},
  annote =	{Keywords: symmetry breaking, boolean satisfiability, matrix models, graph isomorphism}
}
Document
DOI: 10.4230/LIPIcs.SAT.2024.4
Satsuma: Structure-Based Symmetry Breaking in SAT

Authors: Markus Anders, Sofia Brenner, and Gaurav Rattan

Published in: LIPIcs, Volume 305, 27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024)

Abstract
Symmetry reduction is crucial for solving many interesting SAT instances in practice. Numerous approaches have been proposed, which try to strike a balance between symmetry reduction and computational overhead. Arguably the most readily applicable method is the computation of static symmetry breaking constraints: a constraint restricting the search-space to non-symmetrical solutions is added to a given SAT instance. A distinct advantage of static symmetry breaking is that the SAT solver itself is not modified. A disadvantage is that the strength of symmetry reduction is usually limited. In order to boost symmetry reduction, the state-of-the-art tool BreakID [Devriendt et. al] pioneered the identification and tailored breaking of a particular substructure of symmetries, the so-called row interchangeability groups. In this paper, we propose a new symmetry breaking tool called satsuma. The core principle of our tool is to exploit more diverse but frequently occurring symmetry structures. This is enabled by new practical detection algorithms for row interchangeability, row-column symmetry, Johnson symmetry, and various combinations. Based on the resulting structural description, we then produce symmetry breaking constraints. We compare this new approach to BreakID on a range of instance families exhibiting symmetry. Our benchmarks suggest improved symmetry reduction in the presence of Johnson symmetry and comparable performance in the presence of row-column symmetry. Moreover, our implementation runs significantly faster, even though it identifies more diverse structures.
Cite as

Markus Anders, Sofia Brenner, and Gaurav Rattan. Satsuma: Structure-Based Symmetry Breaking in SAT. In 27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 305, pp. 4:1-4:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{anders_et_al:LIPIcs.SAT.2024.4,
  author =	{Anders, Markus and Brenner, Sofia and Rattan, Gaurav},
  title =	{{Satsuma: Structure-Based Symmetry Breaking in SAT}},
  booktitle =	{27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024)},
  pages =	{4:1--4:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-334-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{305},
  editor =	{Chakraborty, Supratik and Jiang, Jie-Hong Roland},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2024.4},
  URN =		{urn:nbn:de:0030-drops-205269},
  doi =		{10.4230/LIPIcs.SAT.2024.4},
  annote =	{Keywords: symmetry breaking, boolean satisfiability, graph isomorphism}
}
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
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
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.MFCS.2016.13
The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs

Authors: Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Sebastian Kuhnert, and Gaurav Rattan

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
In this paper we study the complexity of the following problems: 1. Given a colored graph X=(V,E,c), compute a minimum cardinality set of vertices S (subset of V) such that no nontrivial automorphism of X fixes all vertices in S. A closely related problem is computing a minimum base S for a permutation group G <= S_n given by generators, i.e., a minimum cardinality subset S of [n] such that no nontrivial permutation in G fixes all elements of S. Our focus is mainly on the parameterized complexity of these problems. We show that when k=|S| is treated as parameter, then both problems are MINI[1]-hard. For the dual problems, where k=n-|S| is the parameter, we give FPT~algorithms. 2. A notion closely related to fixing is called individualization. Individualization combined with the Weisfeiler-Leman procedure is a fundamental technique in algorithms for Graph Isomorphism. Motivated by the power of individualization, in the present paper we explore the complexity of individualization: what is the minimum number of vertices we need to individualize in a given graph such that color refinement "succeeds" on it. Here "succeeds" could have different interpretations, and we consider the following: It could mean the individualized graph becomes: (a) discrete, (b) amenable, (c)compact, or (d) refinable. In particular, we study the parameterized versions of these problems where the parameter is the number of vertices individualized. We show a dichotomy: For graphs with color classes of size at most 3 these problems can be solved in polynomial time, while starting from color class size 4 they become W[P]-hard.
Cite as

Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Sebastian Kuhnert, and Gaurav Rattan. The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.MFCS.2016.13,
  author =	{Arvind, Vikraman and Fuhlbr\"{u}ck, Frank and K\"{o}bler, Johannes and Kuhnert, Sebastian and Rattan, Gaurav},
  title =	{{The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{13:1--13:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.13},
  URN =		{urn:nbn:de:0030-drops-64294},
  doi =		{10.4230/LIPIcs.MFCS.2016.13},
  annote =	{Keywords: parameterized complexity, graph automorphism, fixing number, base size, individualization}
}
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