TY - JOUR

T1 - Myhill–Nerode Methods for Hypergraphs

AU - van Bevern, René

AU - Downey, Rodney G.

AU - Fellows, Michael R.

AU - Gaspers, Serge

AU - Rosamond, Frances A.

PY - 2015/12/1

Y1 - 2015/12/1

N2 - 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  that runs in linear time for constant In terms of parameterized complexity theory, the problem is fixed-parameter linear parameterized by(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.

AB - 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  that runs in linear time for constant In terms of parameterized complexity theory, the problem is fixed-parameter linear parameterized by(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.

KW - Automata theory

KW - Cutwidth

KW - Fixed-parameter algorithms

KW - Hypertree width

KW - NP-hard problems

UR - http://www.scopus.com/inward/record.url?scp=84949321574&partnerID=8YFLogxK

U2 - 10.1007/s00453-015-9977-x

DO - 10.1007/s00453-015-9977-x

M3 - Article

AN - SCOPUS:84949321574

VL - 73

SP - 696

EP - 729

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 4

ER -