The Taub Faculty of Computer Science Events and Talks

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.