{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T19:37:03Z","timestamp":1780342623026,"version":"3.54.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,9,17]],"date-time":"2018-09-17T00:00:00Z","timestamp":1537142400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2018,12,31]]},"abstract":"\n For a family\n F<\/jats:italic>\n of graphs, a graph\n G<\/jats:italic>\n , and a positive integer\n k<\/jats:italic>\n , the\n F<\/jats:italic>\n -D\n eletion<\/jats:sc>\n problem asks whether we can delete at most\n k<\/jats:italic>\n vertices from\n G<\/jats:italic>\n to obtain a graph in\n F<\/jats:italic>\n .\n F<\/jats:italic>\n -D\n eletion<\/jats:sc>\n generalizes many classical graph problems such as V\n ertex<\/jats:sc>\n C\n over<\/jats:sc>\n , F\n eedback<\/jats:sc>\n V\n ertex<\/jats:sc>\n S\n et<\/jats:sc>\n , and O\n dd<\/jats:sc>\n C\n ycle<\/jats:sc>\n T\n ransversal<\/jats:sc>\n . For an integer \u03b1 \u2265 1, an\n n<\/jats:italic>\n -vertex (multi) graph\n G<\/jats:italic>\n = (\n V<\/jats:italic>\n , \u22c3\n i=1<\/jats:sub>\n \u03b1<\/jats:sup>\n E<\/jats:italic>\n i<\/jats:sub>\n ), where the edge set of\n G<\/jats:italic>\n is partitioned into \u03b1 color classes, is called an \u03b1-edge-colored (multi) graph. A natural extension of the\n F<\/jats:italic>\n -D\n eletion<\/jats:sc>\n problem to edge-colored graphs is the S\n imultaneous<\/jats:sc>\n F<\/jats:italic>\n -D\n eletion<\/jats:sc>\n problem. In the latter problem, we are given an \u03b1-edge-colored graph\n G<\/jats:italic>\n and the goal is to find a set\n S<\/jats:italic>\n of at most\n k<\/jats:italic>\n vertices such that each graph\n \n G\n i<\/jats:sub>\n <\/jats:italic>\n \u2212\n S<\/jats:italic>\n , where\n \n G\n i<\/jats:sub>\n <\/jats:italic>\n = (\n V<\/jats:italic>\n ,\n \n E\n i<\/jats:sub>\n <\/jats:italic>\n ) and 1 \u2264\n i<\/jats:italic>\n \u2264 \u03b1, is in\n F<\/jats:italic>\n . In this work, we study S\n imultaneous<\/jats:sc>\n F<\/jats:italic>\n -D\n eletion<\/jats:sc>\n for\n F<\/jats:italic>\n being the family of forests. In other words, we focus on the S\n imultaneous<\/jats:sc>\n F\n eedback<\/jats:sc>\n V\n ertex<\/jats:sc>\n S\n et<\/jats:sc>\n (S\n im<\/jats:sc>\n FVS) problem. Algorithmically, we show that, like its classical counterpart, S\n im<\/jats:sc>\n FVS parameterized by\n k<\/jats:italic>\n is fixed-parameter tractable (FPT) and admits a polynomial kernel, for any fixed constant \u03b1. In particular, we give an algorithm running in 2\n \n O<\/jats:italic>\n (\n \u03b1 k<\/jats:italic>\n )\n <\/jats:sup>\n n<\/jats:italic>\n \n O<\/jats:italic>\n (1)\n <\/jats:sup>\n time and a kernel with\n O<\/jats:italic>\n (\u03b1\n k<\/jats:italic>\n 3(\u03b1+1)<\/jats:sup>\n ) vertices. The running time of our algorithm implies that S\n im<\/jats:sc>\n FVS is FPT even when \u03b1 \u2208\n o<\/jats:italic>\n (log\n n<\/jats:italic>\n ). We complement this positive result by showing that if we allow \u03b1 to be in\n O<\/jats:italic>\n (log\n n<\/jats:italic>\n ), where\n n<\/jats:italic>\n is the number of vertices in the input graph, then S\n im<\/jats:sc>\n FVS becomes W[1]-hard. In particular, when \u03b1 is roughly equal to\n c<\/jats:italic>\n log\n n<\/jats:italic>\n , for a non-zero positive constant\n c<\/jats:italic>\n , the problem becomes W[1]-hard. Our positive results answer one of the open problems posed by Cai and Ye (MFCS 2014).\n <\/jats:p>","DOI":"10.1145\/3265027","type":"journal-article","created":{"date-parts":[[2018,9,17]],"date-time":"2018-09-17T12:14:54Z","timestamp":1537186494000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Simultaneous Feedback Vertex Set"],"prefix":"10.1145","volume":"10","author":[{"given":"Akanksha","family":"Agrawal","sequence":"first","affiliation":[{"name":"University of Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"University of Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amer E.","family":"Mouawad","sequence":"additional","affiliation":[{"name":"University of Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"University of Bergen, Norway, and The Institute of Mathematical Sciences, Chennai, India"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,9,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480196305124"},{"key":"e_1_2_1_2_1","volume-title":"Alternating cycles and paths in edge-coloured multigraphs: A survey. Discr. Math. 165-166","author":"Bang-Jensen J\u00f8rgen","year":"1997","unstructured":"J\u00f8rgen Bang-Jensen and Gregory Gutin . 1997. Alternating cycles and paths in edge-coloured multigraphs: A survey. Discr. Math. 165-166 ( 1997 ), 39--60. J\u00f8rgen Bang-Jensen and Gregory Gutin. 1997. Alternating cycles and paths in edge-coloured multigraphs: A survey. Discr. Math. 165-166 (1997), 39--60."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44465-8_13"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629595"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.05.002"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.06.026"},{"key":"e_1_2_1_7_1","volume-title":"Parameterized Algorithms","author":"Cygan Marek","unstructured":"Marek Cygan , Fedor V. Fomin , Lukasz Kowalik , Daniel Lokshtanov , D\u00e1niel Marx , Marcin Pilipczuk , Michal Pilipczuk , and Saket Saurabh . 2015. Parameterized Algorithms . Springer . Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.23"},{"key":"e_1_2_1_9_1","volume-title":"Graph Theory","author":"Diestel Reinhard","unstructured":"Reinhard Diestel . 2012. Graph Theory ( 4 th ed.). Graduate texts in mathematics, Vol. 173 . Springer . Reinhard Diestel. 2012. Graph Theory (4th ed.). Graduate texts in mathematics, Vol. 173. Springer.","edition":"4"},{"key":"e_1_2_1_10_1","volume-title":"Fellows","author":"Downey Rod G.","year":"1997","unstructured":"Rod G. Downey and Michael R . Fellows . 1997 . Parameterized Complexity. Springer-Verlag . Rod G. Downey and Michael R. Fellows. 1997. Parameterized Complexity. Springer-Verlag."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.62"},{"key":"e_1_2_1_12_1","volume-title":"Johnson","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and David S . Johnson . 1979 . Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman . M. R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.06.004"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-008-0789-5"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2797140"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.05.001"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.46"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1789694.1789708"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2566616"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a005"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9233-8"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9484-z"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34611-8_19"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2003.10.009"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721848"},{"key":"e_1_2_1_28_1","volume-title":"On an estimate of the chromatic class of a p-graph. Diskret. Analiz No. 3","author":"Vizing V. G.","year":"1964","unstructured":"V. G. Vizing . 1964. On an estimate of the chromatic class of a p-graph. Diskret. Analiz No. 3 ( 1964 ), 25--30. V. G. Vizing. 1964. On an estimate of the chromatic class of a p-graph. Diskret. Analiz No. 3 (1964), 25--30."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-014-9737-x"},{"key":"e_1_2_1_30_1","volume-title":"A note on finding dual feedback vertex set. CoRR abs\/1510.00773","author":"Junjie Ye.","year":"2015","unstructured":"Junjie Ye. 2015. A note on finding dual feedback vertex set. CoRR abs\/1510.00773 ( 2015 ). http:\/\/arxiv.org\/abs\/1510.00773 Junjie Ye. 2015. A note on finding dual feedback vertex set. CoRR abs\/1510.00773 (2015). http:\/\/arxiv.org\/abs\/1510.00773"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3265027","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3265027","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:57:27Z","timestamp":1750208247000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3265027"}},"subtitle":["A Parameterized Perspective"],"short-title":[],"issued":{"date-parts":[[2018,9,17]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,12,31]]}},"alternative-id":["10.1145\/3265027"],"URL":"https:\/\/doi.org\/10.1145\/3265027","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,17]]},"assertion":[{"value":"2017-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-09-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}