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 study the \textsc{$\alpha$-Fixed Cardinality Graph Partitioning($\alpha$-FCGP)} problem, the generic local graph partitioning problemintroduced by Bonnet et al. [Algorithmica 2015]. In this problem, we are givena graph $G$, two numbers $k,p$ and $0\leq\alpha\leq 1$, the question is whetherthere is a set $S\subseteq V$ of size $k$ with a specified coverage function$cov_{\alpha}(S)$ at least $p$ (or at most $p$ for the minimization version).The coverage function $cov_{\alpha}(\cdot)$ counts edges with exactly oneendpoint in $S$ with weight $\alpha$ and edges with both endpoints in $S$ withweight $1 - \alpha$. $\alpha$-FCGP generalizes a number of fundamental graphproblems such as \textsc{Densest $k$-Subgraph}, \textsc{Max $k$-Vertex Cover},and \textsc{Max $(k,n-k)$-Cut}.  A natural question in the study of $\alpha$-FCGP is whether the algorithmicresults known for its special cases, like \textsc{Max $k$-Vertex Cover}, couldbe extended to more general settings. One of the simple but powerful methodsfor obtaining parameterized approximation [Manurangsi, SOSA 2019] andsubexponential algorithms [Fomin et al. IPL 2011] for \textsc{Max $k$-VertexCover} is based on the greedy vertex degree orderings. The main insight of ourwork is that the idea of greed vertex degree ordering could be used to designfixed-parameter approximation schemes (FPT-AS) for $\alpha > 0$ and thesubexponential-time algorithms for the problem on apex-minor free graphs formaximization with $\alpha > 1/3$ and minimization with $\alpha < 1/3$.

FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges