Ran Ben-Basat, M.Sc. Thesis Seminar
Parameterization is a useful tool for handling NP-hard problems in the
real world. It aims to reduce the running times of algorithms for such
problems, by confining the combinatorial explosion to some parameter k. As
this parameter is often significantly smaller than the input size, it
allows to develop practical algorithms for non-trivial classes of
instances for these problems.
In this talk we present a novel framework for developing parameterized
algorithms, using constructions of automata for the corresponding languages.
Our automata-based framework gives a different view of the parameterized
versions of several classic problems, including Traveling Salesman and
3D-Matching. We show that many of the previously used techniques for
solving these problems imply automata constructions for some implicitly
related regular languages. We use automata tools also to infer lower
bounds for these techniques.
Finally, we note that our framework allows clean and simple design of
algorithms for a family of problems, where the design of a single automaton
for a specific problem yields deterministic, randomized and approximate
witness counting algorithms for the problem.