We study algorithms to detect induced G-subgraphs, for fixed patterns G, given host graphs with n vertices and m edges as input. We show that: 1) There are at least five 5-vertex connected graphs G (out of 21) that can be detected in O(nm)-time. 2)There are at least sixty-five 6-vertex connected graphs G (out of 112) that can be detected in O(m^2)-time. 3)The graphs P_7 and C_7 can be detected in O(nm^2)-time.
Our main technical tool is a generalized notion of the width of tree decompositions that we call $(p, q)$-width tree decompositions. We use (p, q)-width tree decompositions to derive algorithms with running-time O(n^pm^q) for detecting induced subgraphs. Our upper bounds are never worse than existing upper bounds and are faster when m = o(n^2). Moreover, for some patterns, such as C_7, our algorithms are optimal under standard complexity-theoretic assumptions.
The new technique we use to obtain fast algorithms for fixed-pattern graphs is not scalable to families of pattern graphs. We further refine this idea by constructing pattern-based polynomials that exploit the structure of the tree decomposition, and not just its width, to obtain algorithms for larger classes of graphs. We show: 1) An O(m^{k-1})-time algorithm for detecting induced P_{2k} in bipartite graphs. 2) An O(nm^{k-1})-time algorithm for detecting induced C_{2k} in bipartite graphs. These algorithms improve the best-known upper bounds for general graphs.
Many classes of graphs can be defined by what is missing. In this talk, we will explore this theme of Forbidden Structures and see snapshots of some landmark results in Graph Colouring. This is an overview intended for students of all levels.
We are given an undirected weighted graph G with n vertices and m edges, edge weights in [1, W], and a designated source vertex s. We design a single-source dual fault-tolerant distance oracle for G. Given a destination vertex t and a set F of at most two faulty edges, the oracle returns a (1 + O(ε))-approximation of the weight of the shortest path from the source s to t avoiding F. Our oracle uses Õ(n√n) space and has Õ(1) query time. Prior to our result, single-source single-fault-tolerant oracles were known to return a (1 + ε)-approximation of the weight of the shortest path using Õ(n) space and O(1) query time. However, extending these approaches to multiple faults remained an open problem. Indeed, all (1 + ε)-approximate distance oracles that handle multiple faults require Ω(n²) space. We break this bound by presenting the first dual fault-tolerant distance oracle with o(n²) space.
This work is a collaboration with Prof. Manoj Gupta and has been accepted at ESA 2026.