Generalized hypertree width is W[1]-hard parameterized by incidence treewidth
Generalized hypertree width is W[1]-hard parameterized by incidence treewidth
Let be a hypergraph, and let the incidence treewidth of be the treewidth of its incidence graph. Generalized-hypertree-width conjecture. Generalized Hypertree Width is W[1]-hard with respect to the parameter incidence treewidth. The paper motivates this conjecture by the number of equivalence classes arising in its Myhill–Nerode construction; it does not establish the conjectured parameterized-hardness result.
Sources & referencesView supporting material
Primary source
René van Bevern, Rodney G. Downey, Michael R. Fellows, Serge Gaspers and Frances A. Rosamond, “Myhill-Nerode methods for hypergraphs”, arXiv:1211.1299 (2015).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.