Myhill–Nerode Methods for Hypergraphs

We give an analog of the Myhill–Nerode theorem from formal language theory for hypergraphs and use it to derive the following results for two NP-hard hypergraph problems. (1) We provide an algorithm for testing whether a hypergraph has cutwidth at most  k that runs in linear time for constant  k . I...

Full description

Saved in:
Bibliographic Details
Published in:Algorithmica 2015-12, Vol.73 (4), p.696-729
Main Authors: van Bevern, René, Downey, Rodney G., Fellows, Michael R., Gaspers, Serge, Rosamond, Frances A.
Format: Article
Language:English
Subjects:
Algorithm Analysis and Problem Complexity
Algorithms
Computer Science
Computer Systems Organization and Communication Networks
Data Structures and Information Theory
Mathematics of Computing
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We give an analog of the Myhill–Nerode theorem from formal language theory for hypergraphs and use it to derive the following results for two NP-hard hypergraph problems. (1) We provide an algorithm for testing whether a hypergraph has cutwidth at most  k that runs in linear time for constant  k . In terms of parameterized complexity theory, the problem is fixed-parameter linear parameterized by  k . (2) We show that it is not expressible in monadic second-order logic whether a hypergraph has bounded (fractional, generalized) hypertree width. The proof leads us to conjecture that, in terms of parameterized complexity theory, these problems are W[1]-hard parameterized by the incidence treewidth (the treewidth of the incidence graph). Thus, in the form of the Myhill–Nerode theorem for hypergraphs, we obtain a method to derive linear-time algorithms and to obtain indicators for intractability for hypergraph problems parameterized by incidence treewidth.
ISSN:0178-4617
1432-0541
DOI:10.1007/s00453-015-9977-x