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

A recent trend in the design of FPT algorithms is exploiting thehalf-integrality of LP relaxations. In other words, starting with ahalf-integral optimal solution to an LP relaxation, we assign integral valuesto variables one-by-one by branch and bound. This technique is general and theresulting time complexity has a low dependency on the parameter. However, thetime complexity often becomes a large polynomial in the input size because weneed to compute half-integral optimal LP solutions.  In this paper, we address this issue by providing an $O(km)$-time algorithmfor solving the LPs arising from various FPT problems, where $k$ is the optimalvalue and $m$ is the number of edges/constraints. Our algorithm is based oninteresting connections among 0/1/all constraints, which has been studied inthe field of constraints satisfaction, $A$-path packing, which has been studiedin the field of combinatorial optimization, and the LPs used in FPT algorithms.With the aid of this algorithm, we obtain improved FPT algorithms for variousproblems, including Group Feedback Vertex Set, Subset Feedback Vertex Set, NodeMultiway Cut, Node Unique Label Cover, and Non-monochromatic Cycle Transversal.The obtained running time for each of these problems is linear in the inputsize and has the current smallest dependency on the parameter. In particular,these algorithms are the first linear-time FPT algorithms for problemsincluding Group Feedback Vertex Set and Non-monochromatic Cycle Transversal.

0/1/all CSPs, Half-Integral $A$-path Packing, and Linear-Time FPT Algorithms