Myhill-Nerode methods for hypergraphs

René Van Bevern, Michael R. Fellows, Serge Gaspers, Frances A. Rosamond

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

4 Citations (Scopus)

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 - 24th International Symposium, ISAAC 2013, Proceedings
Pages372-382
Number of pages11
DOIs
Publication statusPublished - 1 Dec 2013
Externally publishedYes
Event24th International Symposium on Algorithms and Computation, ISAAC 2013 - Hong Kong, China
Duration: 16 Dec 201318 Dec 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8283 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference24th International Symposium on Algorithms and Computation, ISAAC 2013
CountryChina
CityHong Kong
Period16.12.201318.12.2013

Fingerprint Dive into the research topics of 'Myhill-Nerode methods for hypergraphs'. Together they form a unique fingerprint.

Cite this