{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:22:33Z","timestamp":1772119353089,"version":"3.50.1"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,7,13]],"date-time":"2023-07-13T00:00:00Z","timestamp":1689206400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,7,13]],"date-time":"2023-07-13T00:00:00Z","timestamp":1689206400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100021855","name":"University of Ioannina","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100021855","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,3]]},"abstract":"Abstract<\/jats:title>\n \n Chordal graphs are characterized as the intersection graphs of subtrees in a tree and such a representation is known as the tree model. Restricting the characterization results in well-known subclasses of chordal graphs such as interval graphs or split graphs. A typical example of a problem that does not behave computationally the same in all subclasses of chordal graphs is the\n Subset Feedback Vertex Set<\/jats:sc>\n (SFVS) problem: given a vertex-weighted graph\n \n \n $$G=(V,E)$$<\/jats:tex-math>\n \n \n G<\/mml:mi>\n =<\/mml:mo>\n (<\/mml:mo>\n V<\/mml:mi>\n ,<\/mml:mo>\n E<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n and a set\n \n \n $$S\\subseteq V$$<\/jats:tex-math>\n \n \n S<\/mml:mi>\n \u2286<\/mml:mo>\n V<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , we seek for a vertex set of minimum weight that intersects all cycles containing a vertex of\n S<\/jats:italic>\n . SFVS is known to be polynomial-time solvable on interval graphs, whereas SFVS remains\n np<\/jats:sc>\n -complete on split graphs and, consequently, on chordal graphs. Towards a better understanding of the complexity of SFVS on subclasses of chordal graphs, we exploit structural properties of a tree model in order to cope with the hardness of SFVS. Here we consider the\n leafage<\/jats:italic>\n , which measures the minimum number of leaves in a tree model. We show that SFVS can be solved in polynomial time for every chordal graph with bounded leafage. In particular, given a chordal graph on\n n<\/jats:italic>\n vertices with leafage\n \n \n $$\\ell $$<\/jats:tex-math>\n \n \u2113<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , we provide an algorithm for solving SFVS with running time\n \n \n $$n^{O(\\ell )}$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \u2113<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , thus improving upon\n \n \n $$n^{O(\\ell ^2)}$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n \u2113<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , which is the running time of an approach that utilizes the previously known algorithm for graphs with bounded mim-width. We complement our result by showing that SFVS is\n w<\/jats:sc>\n [1]-hard parameterized by\n \n \n $$\\ell $$<\/jats:tex-math>\n \n \u2113<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . Pushing further our positive result, it is natural to also consider the\n vertex leafage<\/jats:italic>\n , which measures the minimum upper bound on the number of leaves of every subtree in a tree model. However, we show that it is unlikely to obtain a similar result, as we prove that SFVS remains\n np<\/jats:sc>\n -complete on undirected path graphs, i.e., chordal graphs having vertex leafage at most two. Lastly, we provide a polynomial-time algorithm for solving SFVS on rooted path graphs, a proper subclass of undirected path graphs and graphs with mim-width one, which is faster than the approach of constructing a graph decomposition of mim-width one and applying the previously known algorithm for graphs with bounded mim-width.\n <\/jats:p>","DOI":"10.1007\/s00453-023-01149-5","type":"journal-article","created":{"date-parts":[[2023,7,13]],"date-time":"2023-07-13T01:02:12Z","timestamp":1689210132000},"page":"874-906","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Computing a Minimum Subset Feedback Vertex Set on Chordal Graphs Parameterized by Leafage"],"prefix":"10.1007","volume":"86","author":[{"given":"Charis","family":"Papadopoulos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Spyridon","family":"Tzimas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,7,13]]},"reference":[{"issue":"5","key":"1149_CR1","doi-asserted-by":"publisher","first-page":"1385","DOI":"10.1007\/s00453-022-00936-w","volume":"84","author":"B Bergougnoux","year":"2022","unstructured":"Bergougnoux, B., Papadopoulos, C., Telle, J.A.: Node multiway cut and subset feedback vertex set on graphs of bounded mim-width. Algorithmica 84(5), 1385\u20131417 (2022)","journal-title":"Algorithmica"},{"issue":"4","key":"1149_CR2","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0020-0190(86)90135-3","volume":"23","author":"Alan A Bertossi","year":"1986","unstructured":"Bertossi, Alan A., Bonuccelli, Maurizio A.: Hamiltonian circuits in interval graph generalizations. Inf. Process. Lett. 23(4), 195\u2013200 (1986)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"1149_CR3","first-page":"14","volume":"7","author":"HL Bodlaender","year":"2000","unstructured":"Bodlaender, H.L., Jansen, K.: On the complexity of the maximum cut problem. Nord. J. Comput. 7(1), 14\u201331 (2000)","journal-title":"Nord. J. Comput."},{"key":"1149_CR4","doi-asserted-by":"crossref","unstructured":"Bondy, J.A., Murty, U.S.R.: Graph Theory. Graduate Texts in Mathematics. Springer (2008)","DOI":"10.1007\/978-1-84628-970-5"},{"key":"1149_CR5","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1137\/0211015","volume":"11","author":"KS Booth","year":"1982","unstructured":"Booth, K.S., Howard Johnson, J.: Dominating sets in chordal graphs. SIAM J. Comput. 11, 191\u2013199 (1982)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1149_CR6","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS Booth","year":"1976","unstructured":"Booth, K.S., Lueker, George S.: Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms. J. Comput. Syst. Sci. 13(3), 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"1149_CR7","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.tcs.2021.12.010","volume":"902","author":"N Brettell","year":"2022","unstructured":"Brettell, N., Johnson, M., Paesani, G., Paulusma, D.: Computing subset transversals in $$H$$-free graphs. Theor. Comput. Sci. 902, 76\u201392 (2022)","journal-title":"Theor. Comput. Sci."},{"key":"1149_CR8","doi-asserted-by":"crossref","unstructured":"Brettell, N., Johnson, M., Paulusma, D.: Computing weighted subset transversals in $$H$$-free graphs. In: Algorithms and Data Structures - 17th International Symposium, WADS 2021, Proceedings, volume 12808 of Lecture Notes in Computer Science, pp. 229\u2013242. Springer (2021)","DOI":"10.1007\/978-3-030-83508-8_17"},{"key":"1149_CR9","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0012-365X(74)90002-8","volume":"9","author":"P Buneman","year":"1974","unstructured":"Buneman, P.: A characterization of rigid circuit graphs. Discret. Math. 9, 205\u2013212 (1974)","journal-title":"Discret. Math."},{"key":"1149_CR10","doi-asserted-by":"crossref","unstructured":"Chaplick, S.: Intersection graphs of non-crossing paths. In: Graph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Revised Papers, volume 11789 of Lecture Notes in Computer Science, pp. 311\u2013324. Springer (2019)","DOI":"10.1007\/978-3-030-30786-8_24"},{"key":"1149_CR11","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.dam.2012.12.006","volume":"168","author":"S Chaplick","year":"2014","unstructured":"Chaplick, S., Stacho, J.: The vertex leafage of chordal graphs. Discret. Appl. Math. 168, 14\u201325 (2014)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"1149_CR12","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0166-218X(88)90086-8","volume":"22","author":"DG Corneil","year":"1988","unstructured":"Corneil, D.G., Fonlupt, J.: The complexity of generalized clique covering. Discret. Appl. Math. 22(2), 109\u2013118 (1988)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"1149_CR13","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0166-218X(84)90088-X","volume":"9","author":"DG Corneil","year":"1984","unstructured":"Corneil, D.G., Perl, Y.: Clustering and domination in perfect graphs. Discret. Appl. Math. 9(1), 27\u201339 (1984)","journal-title":"Discret. Appl. Math."},{"key":"1149_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015)"},{"issue":"1","key":"1149_CR15","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1137\/110843071","volume":"27","author":"M Cygan","year":"2013","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Subset feedback vertex set is fixed-parameter tractable. SIAM J. Discret. Math. 27(1), 290\u2013309 (2013)","journal-title":"SIAM J. Discret. Math."},{"key":"1149_CR16","unstructured":"Dietz, P.F.: Intersection graph algorithms. PhD thesis, Cornell University (1984)"},{"issue":"1","key":"1149_CR17","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"MR Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F.A., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 410(1), 53\u201361 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"1149_CR18","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/s00453-012-9731-6","volume":"69","author":"FV Fomin","year":"2014","unstructured":"Fomin, F.V., Heggernes, P., Kratsch, D., Papadopoulos, C., Villanger, Y.: Enumerating minimal subset feedback vertex sets. Algorithmica 69(1), 216\u2013231 (2014)","journal-title":"Algorithmica"},{"issue":"9","key":"1149_CR19","doi-asserted-by":"publisher","first-page":"2432","DOI":"10.1007\/s00453-020-00692-9","volume":"82","author":"FV Fomin","year":"2020","unstructured":"Fomin, F.V., Golovach, P.A., Raymond, J.-F.: On the tractability of optimization problems on h-graphs. Algorithmica 82(9), 2432\u20132473 (2020)","journal-title":"Algorithmica"},{"key":"1149_CR20","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. W. H. Freeman and Co. (1978)"},{"issue":"1","key":"1149_CR21","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F Gavril","year":"1974","unstructured":"Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Comb. Theory Ser. B 16(1), 47\u201356 (1974)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"3","key":"1149_CR22","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0012-365X(75)90021-7","volume":"13","author":"F Gavril","year":"1975","unstructured":"Gavril, F.: A recognition algorithm for the intersection graphs of directed paths in directed trees. Discret. Math. 13(3), 237\u2013249 (1975)","journal-title":"Discret. Math."},{"key":"1149_CR23","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/j.jda.2013.09.005","volume":"26","author":"PA Golovach","year":"2014","unstructured":"Golovach, P.A., Heggernes, P., Kratsch, D., Saei, R.: Subset feedback vertex sets in chordal graphs. J. Discret. Algorithms 26, 7\u201315 (2014)","journal-title":"J. Discret. Algorithms"},{"key":"1149_CR24","doi-asserted-by":"crossref","unstructured":"Habib, M., Stacho, J.: Polynomial-time algorithm for the leafage of chordal graphs. In: Algorithms\u2014ESA 2009, 17th Annual European Symposium, Proceedings, volume 5757 of Lecture Notes in Computer Science, pp. 290\u2013300. Springer (2009)","DOI":"10.1007\/978-3-642-04128-0_27"},{"key":"1149_CR25","doi-asserted-by":"crossref","unstructured":"Heggernes, P., van \u2019t Hof, P., van Leeuwen, E.J., Saei, R.: Finding disjoint paths in split graphs. Theory Comput. Syst. 57(1), 140\u2013159 (2015)","DOI":"10.1007\/s00224-014-9580-6"},{"key":"1149_CR26","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/s00224-017-9805-6","volume":"62","author":"EC Hols","year":"2018","unstructured":"Hols, E.C., Kratsch, S.: A randomized polynomial kernel for subset feedback vertex set. Theory Comput. Syst. 62, 54\u201365 (2018)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"1149_CR27","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/s00453-010-9411-3","volume":"61","author":"Kyriaki Ioannidou","year":"2011","unstructured":"Ioannidou, Kyriaki, Mertzios, George B., Nikolopoulos, Stavros D.: The longest path problem has a polynomial solution on interval graphs. Algorithmica 61(2), 320\u2013341 (2011)","journal-title":"Algorithmica"},{"key":"1149_CR28","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/j.tcs.2019.09.012","volume":"796","author":"L Jaffke","year":"2019","unstructured":"Jaffke, L., Kwon, O.-J., Str\u00f8mme, T.F., Telle, J.A.: Mim-width III. graph powers and generalized distance domination problems. Theor. Comput. Sci. 796, 216\u2013236 (2019)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"1149_CR29","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/s00453-019-00607-3","volume":"82","author":"L Jaffke","year":"2020","unstructured":"Jaffke, L., Kwon, O.-J., Telle, J.A.: Mim-width II the feedback vertex set problem. Algorithmica 82(1), 118\u2013145 (2020)","journal-title":"Algorithmica"},{"key":"1149_CR30","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of a symposium on the Complexity of Computer Computations, The IBM Research Symposia Series, pp. 85\u2013103. Plenum Press, New York, (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"4","key":"1149_CR31","doi-asserted-by":"publisher","first-page":"1020","DOI":"10.1016\/j.jctb.2011.12.001","volume":"102","author":"K Kawarabayashi","year":"2012","unstructured":"Kawarabayashi, K., Kobayashi, Y.: Fixed-parameter tractability for the subset feedback set problem and the s-cycle packing problem. J. Comb. Theory Ser. B 102(4), 1020\u20131034 (2012)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"1149_CR32","doi-asserted-by":"publisher","first-page":"23","DOI":"10.7151\/dmgt.1061","volume":"18","author":"I-J Lin","year":"1998","unstructured":"Lin, I.-J., McKee, T.A., West, D.B.: The leafage of a chordal graph. Discuss. Math. Graph Theory 18(1), 23\u201348 (1998)","journal-title":"Discuss. Math. Graph Theory"},{"issue":"2","key":"1149_CR33","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0095-8956(86)90042-0","volume":"41","author":"CL Monma","year":"1986","unstructured":"Monma, C.L., Wei, V.K.: Intersection graphs of paths in a tree. J. Comb. Theory Ser. B 41(2), 141\u2013181 (1986)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"3","key":"1149_CR34","first-page":"256","volume":"3","author":"S Natarajan","year":"1996","unstructured":"Natarajan, S., Sprague, A.P.: Disjoint paths in circular arc graphs. Nord. J. Comput. 3(3), 256\u2013270 (1996)","journal-title":"Nord. J. Comput."},{"issue":"1","key":"1149_CR35","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1006\/jctb.2000.2001","volume":"81","author":"BS Panda","year":"2001","unstructured":"Panda, B.S.: The separator theorem for rooted directed vertex graphs. J. Comb. Theory Ser. B 81(1), 156\u2013162 (2001)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1149_CR36","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1016\/j.dam.2018.11.017","volume":"258","author":"C Papadopoulos","year":"2019","unstructured":"Papadopoulos, C., Tzimas, S.: Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs. Discret. Appl. Math. 258, 204\u2013221 (2019)","journal-title":"Discret. Appl. Math."},{"key":"1149_CR37","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/j.tcs.2020.01.029","volume":"814","author":"C Papadopoulos","year":"2020","unstructured":"Papadopoulos, C., Tzimas, S.: Subset feedback vertex set on graphs of bounded independent set size. Theor. Comput. Sci. 814, 177\u2013188 (2020)","journal-title":"Theor. Comput. Sci."},{"issue":"9","key":"1149_CR38","doi-asserted-by":"publisher","first-page":"3586","DOI":"10.1007\/s00453-019-00590-9","volume":"81","author":"G Philip","year":"2019","unstructured":"Philip, G., Rajan, V., Saurabh, S., Tale, P.: Subset feedback vertex set in chordal and split graphs. Algorithmica 81(9), 3586\u20133629 (2019)","journal-title":"Algorithmica"},{"issue":"4","key":"1149_CR39","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1016\/S0022-0000(03)00078-3","volume":"67","author":"K Pietrzak","year":"2003","unstructured":"Pietrzak, K.: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. J. Comput. Syst. Sci. 67(4), 757\u2013771 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"1149_CR40","doi-asserted-by":"crossref","unstructured":"Spinrad, J.P.: Efficient graph representations, volume 19 of Fields Institute monographs. American Mathematical Society (2003)","DOI":"10.1090\/fim\/019"},{"issue":"2","key":"1149_CR41","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1137\/0210022","volume":"10","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Node-deletion problems on bipartite graphs. SIAM J. Comput. 10(2), 310\u2013327 (1981)","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01149-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01149-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01149-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,11]],"date-time":"2024-03-11T11:09:44Z","timestamp":1710155384000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01149-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,13]]},"references-count":41,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["1149"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01149-5","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-2120025\/v1","asserted-by":"object"}]},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,13]]},"assertion":[{"value":"30 September 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 June 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 July 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"All authors declare no conflicts of interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}