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 reduction rules for Directed Feedback Vertex Set (DFVS) on instanceswithout long cycles. A DFVS instance without cycles longer than $d$ naturallycorresponds to an instance of $d$-Hitting Set, however, enumerating all cyclesin an $n$-vertex graph and then kernelizing the resulting $d$-Hitting Setinstance can be too costly, as already enumerating all cycles can take time$\Omega(n^d)$. We show how to compute a kernel with at most $2^dk^d$ verticesand at most $d^{3d}k^d$ induced cycles of length at most $d$ (which however,cannot be enumerated efficiently), where $k$ is the size of a minimum directedfeedback vertex set. We then study classes of graphs whose underlyingundirected graphs have bounded expansion or are nowhere dense; these are verygeneral classes of sparse graphs, containing e.g. classes excluding a minor ora topological minor. We prove that for such classes without induced cycles oflength greater than $d$ we can compute a kernel with $O_d(k)$ and$O_{d,\epsilon}(k^{1+\epsilon})$ vertices for any $\epsilon>0$, respectively,in time $O_d(n^{O(1)})$ and $O_{d,\epsilon}(n^{O(1)})$, respectively. The mostrestricted classes we consider are strongly connected planar graphs without any(induced or non-induced) long cycles. We show that these have bounded treewidthand hence DFVS on planar graphs without cycles of length greater than $d$ canbe solved in time $2^{O(d)}\cdot n^{O(1)}$. We finally present a new datareduction rule for general DFVS and prove that the rule together with a fewstandard rules subsumes all the rules applied by Bergougnoux et al. to obtain apolynomial kernel for DFVS[FVS], i.e., DFVS parameterized by the feedbackvertex set number of the underlying (undirected) graph. We conclude by studyingthe LP-based approximation of DFVS.

Data reduction for directed feedback vertex set on graphs without long induced cycles