Search Results

Documents authored by Das, Bireswar

Document
DOI: 10.4230/LIPIcs.FSTTCS.2024.20
The Isomorphism Problem of Power Graphs and a Question of Cameron

Authors: Bireswar Das, Jinia Ghosh, and Anant Kumar

Published in: LIPIcs, Volume 323, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)

Abstract
We study the isomorphism problem of graphs that are defined in terms of groups, namely power graphs, directed power graphs, and enhanced power graphs. We design polynomial-time algorithms for the isomorphism problems for the power graphs, the directed power graphs and the enhanced power graphs arising from finite nilpotent groups. In contrast, no polynomial-time algorithm is known for the group isomorphism problem, even for nilpotent groups of class 2. Our algorithms do not require the underlying groups of the input graphs to be given. A crucial step in our algorithms is to reconstruct the directed power graph from the given power graph or the enhanced power graph. The problem of efficiently computing the directed power graph from a power graph or an enhanced power graph is due to Cameron [IJGT'22]. Bubboloni and Pinzauti [Arxiv'22] gave a polynomial-time algorithm to reconstruct the directed power graph from a power graph. We give an efficient algorithm to compute the directed power graph from an enhanced power graph. The tools and techniques that we design are general enough to give a different algorithm to compute the directed power graph from a power graph as well.
Cite as

Bireswar Das, Jinia Ghosh, and Anant Kumar. The Isomorphism Problem of Power Graphs and a Question of Cameron. In 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 323, pp. 20:1-20:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.FSTTCS.2024.20,
  author =	{Das, Bireswar and Ghosh, Jinia and Kumar, Anant},
  title =	{{The Isomorphism Problem of Power Graphs and a Question of Cameron}},
  booktitle =	{44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)},
  pages =	{20:1--20:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-355-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{323},
  editor =	{Barman, Siddharth and Lasota, S{\l}awomir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2024.20},
  URN =		{urn:nbn:de:0030-drops-222095},
  doi =		{10.4230/LIPIcs.FSTTCS.2024.20},
  annote =	{Keywords: Graph Isomorphism, Graphs defined on Groups, Power Graphs, Enhanced Power Graphs, Directed Power Graphs, Nilpotent Groups}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.25
Linear Space Data Structures for Finite Groups with Constant Query-Time

Authors: Bireswar Das, Anant Kumar, Shivdutt Sharma, and Dhara Thakkar

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
A finite group of order n can be represented by its Cayley table. In the word-RAM model the Cayley table of a group of order n can be stored using O(n²) words and can be used to answer a multiplication query in constant time. It is interesting to ask if we can design a data structure to store a group of order n that uses o(n²) space but can still answer a multiplication query in constant time. We design a constant query-time data structure that can store any finite group using O(n) words where n is the order of the group. Farzan and Munro (ISSAC 2006) gave an information theoretic lower bound of Ω(n) on the number of words to store a group of order n. Since our data structure achieves this lower bound and answers queries in constant time, it is optimal in both space usage and query-time. A crucial step in the process is essentially to design linear space and constant query-time data structures for nonabelian simple groups. The data structures for nonableian simple groups are designed using a lemma that we prove using the Classification Theorem for Finite Simple Groups (CFSG).
Cite as

Bireswar Das, Anant Kumar, Shivdutt Sharma, and Dhara Thakkar. Linear Space Data Structures for Finite Groups with Constant Query-Time. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.STACS.2022.25,
  author =	{Das, Bireswar and Kumar, Anant and Sharma, Shivdutt and Thakkar, Dhara},
  title =	{{Linear Space Data Structures for Finite Groups with Constant Query-Time}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.25},
  URN =		{urn:nbn:de:0030-drops-158350},
  doi =		{10.4230/LIPIcs.STACS.2022.25},
  annote =	{Keywords: Compact Data Structures, Space Efficient Representations, Finite Groups, Simple Groups, Classification Theorem for Finite Simple Groups}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2010.327
Colored Hypergraph Isomorphism is Fixed Parameter Tractable

Authors: V. Arvind, Bireswar Das, Johannes Köbler, and Seinosuke Toda

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

Abstract
We describe a fixed parameter tractable (fpt) algorithm for Colored Hypergraph Isomorphism} which has running time $2^{O(b)}N^{O(1)}$, where the parameter $b$ is the maximum size of the color classes of the given hypergraphs and $N$ is the input size. We also describe fpt algorithms for certain permutation group problems that are used as subroutines in our algorithm.
Cite as

V. Arvind, Bireswar Das, Johannes Köbler, and Seinosuke Toda. Colored Hypergraph Isomorphism is Fixed Parameter Tractable. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 327-337, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.FSTTCS.2010.327,
  author =	{Arvind, V. and Das, Bireswar and K\"{o}bler, Johannes and Toda, Seinosuke},
  title =	{{Colored Hypergraph Isomorphism is Fixed Parameter Tractable}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
  pages =	{327--337},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.327},
  URN =		{urn:nbn:de:0030-drops-28751},
  doi =		{10.4230/LIPIcs.FSTTCS.2010.327},
  annote =	{Keywords: Fixed parameter tractability, fpt algorithms, graph isomorphism, computational complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2456
Log-space Algorithms for Paths and Matchings in k-trees

Authors: Bireswar Das, Samir Datta, and Prajakta Nimbhorkar

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

Abstract
Reachability and shortest path problems are \NLC\ for general graphs. They are known to be in \Log\ for graphs of tree-width $2$ \cite{JT07}. However, for graphs of tree-width larger than $2$, no bound better than \NL\ is known. In this paper, we improve these bounds for $k$-trees, where $k$ is a constant. In particular, the main results of our paper are log-space algorithms for reachability in directed $k$-trees, and for computation of shortest and longest paths in directed acyclic $k$-trees. Besides the path problems mentioned above, we consider the problem of deciding whether a $k$-tree has a perfect macthing (decision version), and if so, finding a perfect matching (search version), and prove that these problems are \Log-complete. These problems are known to be in \Ptime\ and in \RNC\ for general graphs, and in \SPL\ for planar bipartite graphs \cite{DKR08}. Our results settle the complexity of these problems for the class of $k$-trees. The results are also applicable for bounded tree-width graphs, when a tree-decomposition is given as input. The technique central to our algorithms is a careful implementation of divide-and-conquer approach in log-space, along with some ideas from \cite{JT07} and \cite{LMR07}.
Cite as

Bireswar Das, Samir Datta, and Prajakta Nimbhorkar. Log-space Algorithms for Paths and Matchings in k-trees. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 215-226, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.STACS.2010.2456,
  author =	{Das, Bireswar and Datta, Samir and Nimbhorkar, Prajakta},
  title =	{{Log-space Algorithms for Paths and Matchings in k-trees}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{215--226},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2456},
  URN =		{urn:nbn:de:0030-drops-24563},
  doi =		{10.4230/LIPIcs.STACS.2010.2456},
  annote =	{Keywords: k-trees, reachability, matching, log-space}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2457
Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs

Authors: Bireswar Das, Jacobo Torán, and Fabian Wagner

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

Abstract
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}
Cite as

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.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}
}
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 About DROPS Imprint Privacy Contact