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

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 monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

The Subset Feedback Vertex Set problem generalizes the classical FeedbackVertex Set problem and asks, for a given undirected graph $G=(V,E)$, a set $S\subseteq V$, and an integer $k$, whether there exists a set $X$ of at most $k$vertices such that no cycle in $G-X$ contains a vertex of $S$. It wasindependently shown by Cygan et al. (ICALP '11, SIDMA '13) and Kawarabayashiand Kobayashi (JCTB '12) that Subset Feedback Vertex Set is fixed-parametertractable for parameter $k$. Cygan et al. asked whether the problem also admitsa polynomial kernelization.  We answer the question of Cygan et al. positively by giving a randomizedpolynomial kernelization for the equivalent version where $S$ is a set ofedges. In a first step we show that Edge Subset Feedback Vertex Set has arandomized polynomial kernel parameterized by $|S|+k$ with $O(|S|^2k)$vertices. For this we use the matroid-based tools of Kratsch and Wahlstr\"om(FOCS '12) that for example were used to obtain a polynomial kernel for$s$-Multiway Cut. Next we present a preprocessing that reduces the giveninstance $(G,S,k)$ to an equivalent instance $(G',S',k')$ where the size of$S'$ is bounded by $O(k^4)$. These two results lead to a polynomial kernel forSubset Feedback Vertex Set with $O(k^9)$ vertices.

A randomized polynomial kernel for Subset Feedback Vertex Set