RenĂ© van Bevern, Michael R. Fellows, Serge Gaspers, and Frances A. Rosamond. Myhill-nerode methods for hypergraphs. In Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC'13), Hong Kong, China, volume 8283 of Lecture Notes in Computer Science, pages 372–382. Springer, 2013. The final version of this article appeared in the ISAAC'13 special issue of Algorithmica.

We introduce a method of applying Myhill-Nerode methods from formal language theory to hypergraphs and show how this method can be used to obtain the following parameterized complexity results. Hypergraph Cutwidth (deciding whether a hypergraph on n vertices has cutwidth at most k) is linear-time solvable for constant k. For hypergraphs of constant incidence treewidth (treewidth of the incidence graph), Hypertree Width and variants cannot be solved by simple finite tree automata. The proof leads us to conjecture that Hypertree Width is W[1]-hard for this parameter.

bib | DOI | slides | journal version ] Back

This file was generated by bibtex2html 1.98.