4 papers
Graph Homomorphism Polynomials: Algorithms and Complexity
Balagopal Komarath, Anurag Pandey, C. S. Rahul
We study homomorphism polynomials, which are polynomials that enumerate all homomorphisms from a pattern graph to -vertex graphs. These polynomials have received a lot of at…
On the complexity of detecting hazards
Balagopal Komarath, Nitin Saurabh
Detecting and eliminating logic hazards in Boolean circuits is a fundamental problem in logic circuit design. We show that there is no time algorithm…
Graph Pattern Polynomials
Markus Bläser, Balagopal Komarath, Karteek Sreenivasaiah
We study the time complexity of induced subgraph isomorphism problems where the pattern graph is fixed. The earliest known example of an improvement over trivial algorithms is by I…
Pebbling Meets Coloring: Reversible Pebble Game On Trees
Balagopal Komarath, Jayalal Sarma, Saurabh Sawlani
The reversible pebble game is a combinatorial game played on rooted DAGs. This game was introduced by Bennett (1989) motivated by applications in designing space efficient reversib…