Showing cs.DSShow all
3 papers · 1 filter
cs.DS2025
Counting Patterns in Degenerate Graphs in Constant Space
Balagopal Komarath, Anant Kumar, Akash Pareek
For a fixed pattern graph, we study the algorithmic complexity of counting homomorphisms, subgraph isomorphisms, and induced subgraph isomorphisms into an -vertex, -degenerat…
cs.DS2023
The Isomorphism Problem of Power Graphs and a Question of Cameron
Bireswar Das, Jinia Ghosh, Anant Kumar
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 prob…
cs.DS2023
Finding and Counting Patterns in Sparse Graphs
Balagopal Komarath, Anant Kumar, Suchismita Mishra +1
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…