Name
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$$k that runs in linear time for constant $$k$$k. In terms of parameterized complexity theory, the problem is fixed-parameter linear parameterized by $$k$$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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s00453-015-9977-x | Algorithmica |
Keywords | DocType | Volume |
NP-hard problems,Fixed-parameter algorithms,Automata theory,Cutwidth,Hypertree width | Conference | 73 |
Issue | ISSN | Citations |
4 | 0178-4617 | 3 |
PageRank | References | Authors |
0.38 | 8 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| René van Bevern | 1 | 126 | 19.33 |
| Michael R. Fellows | 2 | 4138 | 319.37 |
| Serge Gaspers | 3 | 411 | 31.98 |
| Frances A. Rosamond | 4 | 21 | 2.83 |