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 Proceedingspeer-review

    4 Citations (Scopus)


    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
    Number of pages11
    ISBN (Print)978-3-642-45029-7
    Publication statusPublished - 2013
    Event24th International Symposium, ISAAC 2013 - Hong Kong, China
    Duration: 16 Dec 201318 Dec 2013

    Publication series

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


    Conference24th International Symposium, ISAAC 2013


    Dive into the research topics of 'Myhill-Nerode Methods for Hypergraphs'. Together they form a unique fingerprint.

    Cite this