2017/01/17 by Charis Papadopoulos, Papadopoulos, Charis, Spyridon Tzimas +1
Computer Science · Neuroscience · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Nuclear Receptors and Signaling
paper · pdf · doi:10.48550/arxiv.1701.04634
openalex publication_date 2017/01/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a vertex-weighted graph G=(V,E) and a set S \⊆ V, a subset\nfeedback vertex set X is a set of the vertices of G such that the graph\ninduced by V \∖ X has no cycle containing a vertex of S. The\n\Subset Feedback Vertex Set problem takes as input G and S and asks\nfor the subset feedback vertex set of minimum total weight. In contrast to the\nclassical \Feedback Vertex Set problem which is obtained from the\n\Subset Feedback Vertex Set problem for S=V, restricted to graph\nclasses the \Subset Feedback Vertex Set problem is known to be\nNP-complete on split graphs and, consequently, on chordal graphs. However as\n\Feedback Vertex Set is polynomially solvable for AT-free graphs, no\nsuch result is known for the \Subset Feedback Vertex Set problem on any\nsubclass of AT-free graphs. Here we give the first polynomial-time algorithms\nfor the problem on two unrelated subclasses of AT-free graphs: interval graphs\nand permutation graphs. As a byproduct we show that there exists a\npolynomial-time algorithm for circular-arc graphs by suitably applying our\nalgorithm for interval graphs. Moreover towards the unknown complexity of the\nproblem for AT-free graphs, we give a polynomial-time algorithm for\nco-bipartite graphs. Thus we contribute to the first positive results of the\n\Subset Feedback Vertex Set problem when restricted to graph classes\nfor which \Feedback Vertex Set is solved in polynomial time.\n