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 Proceedings

    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 Dive into the research topics of 'Myhill-Nerode Methods for Hypergraphs'. Together they form a unique fingerprint.

  • 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). Springer. https://doi.org/10.1007/978-3-642-45030-3_35