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

We consider questions that arise from the intersection between the areas ofpolynomial-time approximation algorithms, subexponential-time algorithms, andfixed-parameter tractable algorithms. The questions, which have been askedseveral times (e.g., [Marx08, FGMS12, DF13]), are whether there is anon-trivial FPT-approximation algorithm for the Maximum Clique (Clique) andMinimum Dominating Set (DomSet) problems parameterized by the size of theoptimal solution. In particular, letting $\text{OPT}$ be the optimum and $N$ bethe size of the input, is there an algorithm that runs in$t(\text{OPT})\text{poly}(N)$ time and outputs a solution of size$f(\text{OPT})$, for any functions $t$ and $f$ that are independent of $N$ (forClique, we want $f(\text{OPT})=\omega(1)$)?  In this paper, we show that both Clique and DomSet admit no non-trivialFPT-approximation algorithm, i.e., there is no$o(\text{OPT})$-FPT-approximation algorithm for Clique and no$f(\text{OPT})$-FPT-approximation algorithm for DomSet, for any function $f$(e.g., this holds even if $f$ is the Ackermann function). In fact, our resultsimply something even stronger: The best way to solve Clique and DomSet, evenapproximately, is to essentially enumerate all possibilities. Our results holdunder the Gap Exponential Time Hypothesis (Gap-ETH) [Dinur16, MR16], whichstates that no $2^{o(n)}$-time algorithm can distinguish between a satisfiable3SAT formula and one which is not even $(1 - \epsilon)$-satisfiable for someconstant $\epsilon > 0$.  Besides Clique and DomSet, we also rule out non-trivial FPT-approximation forMaximum Balanced Biclique, Maximum Subgraphs with Hereditary Properties, andMaximum Induced Matching in bipartite graphs. Additionally, we rule out$k^{o(1)}$-FPT-approximation algorithm for Densest $k$-Subgraph although thisratio does not yet match the trivial $O(k)$-approximation algorithm.

From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More