Tamojit Saha, Student of Dept. of Computer Science, Ramakrishna Mission Vivekananda Educational and Research Institute (RKMVERI), has been awarded the third prize for the student presentation in Young Research Forum (YRF) held as a part of Ajit Diwan Memprial Workshop organised on 19 – 21 January 2026.

Talk Topic: Subset Feedback Vertex Set and Subset Vertex Cover on AT-free graphs.

Abstract

Given a graph $G=(V,E)$ and a subset $S \subseteq V(G)$, the \textit{Subset Feedback Vertex Set (SFVS)} problem asks to find a minimum vertex set that intersects every cycle containing a vertex from set $S$. SFVS is known to be NP-hard on general graphs. The computational complexity of SFVS on AT-free graphs was posed as an open problem by Papadopoulos~et al. in \cite{papadopoulos2019polynomial}. We resolve this problem by presenting a polynomial-time algorithm for SFVS on AT-free graphs. Along with this, we also present a polynomial time algorithm for \textit{Subset Vertex Cover (SVC)} problem on AT-free graphs. In SVC, the task is to find a minimum vertex set that contains an endpoint of every edge which contains some vertex from $S$ as its end point. We note here, SVC is used as a subroutine to compute SFVS.