Suppose we are given a set of generators for a group G of permutations of a colored set A. The color automorphism problem for G involves finding generators for the …
Suppose we are given a set of generators for a group G of permutations of a colored set A. The color automorphism problem for G involves finding generators for the subgroup of G which stabilizes the color classes. Testing isomorphism of graphs of valence ≤ t is polynomial-time reducible to the color automorphism problem for groups with small simple sections. The algorithm for the latter problem involves several divide-and-conquer tricks. The problem is solved sequentially on the G-orbits. An orbit is broken into a minimal set of blocks permuted by G. The hypothesis on G guarantees the existence of a 'large' subgroup P which acts as a p-group on the blocks. A similar process is repeated for each coset of P on G. Some results on primitive permutation groups are used to show that the algorithm runs in polynomial time.
Many complex questions in biology, physics, and mathematics can be mapped to the graph isomorphism problem and the closely related graph automorphism problem. In particular, these problems appear in the …
Many complex questions in biology, physics, and mathematics can be mapped to the graph isomorphism problem and the closely related graph automorphism problem. In particular, these problems appear in the context of network visualization, computational logic, structure recognition, and dynamics of complex systems. Both problems have previously been suspected, but not proven, to be NP-complete. In this paper we propose an algorithm that solves both graph automorphism and isomorphism problems in polynomial time. The algorithm can be easily implemented and thus opens up a wide range of applications.
An explicit algorithm is presented for testing whether two non-directed graphs are isomorphic or not. It is shown that for a graph of n vertices, the number of n independent …
An explicit algorithm is presented for testing whether two non-directed graphs are isomorphic or not. It is shown that for a graph of n vertices, the number of n independent operations needed for the test is polynomial in n. A proof that the algorithm actually performs the test is presented.
We use the concept of a Kirchhoff resistor network (alternatively random walk on a network) to probe connected graphs and produce symmetry revealing canonical labelings of the graph(s) nodes and …
We use the concept of a Kirchhoff resistor network (alternatively random walk on a network) to probe connected graphs and produce symmetry revealing canonical labelings of the graph(s) nodes and edges.
ADVERTISEMENT RETURN TO ISSUEPREVArticleNEXTComputational Techniques for the Automorphism Groups of GraphsK. BalasubramanianCite this: J. Chem. Inf. Comput. Sci. 1994, 34, 3, 621–626Publication Date (Print):May 1, 1994Publication History Published online1 May …
ADVERTISEMENT RETURN TO ISSUEPREVArticleNEXTComputational Techniques for the Automorphism Groups of GraphsK. BalasubramanianCite this: J. Chem. Inf. Comput. Sci. 1994, 34, 3, 621–626Publication Date (Print):May 1, 1994Publication History Published online1 May 2002Published inissue 1 May 1994https://pubs.acs.org/doi/10.1021/ci00019a022https://doi.org/10.1021/ci00019a022research-articleACS PublicationsRequest reuse permissionsArticle Views80Altmetric-Citations7LEARN ABOUT THESE METRICSArticle Views are the COUNTER-compliant sum of full text article downloads since November 2008 (both PDF and HTML) across all institutions and individuals. These metrics are regularly updated to reflect usage leading up to the last few days.Citations are the number of other articles citing this article, calculated by Crossref and updated daily. Find more information about Crossref citation counts.The Altmetric Attention Score is a quantitative measure of the attention that a research article has received online. Clicking on the donut icon will load a page at altmetric.com with additional details about the score and the social media presence for the given article. Find more information on the Altmetric Attention Score and how the score is calculated. Share Add toView InAdd Full Text with ReferenceAdd Description ExportRISCitationCitation and abstractCitation and referencesMore Options Share onFacebookTwitterWechatLinked InRedditEmail Other access options Get e-Alerts
A polynomial algorithm for graphs' isomorphism testing is constructed in assumption that there exists a corresponding polynomial algorithm for graphs with trivial automorphism group.
A polynomial algorithm for graphs' isomorphism testing is constructed in assumption that there exists a corresponding polynomial algorithm for graphs with trivial automorphism group.
A permutation group on n letters may always be represented by a small set of generators, even though its size may be exponential in n. We show that it is …
A permutation group on n letters may always be represented by a small set of generators, even though its size may be exponential in n. We show that it is practical to use such a representation since many problems such as membership testing, equality testing, and inclusion testing are decidable in polynomial time. In addition, we demonstrate that the normal closure of a subgroup can be computed in polynomial time, and that this proceaure can be used to test a group for solvability. We also describe an approach to computing the intersection of two groups. The procedures and techniques have wide applicability and have recently been used to improve many graph isomorphism algorithms.
Let us be given two graphs $Γ_1$, $Γ_2$ of $n$ vertices. Are they isomorphic? If they are, the set of isomorphisms from $Γ_1$ to $Γ_2$ can be identified with a …
Let us be given two graphs $Γ_1$, $Γ_2$ of $n$ vertices. Are they isomorphic? If they are, the set of isomorphisms from $Γ_1$ to $Γ_2$ can be identified with a coset $H\cdotπ$ inside the symmetric group on $n$ elements. How do we find $π$ and a set of generators of $H$? The challenge of giving an always efficient algorithm answering these questions remained open for a long time. Babai has recently shown how to solve these problems -- and others linked to them -- in quasi-polynomial time, i.e. in time $\exp\left(O(\log n)^{O(1)}\right)$. His strategy is based in part on the algorithm by Luks (1980/82), who solved the case of graphs of bounded degree.
This article deals with new polynomial time algorithm for graph isomorphism testing.
This article deals with new polynomial time algorithm for graph isomorphism testing.
It's important to design polynomial time algorithms to test if two graphs are isomorphic at least for some special classes of graphs. An approach to this was presented by Eugene …
It's important to design polynomial time algorithms to test if two graphs are isomorphic at least for some special classes of graphs. An approach to this was presented by Eugene M. Luks(1981) in the work \textit{Isomorphism of Graphs of Bounded Valence Can Be Tested in Polynomial Time}. Unfortunately, it was a theoretical algorithm and was very difficult to put into practice. On the other hand, there is no known implementation of the algorithm, although Galil, Hoffman and Luks(1983) shows an improvement of this algorithm running in $O(n^3 \log n)$. The two main goals of this master thesis are to explain more carefully the algorithm of Luks(1981), including a detailed study of the complexity and, then to provide an efficient implementation in SAGE system. It is divided into four chapters plus an appendix.
Given a graph $G$, the graph $[G]$ obtained by adding, for each pair of vertices of $G$, a unique vertex adjacent to both vertices is called the binding graph of …
Given a graph $G$, the graph $[G]$ obtained by adding, for each pair of vertices of $G$, a unique vertex adjacent to both vertices is called the binding graph of $G$. In this work, we show that the class of binding graphs is graph-isomorphism complete and that the stable partitions of binding graphs by the Weisfeiler-Lehman (WL) algorithm produce automorphism partitions. To test the isomorphism of two graphs $G$ and $H$, one computes the stable graph of the binding graph $[G\uplus H]$ for the disjoint union graph $G\uplus H$. The automorphism partition reveals the isomorphism of $G$ and $H$. Because the WL algorithm is a polynomial-time procedure, the claim can be made that the graph-isomorphism problem is in complexity class $\mathtt{P}$.
In this paper, we show the existence of a polynomial time graph isomorphism algorithm for all graphs excluding graphs that are locally trianglefree. This particular class of graphs allows to …
In this paper, we show the existence of a polynomial time graph isomorphism algorithm for all graphs excluding graphs that are locally trianglefree. This particular class of graphs allows to divide the graph into neighbourhood sub-graph where each of induced sub-graph (neighbourhood) has at least 2 vertices. We construct all possible permutations for each induced sub-graph using a search tree. We construct automorphisms of subgraphs based on these permutations. Finally, we decide isomorphism through automorphisms .
The author expects that the solution, present in this paper, may lead to a faster algorithm for the general case of graph isomorphism (using barycentric subdivision ). The paper might affect group isomorphism also as we may construct graphs (corresponds to a particular group) in way so we can avoid it to be a triangle free graph. Since,for a given group G , each choice of a generating set will give a different Cayley graph.
Abstract We resolve the computational complexity of Graph Isomorphism for classes of graphs characterized by two forbidden induced subgraphs $$ H_{1} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>H</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:math> and …
Abstract We resolve the computational complexity of Graph Isomorphism for classes of graphs characterized by two forbidden induced subgraphs $$ H_{1} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>H</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:math> and $$H_2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>H</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:math> for all but six pairs $$(H_1,H_2)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>H</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>H</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . Schweitzer had previously shown that the number of open cases was finite, but without specifying the open cases. Grohe and Schweitzer proved that Graph Isomorphism is polynomial-time solvable on graph classes of bounded clique-width. Our work combines known results such as these with new results. By exploiting a relationship between Graph Isomorphism and clique-width, we simultaneously reduce the number of open cases for boundedness of clique-width for $$(H_1,H_2)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>H</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>H</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -free graphs to five.
The author announces methods for efficient management of solvable matrix groups over finite fields. He shows that solvability and nilpotence can be tested in polynomial-time. Such efficiency seems unlikely for …
The author announces methods for efficient management of solvable matrix groups over finite fields. He shows that solvability and nilpotence can be tested in polynomial-time. Such efficiency seems unlikely for membership-testing, which subsumes the discrete-log problem. However, assuming that the primes in mod G mod (other than the field characteristic) are polynomially-bounded, membership-testing and many other computational problems are in polynomial time. These problems include finding stabilizers of vectors and of subspaces and finding centralizers and intersections of subgroups. An application to solvable permutation groups puts the problem of finding normalizers of subgroups into polynomial time. Some of the results carry over directly to finite matrix groups over algebraic number fields; thus, testing solvability is in polynomial time, as is testing membership and finding Sylow subgroups.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
In this paper we consider the problems of testing isomorphism of tensors, $p$-groups, cubic forms, algebras, and more, which arise from a variety of areas, including machine learning, group theory, …
In this paper we consider the problems of testing isomorphism of tensors, $p$-groups, cubic forms, algebras, and more, which arise from a variety of areas, including machine learning, group theory, and cryptography. These problems can all be cast as orbit problems on multi-way arrays under different group actions. Our first two main results are: 1. All the aforementioned isomorphism problems are equivalent under polynomial-time reductions, in conjunction with the recent results of Futorny-Grochow-Sergeichuk (Lin. Alg. Appl., 2019). 2. Isomorphism of $d$-tensors reduces to isomorphism of 3-tensors, for any $d \geq 3$. Our results suggest that these isomorphism problems form a rich and robust equivalence class, which we call Tensor Isomorphism-complete, or TI-complete. We then leverage the techniques used in the above results to prove two first-of-their-kind results for Group Isomorphism (GpI): 3. We give a reduction from GpI for $p$-groups of exponent $p$ and small class ($c < p$) to GpI for $p$-groups of exponent $p$ and class 2. The latter are widely believed to be the hardest cases of GpI, but as far as we know, this is the first reduction from any more general class of groups to this class. 4. We give a search-to-decision reduction for isomorphism of $p$-groups of exponent $p$ and class 2 in time $|G|^{O(\log \log |G|)}$. While search-to-decision reductions for Graph Isomorphism (GI) have been known for more than 40 years, as far as we know this is the first non-trivial search-to-decision reduction in the context of GpI. Our main technique for (1), (3), and (4) is a linear-algebraic analogue of the classical graph coloring gadget, which was used to obtain the search-to-decision reduction for GI. This gadget construction may be of independent interest and utility. The technique for (2) gives a method for encoding an arbitrary tensor into an algebra.
We place many computational problems over solvable black-box groups in the counting complexity classes SPP or LWPP\@. The classes SPP and LWPP are considered classes of low counting complexity. In …
We place many computational problems over solvable black-box groups in the counting complexity classes SPP or LWPP\@. The classes SPP and LWPP are considered classes of low counting complexity. In particular, SPP is low (powerless when used as oracles) for all gap-definable counting classes (PP\@, C$_=$P\@, Mod$_k$P\@, etc.) and LWPP is low for PP and C$_=$P\@. The results improve the upper bounds for these problems proved in [Arvind and Vinodchandran, Theoret. Comput. Sci., 180 (1997), pp. 17--45], where the authors place these problems in randomized versions of SPP and LWPP. Because of the randomization, upper bounds in that paper implied lowness only for the class PP. The results in this paper favor the belief that these problems are unlikely to be complete for NP.
This paper discusses the uses of computer algebra within statistics and probability. A distinction is drawn between the use of computer algebra packages to support investigations, by performing calculations, ankl …
This paper discusses the uses of computer algebra within statistics and probability. A distinction is drawn between the use of computer algebra packages to support investigations, by performing calculations, ankl their use to implement structure; to build in elements of a theory (such as stochastic calculus or the Taylor string theory of Barndorff Nielsen and others) as a preliminary to research investigations. Brief surveys are given of instances in the literature of use of computer algebra in probability and statistics. Two examples of implementations of structure are discussed, both drawn from the author's own work with the computer algebra package REDUCE. One is a simple demonstration using moments of the Poisson distribution. The other is itovsn3 , an implementation of the semimartingale stochastic calculus. It is described how itovsn3 may be used to derive the characteristic function of the Lévy stochastic area, following a proof due to S. Janson. Prospects for future work and for work in progress are discussed.
We prove that the combinatorial Weisfeiler-Leman algorithm of dimension (3k+4) is a complete isomorphism test for the class of all graphs of rank width at most k. Rank width is …
We prove that the combinatorial Weisfeiler-Leman algorithm of dimension (3k+4) is a complete isomorphism test for the class of all graphs of rank width at most k. Rank width is a graph invariant that, similarly to tree width, measures the width of a certain style of hierarchical decomposition of graphs; it is equivalent to clique width. It was known that isomorphism of graphs of rank width k is decidable in polynomial time (Grohe and Schweitzer, FOCS 2015), but the best previously known algorithm has a running time n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">f(k)</sup> for a non-elementary function f. Our result yields an isomorphism test for graphs of rank width k running in time n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(k)</sup> . Another consequence of our result is the first polynomial time canonisation algorithm for graphs of bounded rank width. Our second main result is that fixed-point logic with counting captures polynomial time on all graph classes of bounded rank width.
An automorphism of a graph $G$ with $n$ vertices is a bijective map $ϕ$ from $V(G)$ to itself such that $ϕ(v_i)ϕ(v_j)\in E(G)$ $\Leftrightarrow$ $v_i v_j\in E(G)$ for any two vertices …
An automorphism of a graph $G$ with $n$ vertices is a bijective map $ϕ$ from $V(G)$ to itself such that $ϕ(v_i)ϕ(v_j)\in E(G)$ $\Leftrightarrow$ $v_i v_j\in E(G)$ for any two vertices $v_i$ and $v_j$ of $G$. Denote by $\mathfrak{G}$ the group consisting of all automorphisms of $G$. As well-known, the structure of the action of $\mathfrak{G}$ on $V(G)$ is represented definitely by its block systems. On the other hand for each permutation $σ$ on $[n]$, there is a natural action on any vector $\pmb{v}=(v_1,v_2,\ldots,v_n)^t\in \mathbb{R}^n$ such that $σ\pmb{v}=(v_{σ^{-1}1},v_{σ^{-1}2},\ldots,v_{σ^{-1} n})^t$. Accordingly, we actually have a permutation representation of $\mathfrak{G}$ in $\mathbb{R}^n$. In this paper, we establish the some connections between block systems of $\mathfrak{G}$ and its irreducible representations, and by virtue of that we finally devise an algorithm outputting a generating set and all block systems of $\mathfrak{G}$ within time $n^{C \log n}$ for some constant $C$.
Abstract Random sampling is a technique for dealing with possible states or solutions having an exponentially large space. The best method of random sampling generally involves a random walk or …
Abstract Random sampling is a technique for dealing with possible states or solutions having an exponentially large space. The best method of random sampling generally involves a random walk or a Markov chain. A Markov chain requires a number of steps to approach equilibrium, and thus provide a good random sample of the state space. This number of steps is called mixing time, which can be calculated by thinking about how quickly its choices overwhelm the system’s memory of its initial state, the extent to which one part of a system influences another, and how smoothly probability flows from one part of the state space to another. This chapter explores random walks and rapid mixing, first by considering a classic example from physics: a block of iron. It then discusses transition matrices, ergodicity, coupling, spectral gap, and expanders, as well as the role of conductance and the spectral gap in rapid mixing. It concludes by showing that temporal mixing is closely associated with spatial mixing.
We give a new fpt algorithm testing isomorphism of $n$-vertex graphs of tree width $k$ in time $2^{k\operatorname{polylog} (k)}\operatorname{poly} (n)$, improving the fpt algorithm due to Lokshtanov, Pilipczuk, Pilipczuk, and …
We give a new fpt algorithm testing isomorphism of $n$-vertex graphs of tree width $k$ in time $2^{k\operatorname{polylog} (k)}\operatorname{poly} (n)$, improving the fpt algorithm due to Lokshtanov, Pilipczuk, Pilipczuk, and Saurabh (FOCS 2014), which runs in time $2^{\mathcal{O}(k^5\log k)}\operatorname{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 also give a second algorithm which, at the price of a slightly worse running time $2^{\mathcal{O}(k^2 \log k)}\operatorname{poly} (n)$, avoids the use of Babai's algorithm and, more importantly, has the additional benefit that it can also used as a canonization algorithm.
We resolve the computational complexity of Graph Isomorphism for classes of graphs characterized by two forbidden induced subgraphs $H_1$ and $H_2$ for all but six pairs $(H_1,H_2)$. Schweitzer had previously …
We resolve the computational complexity of Graph Isomorphism for classes of graphs characterized by two forbidden induced subgraphs $H_1$ and $H_2$ for all but six pairs $(H_1,H_2)$. Schweitzer had previously shown that the number of open cases was finite, but without specifying the open cases. Grohe and Schweitzer proved that Graph Isomorphism is polynomial-time solvable on graph classes of bounded clique-width. Our work combines known results such as these with new results. By exploiting a relationship between Graph Isomorphism and clique-width, we simultaneously reduce the number of open cases for boundedness of clique-width for $(H_1,H_2)$-free graphs to five.
We generalize the structure theorem of Robertson and Seymour for graphs excluding a fixed graph $H$ as a minor to graphs excluding $H$ as a topological subgraph. We prove that …
We generalize the structure theorem of Robertson and Seymour for graphs excluding a fixed graph $H$ as a minor to graphs excluding $H$ as a topological subgraph. We prove that for a fixed $H$, every graph excluding $H$ as a topological subgraph has a tree decomposition where each part is either almost embeddable to a fixed surface or has bounded degree with the exception of a bounded number of vertices. Furthermore, we prove that such a decomposition is computable by an algorithm that is fixed-parameter tractable with parameter $|H|$.
We present two algorithmic applications of our structure theorem. To illustrate the mechanics of a typical application of the structure theorem, we show that on graphs excluding $H$ as a topological subgraph, Partial Dominating Set (find $k$ vertices whose closed neighborhood has maximum size) can be solved in time $f(H,k)\cdot n^{O(1)}$ time. More significantly, we show that on graphs excluding $H$ as a topological subgraph, Graph Isomorphism can be solved in time $n^{f(H)}$. This result unifies and generalizes two previously known important polynomial-time solvable cases of Graph Isomorphism: bounded-degree graphs and $H$-minor free graphs. The proof of this result needs a generalization of our structure theorem to the context of invariant treelike decomposition.
We consider the group isomorphism problem: given two finite groups G and H specified by their multiplication tables, decide if G b H. The nlog n barrier for group isomorphism …
We consider the group isomorphism problem: given two finite groups G and H specified by their multiplication tables, decide if G b H. The nlog n barrier for group isomorphism has withstood all attacks --- even for the special cases of p-groups and solvable groups --- ever since the nlog n+O(1) generator-enumeration algorithm. In this work, we present the first significant improvement over nlog n by showing that group isomorphism is n(1/2) logpn+O(1) Turing reducible to composition-series isomorphism where p is the smallest prime dividing the order of the group. Combining our reduction with an nO(p/log p) algorithm for p-group composition-series isomorphism, we obtain an n(1/2) log n+O(1) algorithm for p-group isomorphism. We then generalize our techniques from p-groups using Sylow bases to derive an n(1/2) log n+O(log n/log log n) algorithm for solvable-group isomorphism. Finally, we relate group isomorphism to the collision problem which allows us replace the 1/2 in the exponents with 1/4 using randomized algorithms and 1/6 using quantum algorithms.
We show that the Graph Isomorphism (GI) problem and the related problems of String Isomorphism (under group action) (SI) and Coset Intersection (CI) can be solved in quasipolynomial (exp (logn) …
We show that the Graph Isomorphism (GI) problem and the related problems of String Isomorphism (under group action) (SI) and Coset Intersection (CI) can be solved in quasipolynomial (exp (logn) O(1) � ) time. The best previous bound for GI was exp(O( √ nlogn)), where n is the number of vertices (Luks, 1983); for the other two problems, the bound was similar, exp( e O( √ n)), where n is the size of the permutation domain (Babai, 1983). The algorithm builds on Luks’s SI framework and attacks the barrier configurations for Luks’s algorithm by group theoretic “local certificates” and combinatorial canonical partitioning techniques. We show that in a well-defined sense, Johnson graphs are the only obstructions to effective canonical partitioning.
We build a theory of black box groups, and apply it to matrix groups over finite fields. Elements of a black box group are encoded by strings of uniform length …
We build a theory of black box groups, and apply it to matrix groups over finite fields. Elements of a black box group are encoded by strings of uniform length and group operations are performd by an oracle. Subgroups are given by a list of generators. We prove that for such subgroups, membership and divisor of the order are in NP <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">B</sup> . (B is the group box oracle.) Under a plausible mathematical hypothesis on short presentations of finite simple groups, nom membership and exaact order will also be in NP <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">B</sup> and thus in NP <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">B</sup> ∩ NP <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">B</sup> .
The isomorphism problem for finite groups of order n (GpI) has long been known to be solvable in $n^{\log n+O(1)}$ time, but only recently were polynomial-time algorithms designed for several …
The isomorphism problem for finite groups of order n (GpI) has long been known to be solvable in $n^{\log n+O(1)}$ time, but only recently were polynomial-time algorithms designed for several interesting group classes. Inspired by recent progress, we revisit the strategy for GpI via the extension theory of groups. The extension theory describes how a normal subgroup N is related to G/N via G, and this naturally leads to a divide-and-conquer strategy that splits GpI into two subproblems: one regarding group actions on other groups, and one regarding group cohomology. When the normal subgroup N is abelian, this strategy is well-known. Our first contribution is to extend this strategy to handle the case when N is not necessarily abelian. This allows us to provide a unified explanation of all recent polynomial-time algorithms for special group classes. Guided by this strategy, to make further progress on GpI, we consider central-radical groups, proposed in Babai et al. (SODA 2011): the class of groups such that G mod its center has no abelian normal subgroups. This class is a natural extension of the group class considered by Babai et al. (ICALP 2012), namely those groups with no abelian normal subgroups. Following the above strategy, we solve GpI in $n^{O(\log \log n)}$ time for central-radical groups, and in polynomial time for several prominent subclasses of central-radical groups. We also solve GpI in $n^{O(\log\log n)}$ time for groups whose solvable normal subgroups are elementary abelian but not necessarily central. As far as we are aware, this is the first time there have been worst-case guarantees on a $n^{o(\log n)}$-time algorithm that tackles both aspects of GpI---actions and cohomology---simultaneously.
Let $G$ and $H$ be two simple graphs. A bijection $\phi:V(G)\rightarrow V(H)$ is called an isomorphism between $G$ and $H$ if $(\phi v_i)(\phi v_j)\in E(H)$ $\Leftrightarrow$ $v_i v_j\in E(G)$, $\forall …
Let $G$ and $H$ be two simple graphs. A bijection $\phi:V(G)\rightarrow V(H)$ is called an isomorphism between $G$ and $H$ if $(\phi v_i)(\phi v_j)\in E(H)$ $\Leftrightarrow$ $v_i v_j\in E(G)$, $\forall v_i,v_j \in V(G)$. In the case that $G = H$, we say $\phi$ an automorphism of $G$ and denote the group consisting of all automorphisms of $G$ by $\mathrm{Aut}~G$. As well-known, the problem of determining whether or not two given graphs are isomorphic is called Graph Isomorphism Problem (GI). One of key steps in resolving GI is to work out the partition $\Pi^*_G$ of $V(G)$ composed of orbits of $\mathrm{Aut}~G$. By means of geometric features of $\Pi^*_G$ and combinatorial constructions such as the multipartite graph $[\Pi^*_{t_1},\cdots,\Pi^*_{t_s}]$, we can reduce the problem of determining $\Pi_G^*$ to that of working out a series of partitions of $V(G)$ each of which consists of orbits of a stabilizer that fixes a sequence of vertices of $G$, and thus the determination of the partition $\Pi^*_v$ is a critical transition. On the other hand, we have for a given subspace $U \subseteq \mathbb{R}^n$ a permutation group $\mathrm{Aut}~U := \{ \sigma \in S_n : \sigma ~ U = U \}$. As a matter of fact, $\mathrm{Aut}~G = \cap_{\lambda \in \mathrm{spec} \mathbf{A}(G) } \mathrm{Aut}~V_{\lambda}$, and moreover we can obtain a good approximation $\Pi[ \oplus V_{\lambda} ; v ]$ to $\Pi_v^*$ by analyzing a decomposition of $V_{\lambda}$ resulted from the division of $V_{\lambda}$ by subspaces $\{ \mathrm{proj}[ V_{\lambda} ]( \pmb{e}_v )^{\perp} : v \in V(G) \}$. In fact, there is a close relation among subspaces spanned by cells of $\Pi[ \oplus V_{\lambda} ; v ]$ of $G$, which enables us to determine $\Pi_v^*$ more efficiently. In virtue of that, we devise a deterministic algorithm solving GI in time $n^{ O( \log n ) }$.
We show that a nontrivial graph isomorphism problem of two undirected graphs, and more generally, the permutation similarity of two given $n\times n$ matrices, is equivalent to equalities of volumes …
We show that a nontrivial graph isomorphism problem of two undirected graphs, and more generally, the permutation similarity of two given $n\times n$ matrices, is equivalent to equalities of volumes of the induced three convex bounded polytopes intersected with a given sequence of balls, centered at the origin with radii $t_i\in (0,\sqrt{n-1})$, where $\{t_i\}$ is an increasing sequence converging to $\sqrt{n-1}$. These polytopes are characterized by $n^2$ inequalities in at most $n^2$ variables. The existence of fpras for computing volumes of convex bodies gives rise to a semi-frpas of order $O^*(n^{14})$ at most to find if given two undirected graphs are isomorphic.
We show that a canonical form for strongly regular (s.r.) graphs can be found in time exp(O~(n1/5)) and therefore isomorphism of s.r. graphs can be tested within the same time …
We show that a canonical form for strongly regular (s.r.) graphs can be found in time exp(O~(n1/5)) and therefore isomorphism of s.r. graphs can be tested within the same time bound, where n is the number of vertices and the tilde hides a polylogarithmic factor. The best previous bound for testing isomorphism of s. r. graphs was exp(O~(n1/3)) (Spiel man, STOC 1996) while the bound for GI in general has been standing firmly at exp(O~(n1/2)) for three decades. (These results, too, provided canonical forms.) The previous bounds on isomorphism of s.r. graphs (Babai 1980 and Spiel man 1996) were based on the analysis of the classical individualization/refinement (I/R) heuristic. The present bound depends on a combination of a deeper analysis of the I/R heuristic with Luks's group theoretic divide-and-conquer methods following Babai-Luks (STOC 1983) and Miller (1983). Our analysis builds on Spiel man's work that brought Neumaier's 1979 classification of s.r. graphs to bear on the problem. One of Neumaier's classes, the line-graphs of Steiner 2-designs, has been eliminated as a bottleneck in recent work by the present authors (STOC'13). In the remaining hard cases, we have the benefit of Neumaier's claw bound" and its asymptotic consequences derived by Spiel man, some of which we improve via a new "clique geometry." We also prove, by an analysis of the I/R heuristic, that, with known (trivial) exceptions, s.r. graphs have exp(O~(n9/37)) automorphisms, improving Spiel man's exp(O~(n1/3)) bound. No knowledge of group theory is required for this paper. The group theoretic method is only used through an easily stated combinatorial consequence (Babai -- Luks, 1983 combined with Miller, 1983). While the bulk of this paper is joint work by the five authors, it also includes two contributions by subsets of the authors: the clique geometry [BW] and the auto orphism bound [CST]."
The graph isomorphism problem is a main problem which has numerous applications in different fields. Thus, finding an efficient and easy to implement method to discriminate non-isomorphic graphs is valuable. …
The graph isomorphism problem is a main problem which has numerous applications in different fields. Thus, finding an efficient and easy to implement method to discriminate non-isomorphic graphs is valuable. In this paper, a new method is introduced which is very simple and easy to implement, but very efficient in discriminating non-isomorphic graphs, in practice. This method does not need any heuristic attempt and based on the eigenvalues of a new matrix representation for graphs. It, almost always, separates non-isomorphic $n$-vertex graphs in time $O(n^3)$ and in worst cases such as strongly regular graphs, in time $O(n^4)$. Here, we show that this method, successfully, characterizes the isomorphism classes of studied instances of strongly regular graphs (up to 64 vertices). Strongly regular graphs are believed to be hard cases of the graph isomorphism problem.
special issue in honor of Laci Babai's 60th birthday: Combinatorics, Groups, Algorithms, and Complexity For an integer constant d \textgreater 0, let Gamma(d) denote the class of finite groups all …
special issue in honor of Laci Babai's 60th birthday: Combinatorics, Groups, Algorithms, and Complexity For an integer constant d \textgreater 0, let Gamma(d) denote the class of finite groups all of whose nonabelian composition factors lie in S-d; in particular, Gamma(d) includes all solvable groups. Motivated by applications to graph-isomorphism testing, there has been extensive study of the complexity of computation for permutation groups in this class. In particular, the problems of finding set stabilizers, intersections and centralizers have all been shown to be polynomial-time computable. A notable open issue for the class Gamma(d) has been the question of whether normalizers can be found in polynomial time. We resolve this question in the affirmative. We prove that, given permutation groups G, H \textless= Sym(Omega) such that G is an element of Gamma(d), the normalizer of H in G can be found in polynomial time. Among other new procedures, our method includes a key subroutine to solve the problem of finding stabilizers of subspaces in linear representations of permutation groups in Gamma(d).
For an integer constant d > 0, let Γd denote the class of finite groups all of whose nonabelian composition factors lie in Sd; in particular, Γd includes all solvable …
For an integer constant d > 0, let Γd denote the class of finite groups all of whose nonabelian composition factors lie in Sd; in particular, Γd includes all solvable groups. Motivated by applications to graph-isomorphism testing, there has been extensive study of the complexity of computation for permutation groups in this class. In particular, set-stabilizers, group intersections, and centralizers have all been shown to be polynomial-time computable. The most notable gap in the theory has been the question of whether normalizers of subgroups can be found in polynomial time. We resolve this question in the affirmative. Among other new procedures, the algorithm requires instances of subspace-stabilizers for certain linear representations and therefore some polynomial-time computation in matrix groups.
By a map we mean a $2$-cell decomposition of a closed compact surface, i.e., an embedding of a graph such that every face is homeomorphic to an open disc. Automorphism …
By a map we mean a $2$-cell decomposition of a closed compact surface, i.e., an embedding of a graph such that every face is homeomorphic to an open disc. Automorphism of a map can be thought of as a permutation of the vertices which preserves the vertex-edge-face incidences in the embedding. When the underlying surface is orientable, every automorphism of a map determines an angle-preserving homeomorphism of the surface. While it is conjectured that there is no "truly subquadratic" algorithm for testing map isomorphism for unconstrained genus, we present a linear-time algorithm for computing the generators of the automorphism group of a map, parametrized by the genus of the underlying surface. The algorithm applies a sequence of local reductions and produces a uniform map, while preserving the automorphism group. The automorphism group of the original map can be reconstructed from the automorphism group of the uniform map in linear time. We also extend the algorithm to non-orientable surfaces by making use of the antipodal double-cover.
Let H be a graph, and let C H ( G ) be the number of (subgraph isomorphic) copies of H contained in a graph G . We investigate the …
Let H be a graph, and let C H ( G ) be the number of (subgraph isomorphic) copies of H contained in a graph G . We investigate the fundamental problem of estimating C H ( G ). Previous results cover only a few specific instances of this general problem, for example the case when H has degree at most one (the monomer-dimer problem). In this paper we present the first general subcase of the subgraph isomorphism counting problem, which is almost always efficiently approximable. The results rely on a new graph decomposition technique. Informally, the decomposition is a labelling of the vertices such that every edge is between vertices with different labels, and for every vertex all neighbours with a higher label have identical labels. The labelling implicitly generates a sequence of bipartite graphs, which permits us to break the problem of counting embeddings of large subgraphs into that of counting embeddings of small subgraphs. Using this method, we present a simple randomized algorithm for the counting problem. For all decomposable graphs H and all graphs G , the algorithm is an unbiased estimator. Furthermore, for all graphs H having a decomposition where each of the bipartite graphs generated is small and almost all graphs G , the algorithm is a fully polynomial randomized approximation scheme. We show that the graph classes of H for which we obtain a fully polynomial randomized approximation scheme for almost all G includes graphs of degree at most two, bounded-degree forests, bounded-width grid graphs, subdivision of bounded-degree graphs, and major subclasses of outerplanar graphs, series-parallel graphs and planar graphs of large girth, whereas unbounded-width grid graphs are excluded. Moreover, our general technique can easily be applied to proving many more similar results.
Article Free Access Share on Faster isomorphism testing of strongly regular graphs Author: Daniel A. Spielman Computer Science Division, U.C. Berkeley, CA Computer Science Division, U.C. Berkeley, CAView Profile Authors …
Article Free Access Share on Faster isomorphism testing of strongly regular graphs Author: Daniel A. Spielman Computer Science Division, U.C. Berkeley, CA Computer Science Division, U.C. Berkeley, CAView Profile Authors Info & Claims STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of ComputingJuly 1996 Pages 576–584https://doi.org/10.1145/237814.238006Online:01 July 1996Publication History 28citation925DownloadsMetricsTotal Citations28Total Downloads925Last 12 Months57Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF
Let F be a finite field or an algebraic number field. In previous work we have shown how to find the basic building blocks (the radical and the simple components) …
Let F be a finite field or an algebraic number field. In previous work we have shown how to find the basic building blocks (the radical and the simple components) of a finite dimensional algebra over F in polynomial time (deterministically in characteristic zero and Las Vegas in the finite case). Here we address the more general problem of finding zero divisors in A. This problem is equivalent to finding a nontrivial common invariant subspace of a set of linear operators and includes, as a subcase, the problem of factoring polynomials over the field in question. In [FR] the problem of zero divisors has been reduced, in polynomial time (Las Vegas in the finite case), to the case of simple algebras. We show that, while zero divisors can be found in Las Vegas polynomial time if F is finite, the problem over the rationals might be substantially more difficult. We link the problem to hard number theoretic problems such as quadratic residuosity modulo a composite number. We show that assuming the Generalized Riemann Hypothesis, there exists a randomized polynomial time reduction from quadratic residuosity to determining whether or not a given 4-dimensional algebra over Q has zero divisors. It will follow that finding a pair of zero divisors is at least as hard as factoring squarefree integers.
If S,, is a Sylow p-subgroup of the symmetric group of degree pn, then any group of order pn may be imbedded in Sn. We may express Sn as the …
If S,, is a Sylow p-subgroup of the symmetric group of degree pn, then any group of order pn may be imbedded in Sn. We may express Sn as the complete product' C o C o ... o C of n cyclic groups of order p and the purpose of this paper is to show that any Sylow psubgroup of a classical group (see ?1) over the finite field GF(q) with q elements, where (q, p) = 1, is expressible as a direct product of basic subgroups En-C O C O ... o C (n factors), where Z is cyclic of order pr. (We assume always that p ;2.) Since C may be imbedded in S., we see that n is imbedded in Sn+r-l in a particularly simple way. The above r is defined by the equation q -1 =pt *where qI is the first power of q which is congruent to 1 mod p and * denotes some unspecified number prime to p. The case r = 1 is therefore of frequent occurrence, and then clearly SnSn Professor Philip Hall was my research supervisor in Cambridge (England) during the years 1949-1952 and it is a pleasure to acknowledge here my indebtedness to him for his generous encouragement.
Suppose we are given a set of generators for a group G of permutations of a colored set A. The color automorphism problem for G involves finding generators for the …
Suppose we are given a set of generators for a group G of permutations of a colored set A. The color automorphism problem for G involves finding generators for the subgroup of G which stabilizes the color classes. Testing isomorphism of graphs of valence ≤ t is polynomial-time reducible to the color automorphism problem for groups with small simple sections. The algorithm for the latter problem involves several divide-and-conquer tricks. The problem is solved sequentially on the G-orbits. An orbit is broken into a minimal set of blocks permuted by G. The hypothesis on G guarantees the existence of a 'large' subgroup P which acts as a p-group on the blocks. A similar process is repeated for each coset of P on G. Some results on primitive permutation groups are used to show that the algorithm runs in polynomial time.
Abstract. We present an O(V 4 log V ) coin flipping algorithm to test vertex-colored graphs with bounded color multiplicities for color-preserving isomorphism. We are also able to generate uniformly …
Abstract. We present an O(V 4 log V ) coin flipping algorithm to test vertex-colored graphs with bounded color multiplicities for color-preserving isomorphism. We are also able to generate uniformly distributed random automorphisms of such graphs. A more general result finds generators for the intersection of cylindric subgroups of a direct product of groups in O(n7/2 log n) time, where n is the length of the input string. This result will be applied in another paper to find a polynomial time coin flipping algorithm to test isomorphism of graphs with bounded eigenvalue multiplicities. The most general result says that if AutX is accessible by a chain G0 ≥ · · · ≥ Gk = AutX of quickly recognizable groups such that the indices |Gi−1 : Gi| are small (but unknown), the order of |G0| is known and there is a fast way of generating uniformly distributed random members of G0 then a set of generators of AutX can be found by a fast algorithm. Applications of the main result improve the complexity of isomorphism testing for graphs with bounded valences to exp(n1/2+o(1)) and for distributive lattices to O(n6 log logn). ∗Apart from possible typos, this is a verbatim transcript of the author’s 1979 technical report, “Monte Carlo algorithms in graph isomorphism testing” (Universite de Montreal, D.M.S. No. 79-10), with two footnotes added to correct a typo and a glaring omission in the original. We present an O(V 4 log V ) coin flipping algorithm to test vertex-colored graphs with bounded color multiplicities for color-preserving isomorphism. We are also able to generate uniformly distributed random automorphisms of such graphs. A more general result finds generators for the intersection of cylindric subgroups of a direct product of groups in O(n7/2 log n) time, where n is the length of the input string. This result will be applied in another paper to find a polynomial time coin flipping algorithm to test isomorphism of graphs with bounded eigenvalue multiplicities. The most general result says that if AutX is accessible by a chain G0 ≥ · · · ≥ Gk = AutX of quickly recognizable groups such that the indices |Gi−1 : Gi| are small (but unknown), the order of |G0| is known and there is a fast way of generating uniformly distributed random members of G0 then a set of generators of AutX can be found by a fast algorithm. Applications of the main result improve the complexity of isomorphism testing for graphs with bounded valences to exp(n1/2+o(1)) and for distributive lattices to O(n6 log logn). ∗Apart from possible typos, this is a verbatim transcript of the author’s 1979 technical report, “Monte Carlo algorithms in graph isomorphism testing” (Universite de Montreal, D.M.S. No. 79-10), with two footnotes added to correct a typo and a glaring omission in the original.
A permutation group on n letters may always be represented by a small set of generators, even though its size may be exponential in n. We show that it is …
A permutation group on n letters may always be represented by a small set of generators, even though its size may be exponential in n. We show that it is practical to use such a representation since many problems such as membership testing, equality testing, and inclusion testing are decidable in polynomial time. In addition, we demonstrate that the normal closure of a subgroup can be computed in polynomial time, and that this proceaure can be used to test a group for solvability. We also describe an approach to computing the intersection of two groups. The procedures and techniques have wide applicability and have recently been used to improve many graph isomorphism algorithms.