Browsing by Author "Kumar, Anant"

For an arbitrary, fixed graph (pattern graph), we study the algorithmic complexity of counting homomorphisms, subgraph isomorphisms, and induced subgraph isomorphisms from the pattern graph to -vertex, -degenerate graphs as input. Recent work by Bressan (Algorithmica, 2021) has shown that this problem has efficient dynamic programming algorithms using a graph parameter called DAG treewidth. Bressan used DAG treewidth to design a fast algorithm for counting homomorphisms, subgraph isomorphisms, and induced subgraph isomorphisms that use polynomial space. Bera, Gishboliner, Levanzov, Seshadhri, and Shapira (SODA, 2021) provided a characterization of graphs with DAG treewidth one. In this paper, we introduce a new graph parameter called DAG treedepth and show that it yields efficient divide and conquer algorithms that use only constant space (in the unit-cost RAM model). Specifically, we show: An algorithm for counting subgraphs isomorphic to sparse pattern graphs using only constant space. We derive an induced minor-based characterization for graphs of DAG treedepth up to two. For pattern graphs upto nine vertices, the induced subgraphs can be counted in time using constant space. An algorithm for counting induced subgraphs that matches the running time given by Bressan but only uses constant space. Apart from the DAG treedepth result, we also focus on DAG treewidth. For DAG treewidth, we show that we can count homomorphisms, subgraph isomorphisms, and induced subgraph isomorphisms faster than Bressan's algorithm (2021). We further show that for all pattern graphs up to 11 vertices, we can count induced subgraphs in quadratic time.

We consider algorithms for finding and counting small, fixed graphs in sparse host graphs. In the non-sparse setting, the parameters treedepth and treewidth play a crucial role in fast, constant-space and polynomial-space algorithms respectively. We discover two new parameters that we call matched treedepth and matched treewidth. We show that finding and counting patterns with low matched treedepth and low matched treewidth can be done asymptotically faster than the existing algorithms when the host graphs are sparse for many patterns. As an application to finding and counting fixed-size patterns, we discover O^͠ (m³)-time¹, constant-space algorithms for cycles of length at most 11 and O͠ (m²)-time, polynomial-space algorithms for paths of length at most 10.

We consider algorithms for finding and counting small, fixed graphs in sparse host graphs. In the non-sparse setting, the parameters treedepth and treewidth play a crucial role in fast, constant-space and polynomial-space algorithms respectively. We discover two new parameters that we call matched treedepth and matched treewidth. We show that finding and counting patterns with low matched treedepth and low matched treewidth can be done asymptotically faster than the existing algorithms when the host graphs are sparse for many patterns. As an application to finding and counting fixed-size patterns, we discover Oe(m3)-time 1, constant-space algorithms for cycles of length at most 11 and Oe(m2)-time, polynomial-space algorithms for paths of length at most 10.

We consider algorithms for finding and counting small, fixed graphs in sparse host graphs. In the non-sparse setting, the parameters treedepth and treewidth play a crucial role in fast, constant-space and polynomial-space algorithms respectively. We discover two new parameters that we call matched treedepth and matched treewidth. We show that, for many patterns, finding and counting patterns with low matched treedepth and low matched treewidth can be done asymptotically faster than the existing algorithms when the host graphs are sparse. As an application to finding and counting fixed-size patterns, we discover O˜(m³)-time.¹ constant-space algorithms for graphs on at most 11 edges and O˜(m²)-time, polynomial-space algorithms for graphs on at most 9 edges.²

In this paper, we propose localized versions of Weisfeiler-Leman (WL) algorithms in an effort to both increase the expressivity, as well as decrease the computational overhead. We focus on the specific problem of subgraph counting and give localized versions of k-WL for any k. We analyze the power of Local k-WL and prove that it is more expressive than k-WL and at most as expressive as (k+1)-WL. We give a characterization of patterns whose count as a subgraph and induced subgraph are invariant if two graphs are Local k-WL equivalent. We also introduce two variants of k-WL: Layer k-WL and recursive k-WL. These methods are more time and space efficient than applying k-WL on the whole graph. We also propose a fragmentation technique that guarantees the exact count of all induced subgraphs of size at most 4 using just 1-WL. The same idea can be extended further for larger patterns using k>1. We also compare the expressive power of Local k-WL with other GNN hierarchies and show that given a bound on the time-complexity, our methods are more expressive than the ones mentioned in Papp and Wattenhofer[2022a].

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. Das et al. (J Comput Syst Sci 114:137–146, 2020) showed that for any finite group G of order n and for any δ∈[1/logn,1], a data structure can be constructed for G that uses O(n^1+δ/δ) space and answers a multiplication query in time O(1/δ). 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. 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. Since our data structure achieves the information theoretic 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 nonabelian simple groups are designed using a lemma that we prove using the Classification Theorem for Finite Simple Groups.

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).

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.

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.