Search

In this paper, we study the oriented diameter of power graphs of groups. We show that a $2$-edge connected power graph of a finite group has oriented diameter at most $4$. We prove that the power graph of a cyclic group of order $n$ has oriented diameter $2$ for all $n\neq 2,4,6$. Until our work, to the best of our knowledge, no infinite family of graphs with oriented diameter 2 had been identified except for subclasses of complete graphs. Finally, we give a complete characterization of the oriented diameter of the power graphs of nilpotent groups. This, in turn, gives an algorithm for computing the oriented diameter of the power graph of a given nilpotent group that runs in time polynomial in the size of the group., Comment: 24 pages

The isomorphism problem for graphs (GI) and the isomorphism problem for groups (GrISO) have been studied extensively by researchers. The current best algorithms for both these problems run in quasipolynomial time. In this paper, we study the isomorphism problem of graphs that are defined in terms of groups, namely power graphs, directed power graphs, and enhanced power graphs. It is not enough to check the isomorphism of the underlying groups to solve the isomorphism problem of such graphs as the power graphs (or the directed power graphs or the enhanced power graphs) of two nonisomorphic groups can be isomorphic. Nevertheless, it is interesting to ask if the underlying group structure can be exploited to design better isomorphism algorithms for these 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. We note that our algorithm does not require the underlying groups of the input graphs to be given. The isomorphism problems of power graphs and enhanced power graphs are solved by first computing the directed power graphs from the input graphs. The problem of efficiently computing the directed power graph from the power graph or the enhanced power graph is due to Cameron [IJGT'22]. Therefore, we give a solution to Cameron's question., Comment: 27 pages

For a finite group $G$, the size of a minimum generating set of $G$ is denoted by $d(G)$. Given a finite group $G$ and an integer $k$, deciding if $d(G)\leq k$ is known as the minimum generating set (MIN-GEN) problem. A group $G$ of order $n$ has generating set of size $\lceil \log_p n \rceil$ where $p$ is the smallest prime dividing $n=|G|$. This fact is used to design an $n^{\log_p n+O(1)}$-time algorithm for the group isomorphism problem of groups specified by their Cayley tables (attributed to Tarjan by Miller, 1978). The same fact can be used to give an $n^{\log_p n+O(1)}$-time algorithm for the MIN-GEN problem. We show that the MIN-GEN problem can be solved in time $n^{(1/4)\log_p n+O(1)}$ for general groups given by their Cayley tables. This runtime incidentally matches with the runtime of the best known algorithm for the group isomorphism problem. We show that if a group $G$, given by its Cayley table, is the product of simple groups then a minimum generating set of $G$ can be computed in time polynomial in $|G|$. Given groups $G_i$ along with $d(G_i)$ for $i\in [r]$ the problem of computing $d(\Pi_{i\in[r]} G_i)$ is nontrivial. As a consequence of our result for products of simple groups we show that this problem also can be solved in polynomial time for Cayley table representation. For the MIN-GEN problem for permutation groups, to the best of our knowledge, no significantly better algorithm than the brute force algorithm is known. For an input group $G\leq S_n$, the brute force algorithm runs in time $|G|^{O(n)}$ which can be $2^{\Omega(n^2)}$. We show that if $G\leq S_n$ is a primitive permutation group then the MIN-GEN problem can be solved in time quasi-polynomial in $n$. We also design a $\mathrm{DTIME}(2^n)$ algorithm for computing a minimum generating set of permutation groups all of whose non-abelian chief factors have bounded orders., Comment: 20 pages

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^2)$ 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^2)$ 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 $\Omega(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)., Comment: A preliminary version of this article appeared in the pro- ceedings of the 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

The Cayley table representation of a group uses $\mathcal{O}(n^2)$ words for a group of order $n$ and answers multiplication queries in time $\mathcal{O}(1)$. It is interesting to ask if there is a $o(n^2)$ space representation of groups that still has $\mathcal{O}(1)$ query-time. We show that for any $\delta$, $\frac{1}{\log n} \le \delta \le 1$, there is an $\mathcal{O}(\frac{n^{1 +\delta}}{\delta})$ space representation for groups of order $n$ with $\mathcal{O}(\frac{1}{\delta})$ query-time. We also show that for Z-groups, simple groups and several group classes defined in terms of semidirect product, there are linear space representations with at most logarithmic query-time. Farzan and Munro (ISSAC'06) defined a model for group representation and gave a succinct data structure for abelian groups with constant query-time. They asked if their result can be extended to categorically larger group classes. We construct data structures in their model for Hamiltonian groups and some other classes of groups with constant query-time.

The Firefighting problem is defined as follows. At time $t=0$, a fire breaks out at a vertex of a graph. At each time step $t \geq 0$, a firefighter permanently defends (protects) an unburned vertex, and the fire then spread to all undefended neighbors from the vertices on fire. This process stops when the fire cannot spread anymore. The goal is to find a sequence of vertices for the firefighter that maximizes the number of saved (non burned) vertices. The Firefighting problem turns out to be NP-hard even when restricted to bipartite graphs or trees of maximum degree three. We study the parameterized complexity of the Firefighting problem for various structural parameterizations. All our parameters measure the distance to a graph class (in terms of vertex deletion) on which the firefighting problem admits a polynomial time algorithm. Specifically, for a graph class $\mathcal{F}$ and a graph $G$, a vertex subset $S$ is called a modulator to $\mathcal{F}$ if $G \setminus S$ belongs to $\mathcal{F}$. The parameters we consider are the sizes of modulators to graph classes such as threshold graphs, bounded diameter graphs, disjoint unions of stars, and split graphs. To begin with, we show that the problem is W[1]-hard when parameterized by the size of a modulator to diameter at most two graphs and split graphs. In contrast to the above intractability results, we show that Firefighting is fixed parameter tractable (FPT) when parameterized by the size of a modulator to threshold graphs and disjoint unions of stars, which are subclasses of diameter at most two graphs. We further investigate the kernelization complexity of these problems to find that firefighting admits a polynomial kernel when parameterized by the size of a modulator to a clique, while it is unlikely to admit a polynomial kernel when parameterized by the size of a modulator to a disjoint union of stars., Comment: 19 pages, To be appeared in CALDAM 2018

In this paper, we study the parallel and the space complexity of the graph isomorphism problem (\GI{}) for several parameterizations. Let $\mathcal{H}=\{H_1,H_2,\cdots,H_l\}$ be a finite set of graphs where $|V(H_i)|\leq d$ for all $i$ and for some constant $d$. Let $\mathcal{G}$ be an $\mathcal{H}$-free graph class i.e., none of the graphs $G\in \mathcal{G}$ contain any $H \in \mathcal{H}$ as an induced subgraph. We show that \GI{} parameterized by vertex deletion distance to $\mathcal{G}$ is in a parameterized version of $\AC^1$, denoted $\PL$-$\AC^1$, provided the colored graph isomorphism problem for graphs in $\mathcal{G}$ is in $\AC^1$. From this, we deduce that \GI{} parameterized by the vertex deletion distance to cographs is in $\PL$-$\AC^1$. The parallel parameterized complexity of \GI{} parameterized by the size of a feedback vertex set remains an open problem. Towards this direction we show that the graph isomorphism problem is in $\PL$-$\TC^0$ when parameterized by vertex cover or by twin-cover. Let $\mathcal{G}'$ be a graph class such that recognizing graphs from $\mathcal{G}'$ and the colored version of \GI{} for $\mathcal{G}'$ is in logspace ($\L$). We show that \GI{} for bounded vertex deletion distance to $\mathcal{G}'$ is in $\L$. From this, we obtain logspace algorithms for \GI{} for graphs with bounded vertex deletion distance to interval graphs and graphs with bounded vertex deletion distance to cographs.

The clique-width is a measure of complexity of decomposing graphs into certain tree-like structures. The class of graphs with bounded clique-width contains bounded tree-width graphs. We give a polynomial time graph isomorphism algorithm for graphs with clique-width at most three. Our work is independent of the work by Grohe et al. \cite{grohe2015isomorphism} showing that the isomorphism problem for graphs of bounded clique-width is polynomial time.

In this paper, we prove that most of the boolean functions, $f : \{-1,1\}^n \rightarrow \{-1,1\}$ satisfy the Fourier Entropy Influence (FEI) Conjecture due to Friedgut and Kalai (Proc. AMS'96). The conjecture says that the Entropy of a boolean function is at most a constant times the Influence of the function. The conjecture has been proven for families of functions of smaller sizes. O'donnell, Wright and Zhou (ICALP'11) verified the conjecture for the family of symmetric functions, whose size is $2^{n+1}$. They are in fact able to prove the conjecture for the family of $d$-part symmetric functions for constant $d$, the size of whose is $2^{O(n^d)}$. Also it is known that the conjecture is true for a large fraction of polynomial sized DNFs (COLT'10). Using elementary methods we prove that a random function with high probability satisfies the conjecture with the constant as $(2 + \delta)$, for any constant $\delta > 0$., Comment: We thank Kunal Dutta and Justin Salez for pointing out that our result can be extended to a high probability statement

The Graph Isomorphism problem restricted to graphs of bounded treewidth or bounded tree distance width are known to be solvable in polynomial time [Bod90],[YBFT99]. We give restricted space algorithms for these problems proving the following results: - Isomorphism for bounded tree distance width graphs is in L and thus complete for the class. We also show that for this kind of graphs a canon can be computed within logspace. - 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 L. - For bounded treewidth graphs, when one of the input graphs is given with a tree decomposition the isomorphism problem is in LogCFL. - As a corollary the isomorphism problem for bounded treewidth graphs is in LogCFL. This improves the known TC1 upper bound for the problem given by Grohe and Verbitsky [GroVer06]., Comment: STACS conference 2010, 12 pages

Reachability and shortest path problems are NL-complete for general graphs. They are known to be in L for graphs of tree-width 2 [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 also consider the problem of deciding whether a k-tree has a perfect macthing (decision version), and if so, finding a perfect match- ing (search version), and prove that these two problems are L-complete. These problems are known to be in P and in RNC for general graphs, and in SPL for planar bipartite graphs [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 [JT07] and [LMR07]., Comment: Accepted in STACS 2010