Charles Darwin University

CDU eSpace
Institutional Repository

CDU Staff and Student only

Myhill-Nerode Methods for Hypergraphs

van Bevern, René, Downey, Rodney G., Fellows, Michael R., Gaspers, Serge and Rosamond, Frances A. (2015). Myhill-Nerode Methods for Hypergraphs. Algorithmica: an international journal in computer science,73:696-729.

Document type: Journal Article
Citation counts:
Google Scholar Search Google Scholar

IRMA ID 84373604xPUB69
Title Myhill-Nerode Methods for Hypergraphs
Author van Bevern, René
Downey, Rodney G.
Fellows, Michael R.
Gaspers, Serge
Rosamond, Frances A.
Journal Name Algorithmica: an international journal in computer science
Publication Date 2015
Volume Number 73
ISSN 0178-4617   (check CDU catalogue open catalogue search in new window)
Scopus ID 2-s2.0-84949321574
Start Page 696
End Page 729
Total Pages 34
Place of Publication United States
Publisher Springer New York LLC
HERDC Category C1 - Journal Article (DIISR)
Abstract 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.
DOI   (check subscription with CDU E-Gateway service for CDU Staff and Students  check subscription with CDU E-Gateway in new window)
Version Filter Type
Access Statistics: 194 Abstract Views  -  Detailed Statistics
Created: Tue, 26 Jul 2016, 12:59:24 CST