I work in theoretical computer science, especially graph theory, parameterized algorithms, and automata theory. A common theme in my work is obtaining exact structural characterizations, such as tractability and hardness thresholds for discrete problems and accepting-state spectra for automata operations.
I also care about teaching and mathematical exposition; I served for a year on the course staff for UC Berkeley’s CS 70, Discrete Mathematics and Probability Theory, first as an academic intern and then as a tutor.
The Path-Extremal Conjecture for Zero Forcing: Distance-Hereditary Graphs and a Split-Decomposition Reduction
Proves the zero-forcing path-extremal conjecture for distance-hereditary graphs and additionally uses canonical split decomposition to reduce the conjecture on an infinite class of graphs -- those with a unique prime bag of bounded size -- to finitely many checks on bounded-order split-prime cores.
Strong Conflict-Free Vertex-Connection via Twin Cover: Kernelization and Chromatic Bounds
Gives a kernel for deciding whether the strong conflict-free vertex-connection number of \(G\) is at most \(k\), parameterized by the twin-cover number of \(G\) and the target number of colors \(k\). It also proves that for a twin cover \(X\), the strong conflict-free vertex-connection number lies between the chromatic number \(\chi(G)\) and \(\chi(G)+|X|\), and derives an exact formula for \(\chi(G)\) in terms of colorings of \(G[X]\).
Layer-Based Width for PAFP
Introduces layer-based width parameters for the Path Avoiding Forbidden Pairs problem via both the union digraph \(G \cup \mathcal{F}\) and the input graph \(G\), and proves a sharp union-digraph contrast: bounded union BFS-width together with bounded backward arcs yields an FPT algorithm, whereas bounded union BFS-width alone remains \(\mathsf{NP}\text{-}\)hard already at width \(2\). On the input-graph side, it gives the first tractability regimes for PAFP with unrestricted forbidden pairs, including FPT for BFS-width \(2\) with bounded backward input arcs and polynomial time for exact-length width \(2\), both of which results, the paper shows, are tight against width-\(3\) hardness.
1 The difference between the arXiv version and the version identified by the DOI is that the former contains the two bounded backward arcs results in the above paper description, whereas the latter doesn't. My other papers featured here contain no substative differences between their arXiv and DOI versions.