Alladi Ramakrishnan Hall

Dynamic Programming using Representative Families

Fahad Panolan

IMSc

Let M=(E,I) be a matroid and let ${\cal S}=\{S_1, \dots, S_t\}$ be a family of subsets of $E$ of size $p$. A subfamily $\widehat{\cal{S}}\subseteq \cal S$ is {\em $q$-representative} for $\cal S$ if for every set $Y\subseteq E$ of size at most $q$, if there is a set $X \in \cal S$ disjoint from $Y$ with $X\cup Y \in \I$, then there is a set $\widehat{X} \in \widehat{\cal S}$ disjoint from $Y$ with $\widehat{X} \cup Y \in \I$. By the classical result of Bollob{\'a}s, in a uniform matroid, every family of sets of size $p$ has a $q$-representative family with at most $\binom{p+q}{p}$ sets. In his famous ``two families theorem'' from 1977, Lov{\'a}sz proved that the same bound also holds for any matroid representable over a field $ \mathbb{F}$. As observed by Marx, Lov{\'a}sz's proof is constructive. In this thesis we show how Lov{\'a}sz's proof can be turned into an algorithm constructing a $q$-representative family of size at most $\binom{p+q}{p}$ in time bounded by a polynomial in $\binom{p+q}{p}$, $t$, and the time required for field operations.

We demonstrate how the efficient construction of representative families can be a powerful tool for designing single-exponential parameterized and exact exponential time algorithms. The applications of our approach include fastest known parameterized (and exact) algorithms for \textsc{Long Directed Cycle}, \textsc{Minimum Equivalent Graph}, ``connectivity'' problems such as \textsc{Hamiltonian Cycle} or \textsc{Steiner Tree} on graphs of
treewidth at most $t$ and {\sc Monomial Testing}. We also use the methods to resolve parameterized complexity of graph editing problems. Our other results in the thesis include algorithms for Matroid Girth and Matroid Connectivity. Finally, we give the first single exponential time polynomial space algorithm for {\sc Steiner Tree} running in time $(4+\epsilon)^{k}n^{O(1)}$. Here, $n$ represents the number of vertices in the input graph and $k$ is the size of the terminal set.

(This is a PhD defense)