Myhill-Nerode Methods for Hypergraphs

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

    Research output: Contribution to journalArticlepeer-review

    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