Myhill–Nerode Methods for Hypergraphs

René van Bevern, Rodney G. Downey, Michael R. Fellows, Serge Gaspers, Frances A. Rosamond

Результат исследования: Научные публикации в периодических изданияхстатья

6 Цитирования (Scopus)

Аннотация

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.

Язык оригиналаанглийский
Страницы (с-по)696-729
Число страниц34
ЖурналAlgorithmica
Том73
Номер выпуска4
DOI
СостояниеОпубликовано - 1 дек 2015
Опубликовано для внешнего пользованияДа

Fingerprint Подробные сведения о темах исследования «Myhill–Nerode Methods for Hypergraphs». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    van Bevern, R., Downey, R. G., Fellows, M. R., Gaspers, S., & Rosamond, F. A. (2015). Myhill–Nerode Methods for Hypergraphs. Algorithmica, 73(4), 696-729. https://doi.org/10.1007/s00453-015-9977-x