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 Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

M ax -C ut (MC), E dge D ominating S et (EDS), G raph C oloring (GC) and H amiltonian P ath (HP) on graphs of bounded cliquewidth have received significant attention as they can be formulated in MSO2 (and therefore have linear-time algorithms on bounded treewidth graphs by the celebrated Courcelle's theorem), but cannot be formulated in MSO1 (which would have yielded linear-time algorithms on bounded cliquewidth graphs by a well-known theorem of Courcelle, Makowsky, and Rotics). Each of these problems can be solved in time g(k)nf(k) on graphs of cliquewidth k. Fomin et al. [Intractability of Clique-Width Parameterizations. SIAM J. Comput. 39(5): 1941--1956 (2010)] showed that the running times cannot be improved to g(k)nO(1) assuming W[1]≠FPT. However, this does not rule out non-trivial improvements to the exponent f(k) in the running times. In a follow-up paper, Fomin et al. [Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width. SIAM J. Comput. 43(5): 1541--1563 (2014)] improved the running times for EDS and MC to nO(k), and proved g(k)no(k) lower bounds for EDS, MC and HP assuming the ETH. Recently, Bergougnoux, Kante and Kwon [WADS 2017] gave an nő(k)-time algorithm for HP. Thus, prior to this work, EDS, MC and HP were known to have tight nΘ(k) algorithmic upper and lower bounds. In contrast, GC has an upper bound of nO(2k) and a lower bound of merely [Equation] (implicit from the W[1]-hardness proof). In this paper, we close the gap for GC by proving a lower bound of n2o(k). This shows that GC behaves qualitatively different from the other three problems. To the best of our knowledge, GC is the first natural problem known to require exponential dependence on the parameter in the exponent of n.

Cliquewidth III: The Odd Case of Graph Coloring Parameterized by Cliquewidth