zbMATH — the first resource for mathematics

Myhill-Nerode methods for hypergraphs. (English) Zbl 1329.68129
Cai, Leizhen (ed.) et al., Algorithms and computation. 24th international symposium, ISAAC 2013, Hong Kong, China, December 16–18, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-45029-7/pbk). Lecture Notes in Computer Science 8283, 372-382 (2013).
Summary: 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.
\(\bullet\) Hypergraph Cutwidth (deciding whether a hypergraph on \(n\) vertices has cutwidth at most \(k\)) is linear-time solvable for constant \(k\).
\(\bullet\) 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.
For the entire collection see [Zbl 1277.68005].

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C65 Hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
68Q45 Formal languages and automata
Full Text: DOI