## René van Bevern, Rodney G. Downey, Michael R. Fellows, Serge Gaspers, and
Frances A. Rosamond.
Myhill-nerode methods for hypergraphs.
*Algorithmica*, 73(4):696–729, 2015.
ISAAC'13 special issue.

We give an analog of the Myhill–Nerode theorem from
formal language theory for hypergraphs and use it to
derive the following results for two NP-hard
hypergraph problems. (1) We provide an algorithm for
testing whether a hypergraph has cutwidth at most k
that runs in linear time for constant k. In terms of
parameterized complexity theory, the problem is
fixed-parameter linear parameterized by k. (2) We show
that it is not expressible in monadic second-order
logic whether a hypergraph has bounded (fractional,
generalized) hypertree width. The proof leads us to
conjecture that, in terms of parameterized complexity
theory, these problems are W[1]-hard parameterized by
the incidence treewidth (the treewidth of the
incidence graph). Thus, in the form of the
Myhill–Nerode theorem for hypergraphs, we obtain a
method to derive linear-time algorithms and to obtain
indicators for intractability for hypergraph problems
parameterized by incidence treewidth.

[ bib |
DOI |
slides |
http ]
Back

*This file was generated by
bibtex2html 1.98.*