Myhill–Nerode Methods for Hypergraphs. / van Bevern, René; Downey, Rodney G.; Fellows, Michael R. et al.
In: Algorithmica, Vol. 73, No. 4, 01.12.2015, p. 696-729.Research output: Contribution to journal › Article › peer-review
}
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 -
ID: 22340121