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

The Subset Feedback Vertex Set problem (SFVS), to delete $k$ vertices from agiven graph such that any vertex in a vertex subset (called a terminal set) isnot in a cycle in the remaining graph, generalizes the famous Feedback VertexSet problem and Multiway Cut problem. SFVS remains NP-hard even in split andchordal graphs, and SFVS in Chordal Graphs (SFVS-C) can be considered as animplicit 3-Hitting Set problem. However, it is not easy to solve SFVS-C fasterthan 3-Hitting Set. In 2019, Philip, Rajan, Saurabh, and Tale (Algorithmica2019) proved that SFVS-C can be solved in $\mathcal{O}^{*}(2^{k})$ time,slightly improving the best result $\mathcal{O}^{*}(2.076^{k})$ for 3-HittingSet. In this paper, we break the "$2^{k}$-barrier" for SFVS-C by giving an$\mathcal{O}^{*}(1.820^{k})$-time algorithm. Our algorithm uses reduction andbranching rules based on the Dulmage-Mendelsohn decomposition and adivide-and-conquer method.

Breaking the Barrier $2^k$ for Subset Feedback Vertex Set in Chordal Graphs