Myhill-Nerode Methods for Hypergraphs

Rene Van Bevern, Rod Downey, Michael Fellows, Serge Gaspers, Frances Rosamond

    Research output: Contribution to journalArticle

    12 Downloads (Pure)

    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 languageEnglish
    Pages (from-to)696-729
    Number of pages34
    JournalAlgorithmica
    Volume73
    Issue number4
    DOIs
    Publication statusPublished - 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