Myhill-Nerode Methods for Hypergraphs

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

    Research output: Chapter in Book/Report/Conference proceedingConference Paper published in ProceedingsResearchpeer-review

    Abstract

    We introduce a method of applying Myhill-Nerode methods from formal language theory to hypergraphs and show how this method can be used to obtain the following parameterized complexity results. - Hypergraph Cutwidth (deciding whether a hypergraph on n vertices has cutwidth at most k) is linear-time solvable for constant k. - For hypergraphs of constant incidence treewidth (treewidth of the incidence graph), Hypertree Width and variants cannot be solved by simple finite tree automata. The proof leads us to conjecture that Hypertree Width is W[1]-hard for this parameter.
    Original languageEnglish
    Title of host publicationAlgorithms and Computation
    Subtitle of host publication24th International Symposium, ISAAC 2013 Hong Kong, China, December 16-18, 2013 Proceedings
    EditorsLeizhen Cai, Sui-Wing Cheng, Tak-Wah Lam
    Place of PublicationGermany
    PublisherSpringer
    Pages372-382
    Number of pages11
    ISBN (Print)978-3-642-45029-7
    DOIs
    Publication statusPublished - 2013
    Event24th International Symposium, ISAAC 2013 - Hong Kong, China
    Duration: 16 Dec 201318 Dec 2013

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer
    Volume8283
    ISSN (Print)0302-9743

    Conference

    Conference24th International Symposium, ISAAC 2013
    Period16/12/1318/12/13

    Fingerprint

    Hypergraph
    Hypertree
    Treewidth
    Incidence
    Tree Automata
    Parameterized Complexity
    Formal Languages
    Finite Automata
    Linear Time
    Graph in graph theory

    Cite this

    Van Bevern, R., Fellows, M., Gaspers, S., & Rosamond, F. (2013). Myhill-Nerode Methods for Hypergraphs. In L. Cai, S-W. Cheng, & T-W. Lam (Eds.), Algorithms and Computation: 24th International Symposium, ISAAC 2013 Hong Kong, China, December 16-18, 2013 Proceedings (pp. 372-382). (Lecture Notes in Computer Science ; Vol. 8283). Germany: Springer. https://doi.org/10.1007/978-3-642-45030-3_35
    Van Bevern, Rene ; Fellows, Michael ; Gaspers, Serge ; Rosamond, Frances. / Myhill-Nerode Methods for Hypergraphs. Algorithms and Computation: 24th International Symposium, ISAAC 2013 Hong Kong, China, December 16-18, 2013 Proceedings. editor / Leizhen Cai ; Sui-Wing Cheng ; Tak-Wah Lam. Germany : Springer, 2013. pp. 372-382 (Lecture Notes in Computer Science ).
    @inproceedings{d8ac065de68f4749a53dd8c71b76d1f9,
    title = "Myhill-Nerode Methods for Hypergraphs",
    abstract = "We introduce a method of applying Myhill-Nerode methods from formal language theory to hypergraphs and show how this method can be used to obtain the following parameterized complexity results. - Hypergraph Cutwidth (deciding whether a hypergraph on n vertices has cutwidth at most k) is linear-time solvable for constant k. - For hypergraphs of constant incidence treewidth (treewidth of the incidence graph), Hypertree Width and variants cannot be solved by simple finite tree automata. The proof leads us to conjecture that Hypertree Width is W[1]-hard for this parameter.",
    keywords = "Cutwidths, Finite tree automaton, Formal language theory, Hyper graph, Incidence graphs, Linear-time, Parameterized complexity, Tree-width, Algorithms, Automata theory, Formal languages, Graph theory",
    author = "{Van Bevern}, Rene and Michael Fellows and Serge Gaspers and Frances Rosamond",
    year = "2013",
    doi = "10.1007/978-3-642-45030-3_35",
    language = "English",
    isbn = "978-3-642-45029-7",
    series = "Lecture Notes in Computer Science",
    publisher = "Springer",
    pages = "372--382",
    editor = "Leizhen Cai and Sui-Wing Cheng and Tak-Wah Lam",
    booktitle = "Algorithms and Computation",
    address = "Switzerland",

    }

    Van Bevern, R, Fellows, M, Gaspers, S & Rosamond, F 2013, Myhill-Nerode Methods for Hypergraphs. in L Cai, S-W Cheng & T-W Lam (eds), Algorithms and Computation: 24th International Symposium, ISAAC 2013 Hong Kong, China, December 16-18, 2013 Proceedings. Lecture Notes in Computer Science , vol. 8283, Springer, Germany, pp. 372-382, 24th International Symposium, ISAAC 2013, 16/12/13. https://doi.org/10.1007/978-3-642-45030-3_35

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

    Algorithms and Computation: 24th International Symposium, ISAAC 2013 Hong Kong, China, December 16-18, 2013 Proceedings. ed. / Leizhen Cai; Sui-Wing Cheng; Tak-Wah Lam. Germany : Springer, 2013. p. 372-382 (Lecture Notes in Computer Science ; Vol. 8283).

    Research output: Chapter in Book/Report/Conference proceedingConference Paper published in ProceedingsResearchpeer-review

    TY - GEN

    T1 - Myhill-Nerode Methods for Hypergraphs

    AU - Van Bevern, Rene

    AU - Fellows, Michael

    AU - Gaspers, Serge

    AU - Rosamond, Frances

    PY - 2013

    Y1 - 2013

    N2 - We introduce a method of applying Myhill-Nerode methods from formal language theory to hypergraphs and show how this method can be used to obtain the following parameterized complexity results. - Hypergraph Cutwidth (deciding whether a hypergraph on n vertices has cutwidth at most k) is linear-time solvable for constant k. - For hypergraphs of constant incidence treewidth (treewidth of the incidence graph), Hypertree Width and variants cannot be solved by simple finite tree automata. The proof leads us to conjecture that Hypertree Width is W[1]-hard for this parameter.

    AB - We introduce a method of applying Myhill-Nerode methods from formal language theory to hypergraphs and show how this method can be used to obtain the following parameterized complexity results. - Hypergraph Cutwidth (deciding whether a hypergraph on n vertices has cutwidth at most k) is linear-time solvable for constant k. - For hypergraphs of constant incidence treewidth (treewidth of the incidence graph), Hypertree Width and variants cannot be solved by simple finite tree automata. The proof leads us to conjecture that Hypertree Width is W[1]-hard for this parameter.

    KW - Cutwidths

    KW - Finite tree automaton

    KW - Formal language theory

    KW - Hyper graph

    KW - Incidence graphs

    KW - Linear-time

    KW - Parameterized complexity

    KW - Tree-width

    KW - Algorithms

    KW - Automata theory

    KW - Formal languages

    KW - Graph theory

    U2 - 10.1007/978-3-642-45030-3_35

    DO - 10.1007/978-3-642-45030-3_35

    M3 - Conference Paper published in Proceedings

    SN - 978-3-642-45029-7

    T3 - Lecture Notes in Computer Science

    SP - 372

    EP - 382

    BT - Algorithms and Computation

    A2 - Cai, Leizhen

    A2 - Cheng, Sui-Wing

    A2 - Lam, Tak-Wah

    PB - Springer

    CY - Germany

    ER -

    Van Bevern R, Fellows M, Gaspers S, Rosamond F. Myhill-Nerode Methods for Hypergraphs. In Cai L, Cheng S-W, Lam T-W, editors, Algorithms and Computation: 24th International Symposium, ISAAC 2013 Hong Kong, China, December 16-18, 2013 Proceedings. Germany: Springer. 2013. p. 372-382. (Lecture Notes in Computer Science ). https://doi.org/10.1007/978-3-642-45030-3_35