English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Many combinatorial problems can be solved in time $O^*(c^{tw})$ on graphs oftreewidth $tw$, for a problem-specific constant $c$. In several cases, matchingupper and lower bounds on $c$ are known based on the Strong Exponential TimeHypothesis (SETH). In this paper we investigate the complexity of solvingproblems on graphs of bounded cutwidth, a graph parameter that takes largervalues than treewidth. We strengthen earlier treewidth-based lower bounds toshow that, assuming SETH, Independent Set cannot be solved in$O^*((2-\varepsilon)^{cutw})$ time, and Dominating Set cannot be solved in$O^*((3-\varepsilon)^{cutw})$ time. By designing a new crossover gadget, weextend these lower bounds even to planar graphs of bounded cutwidth ortreewidth. Hence planarity does not help when solving Independent Set orDominating Set on graphs of bounded width. This sharply contrasts the fact thatin many settings, planarity allows problems to be solved much more efficiently.

Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth