Myhill-Nerode Methods for Hypergraphs

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

    Research output: Contribution to journalArticleResearchpeer-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

    Hypergraph
    Formal languages
    Treewidth
    Computational complexity
    Incidence
    Parameterized Complexity
    Complexity Theory
    Testing
    Hypertree
    Monadic Second-order Logic
    Formal Languages
    Linear-time Algorithm
    Theorem
    Linear Time
    Fractional
    NP-complete problem
    Analogue
    Graph in graph theory

    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
    Van Bevern, Rene ; Downey, Rod ; Fellows, Michael ; Gaspers, Serge ; Rosamond, Frances. / Myhill-Nerode Methods for Hypergraphs. In: Algorithmica. 2015 ; Vol. 73, No. 4. pp. 696-729.
    @article{ad6f48a404924f459a3d8572ae85c512,
    title = "Myhill-Nerode Methods for Hypergraphs",
    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.",
    keywords = "Algorithms, Automata theory, Clustering algorithms, Computational complexity, Formal languages, Formal logic, Parameterization, Polynomials, Cutwidths, Fixed-parameter algorithms, Formal language theory, Hypergraph problem, Hypertree width, Linear-time algorithms, Monadic second-order logic, Parameterized complexity, Graph theory",
    author = "{Van Bevern}, Rene and Rod Downey and Michael Fellows and Serge Gaspers and Frances Rosamond",
    year = "2015",
    month = "12",
    doi = "10.1007/s00453-015-9977-x",
    language = "English",
    volume = "73",
    pages = "696--729",
    journal = "Algorithmica",
    issn = "0178-4617",
    publisher = "Springer",
    number = "4",

    }

    Van Bevern, R, Downey, R, Fellows, M, Gaspers, S & Rosamond, F 2015, 'Myhill-Nerode Methods for Hypergraphs', 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.

    In: Algorithmica, Vol. 73, No. 4, 12.2015, p. 696-729.

    Research output: Contribution to journalArticleResearchpeer-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 -

    Van Bevern R, Downey R, Fellows M, Gaspers S, Rosamond F. Myhill-Nerode Methods for Hypergraphs. Algorithmica. 2015 Dec;73(4):696-729. https://doi.org/10.1007/s00453-015-9977-x