Document

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

We give a new upper bound for the Group and Quasigroup Isomorphism problems when the input structures are given explicitly by multiplication tables. We show that these problems can be computed by polynomial size nondeterministic circuits of unbounded fan-in with $O(\log\log n)$ depth and $O(\log^2 n)$ nondeterministic bits,
where $n$ is the number of group elements. This improves the existing upper bound from \cite{Wolf 94} for the problems. In the previous upper bound the circuits have bounded fan-in but depth $O(\log^2 n)$ and also $O(\log^2 n)$ nondeterministic bits. We then prove that the kind of circuits from our upper bound cannot compute the Parity function. Since Parity is AC0 reducible to Graph Isomorphism, this implies that Graph Isomorphism is strictly harder than Group or Quasigroup Isomorphism under the ordering defined by AC0 reductions.

Arkadev Chattopadhyay, Jacobo Torán, and Fabian Wagner. Graph Isomorphism is not AC^0 reducible to Group Isomorphism. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 317-326, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{chattopadhyay_et_al:LIPIcs.FSTTCS.2010.317, author = {Chattopadhyay, Arkadev and Tor\'{a}n, Jacobo and Wagner, Fabian}, title = {{Graph Isomorphism is not AC^0 reducible to Group Isomorphism}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {317--326}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-23-1}, ISSN = {1868-8969}, year = {2010}, volume = {8}, editor = {Lodaya, Kamal and Mahajan, Meena}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.317}, URN = {urn:nbn:de:0030-drops-28748}, doi = {10.4230/LIPIcs.FSTTCS.2010.317}, annote = {Keywords: Complexity, Algorithms, Group Isomorphism Problem, Circuit Com plexity} }

Document

**Published in:** LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

The Graph Isomorphism problem restricted to graphs of bounded treewidth or bounded tree distance width are known to be solvable in polynomial time~\cite{Bo90},\cite{YBFT}.We give restricted space algorithms for these problems proving the following results:
\begin{itemize}
\item Isomorphism for bounded tree distance width graphs is in \Log\ and thus complete for the class. We also show that for this kind of graphs a canon can be computed within logspace.
\item For bounded treewidth graphs, when both input graphs are given together with a tree decomposition, the problem of whether there is an isomorphism which respects the decompositions (i.e.\ considering only isomorphisms mapping bags in one decomposition blockwise onto bags in the other decomposition)
is in \Log.
\item For bounded treewidth graphs, when one of the input graphs is given with a tree decomposition the isomorphism problem is in \LogCFL.
\item As a corollary the isomorphism problem for bounded treewidth graphs is in \LogCFL. This improves the known \TCone\ upper bound for the problem given by Grohe and Verbitsky~\cite{GV06}.
\end{itemize}

Bireswar Das, Jacobo Torán, and Fabian Wagner. Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 227-238, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.STACS.2010.2457, author = {Das, Bireswar and Tor\'{a}n, Jacobo and Wagner, Fabian}, title = {{Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs}}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, pages = {227--238}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-16-3}, ISSN = {1868-8969}, year = {2010}, volume = {5}, editor = {Marion, Jean-Yves and Schwentick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2457}, URN = {urn:nbn:de:0030-drops-24570}, doi = {10.4230/LIPIcs.STACS.2010.2457}, annote = {Keywords: Complexity, Algorithms, Graph Isomorphism Problem, Treewidth, LogCFL} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010)

Graph Isomorphism is the prime example of a computational problem with a wide
difference between the best known lower and upper bounds on its complexity. There
is a significant gap between extant lower and upper bounds for planar graphs as well.
We bridge the gap for this natural and important special case by presenting an upper
bound that matches the known log-space hardness [JKMT03]. In fact, we show the
formally stronger result that planar graph canonization is in log-space. This improves the
previously known upper bound of AC1 [MR91].
Our algorithm first constructs the biconnected component tree of a connected planar
graph and then refines each biconnected component into a triconnected component
tree. The next step is to log-space reduce the biconnected planar graph isomorphism and
canonization problems to those for 3-connected planar graphs, which are known to be in
log-space by [DLN08]. This is achieved by using the above decomposition, and by making
significant modifications to Lindell’s algorithm for tree canonization, along with changes
in the space complexity analysis.
The reduction from the connected case to the biconnected case requires further new
ideas including a non-trivial case analysis and a group theoretic lemma to bound the
number of automorphisms of a colored 3-connected planar graph.

Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner. Planar Graph Isomorphism is in Log-Space. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 9421, pp. 1-32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:DagSemProc.09421.6, author = {Datta, Samir and Limaye, Nutan and Nimbhorkar, Prajakta and Thierauf, Thomas and Wagner, Fabian}, title = {{Planar Graph Isomorphism is in Log-Space}}, booktitle = {Algebraic Methods in Computational Complexity}, pages = {1--32}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {9421}, editor = {Manindra Agrawal and Lance Fortnow and Thomas Thierauf and Christopher Umans}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09421.6}, URN = {urn:nbn:de:0030-drops-24169}, doi = {10.4230/DagSemProc.09421.6}, annote = {Keywords: Planar Graphs, Graph Isomorphism, Logspace} }

Document

**Published in:** LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)

Graph isomorphism is an important and widely studied computational problem with
a yet unsettled complexity.
However, the exact complexity is known for isomorphism of various classes of
graphs. Recently, \cite{DLNTW09} proved that planar isomorphism is complete for log-space.
We extend this result %of \cite{DLNTW09}
further to the classes of graphs which exclude $K_{3,3}$ or $K_5$ as
a minor, and give a log-space algorithm.
Our algorithm decomposes $K_{3,3}$ minor-free graphs into biconnected and those further into triconnected
components, which are known to be either planar or $K_5$ components \cite{Vaz89}. This gives a triconnected
component tree similar to that for planar graphs. An extension of the log-space algorithm of \cite{DLNTW09}
can then be used to decide the isomorphism problem.
For $K_5$ minor-free graphs, we consider $3$-connected components.
These are either planar or isomorphic to the four-rung mobius ladder on $8$ vertices
or, with a further decomposition, one obtains planar $4$-connected components \cite{Khu88}.
We give an algorithm to get a unique
decomposition of $K_5$ minor-free graphs into bi-, tri- and $4$-connected components,
and construct trees, accordingly.
Since the algorithm of \cite{DLNTW09} does
not deal with four-connected component trees, it needs to be modified in a quite non-trivial way.

Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner. Graph Isomorphism for K_{3,3}-free and K_5-free graphs is in Log-space. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 145-156, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.FSTTCS.2009.2314, author = {Datta, Samir and Nimbhorkar, Prajakta and Thierauf, Thomas and Wagner, Fabian}, title = {{Graph Isomorphism for K\underline\{3,3\}-free and K\underline5-free graphs is in Log-space}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {145--156}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-13-2}, ISSN = {1868-8969}, year = {2009}, volume = {4}, editor = {Kannan, Ravi and Narayan Kumar, K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2314}, URN = {urn:nbn:de:0030-drops-23144}, doi = {10.4230/LIPIcs.FSTTCS.2009.2314}, annote = {Keywords: Graph isomorphism, K\underline\{3,3\}-free graphs, K\underline5-free graphs, log-space} }

Document

**Published in:** LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

The isomorphism problem for planar graphs is known to be
efficiently solvable. For planar 3-connected graphs, the
isomorphism problem can be solved by efficient parallel algorithms,
it is in the class $AC^1$.
In this paper we improve the upper bound for planar 3-connected
graphs to unambiguous logspace, in fact to $UL cap coUL$. As a
consequence of our method we get that the isomorphism problem for
oriented graphs is in $NL$. We also show that the problems are
hard for $L$.

Thomas Thierauf and Fabian Wagner. The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 633-644, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{thierauf_et_al:LIPIcs.STACS.2008.1327, author = {Thierauf, Thomas and Wagner, Fabian}, title = {{The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace}}, booktitle = {25th International Symposium on Theoretical Aspects of Computer Science}, pages = {633--644}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-06-4}, ISSN = {1868-8969}, year = {2008}, volume = {1}, editor = {Albers, Susanne and Weil, Pascal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1327}, URN = {urn:nbn:de:0030-drops-13273}, doi = {10.4230/LIPIcs.STACS.2008.1327}, annote = {Keywords: } }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail