### Abstract

*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

### Cite this

*Algorithmica*,

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

}

*Algorithmica*, vol. 73, no. 4, pp. 696-729. https://doi.org/10.1007/s00453-015-9977-x

**Myhill-Nerode Methods for Hypergraphs.** / Van Bevern, Rene; Downey, Rod; Fellows, Michael; Gaspers, Serge; Rosamond, Frances.

Research output: Contribution to journal › Article › Research › peer-review

TY - JOUR

T1 - Myhill-Nerode Methods for Hypergraphs

AU - Van Bevern, Rene

AU - Downey, Rod

AU - Fellows, Michael

AU - Gaspers, Serge

AU - Rosamond, Frances

PY - 2015/12

Y1 - 2015/12

N2 - 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.

AB - 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.

KW - Algorithms

KW - Automata theory

KW - Clustering algorithms

KW - Computational complexity

KW - Formal languages

KW - Formal logic

KW - Parameterization

KW - Polynomials

KW - Cutwidths

KW - Fixed-parameter algorithms

KW - Formal language theory

KW - Hypergraph problem

KW - Hypertree width

KW - Linear-time algorithms

KW - Monadic second-order logic

KW - Parameterized complexity

KW - Graph theory

U2 - 10.1007/s00453-015-9977-x

DO - 10.1007/s00453-015-9977-x

M3 - Article

VL - 73

SP - 696

EP - 729

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 4

ER -