## 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.*