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/

Zendy Plus

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

Zendy Tools

Zendy Open

There are many classical problems in P whose time complexities have not beenimproved over the past decades. Recent studies of "Hardness in P" have revealedthat, for several of such problems, the current fastest algorithm is the bestpossible under some complexity assumptions. To bypass this difficulty, Fomin etal. (SODA 2017) introduced the concept of fully polynomial FPT algorithms. Fora problem with the current best time complexity $O(n^c)$, the goal is to designan algorithm running in $k^{O(1)}n^{c'}$ time for a parameter $k$ and aconstant $c'<c$. In this paper, we investigate the complexity of graph problemsin P parameterized by tree-depth, a graph parameter related to tree-width. Weshow that a simple divide-and-conquer method can solve many graph problems,including Weighted Matching, Negative Cycle Detection, Minimum Weight Cycle,Replacement Paths, and 2-hop Cover, in $O(\mathrm{td}\cdot m)$ time or$O(\mathrm{td}\cdot (m+n\log n))$ time, where $\mathrm{td}$ is the tree-depthof the input graph. Because any graph of tree-width $\mathrm{tw}$ hastree-depth at most $(\mathrm{tw}+1)\log_2 n$, our algorithms also run in$O(\mathrm{tw}\cdot m\log n)$ time or $O(\mathrm{tw}\cdot (m+n\log n)\log n)$time. These results match or improve the previous best algorithms parameterizedby tree-width. Especially, we solve an open problem of fully polynomial FPTalgorithm for Weighted Matching parameterized by tree-width posed by Fomin etal.

On the Power of Tree-Depth for Fully Polynomial FPT Algorithms