## 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 that runs in linear time for constant In terms of parameterized complexity theory, the problem is fixed-parameter linear parameterized by(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 - 1 Dec 2015 |

Externally published | Yes |

## Keywords

- Automata theory
- Cutwidth
- Fixed-parameter algorithms
- Hypertree width
- NP-hard problems