### Abstract

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.Original language | English |
---|---|

Pages (from-to) | 696-729 |

Number of pages | 34 |

Journal | Algorithmica |

Volume | 73 |

Issue number | 4 |

DOIs | |

Publication status | Published - Dec 2015 |

## Fingerprint Dive into the research topics of 'Myhill-Nerode Methods for Hypergraphs'. Together they form a unique fingerprint.

## Cite this

Van Bevern, R., Downey, R., Fellows, M., Gaspers, S., & Rosamond, F. (2015). Myhill-Nerode Methods for Hypergraphs.

*Algorithmica*,*73*(4), 696-729. https://doi.org/10.1007/s00453-015-9977-x