{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:20:44Z","timestamp":1759638044796,"version":"3.37.3"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2021,3,15]],"date-time":"2021-03-15T00:00:00Z","timestamp":1615766400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,3,15]],"date-time":"2021-03-15T00:00:00Z","timestamp":1615766400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP17K12643","JP16K16010"],"award-info":[{"award-number":["JP17K12643","JP16K16010"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP17K19960","JP18H05291"],"award-info":[{"award-number":["JP17K19960","JP18H05291"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,8]]},"DOI":"10.1007\/s00453-021-00815-w","type":"journal-article","created":{"date-parts":[[2021,3,15]],"date-time":"2021-03-15T10:03:26Z","timestamp":1615802606000},"page":"2503-2520","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Improved Analysis of Highest-Degree Branching for Feedback Vertex Set"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7990-2987","authenticated-orcid":false,"given":"Yoichi","family":"Iwata","sequence":"first","affiliation":[]},{"given":"Yusuke","family":"Kobayashi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,3,15]]},"reference":[{"key":"815_CR1","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1613\/jair.638","volume":"12","author":"A Becker","year":"2000","unstructured":"Becker, A., Bar-Yehuda, R., Geiger, D.: Randomized algorithms for the loop cutset problem. J. Artif. Intell. Res. 12, 219\u2013234 (2000). https:\/\/doi.org\/10.1613\/jair.638","journal-title":"J. Artif. Intell. Res."},{"issue":"1","key":"815_CR2","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1142\/S0129054194000049","volume":"5","author":"HL Bodlaender","year":"1994","unstructured":"Bodlaender, H.L.: On disjoint cycles. Int. J. Found Comput. Sci. 5(1), 59\u201368 (1994). https:\/\/doi.org\/10.1142\/S0129054194000049","journal-title":"Int. J. Found Comput. Sci."},{"key":"815_CR3","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/11847250_18","volume":"2006","author":"K Burrage","year":"2006","unstructured":"Burrage, K., Estivill-Castro, V., Fellows, M.R., Langston, M.A., Mac, S., Rosamond, F.A.: The undirected feedback vertex set problem has a poly(k) kernel. IWPEC 2006, 192\u2013202 (2006). https:\/\/doi.org\/10.1007\/11847250_18","journal-title":"IWPEC"},{"key":"815_CR4","doi-asserted-by":"publisher","unstructured":"Cao, Y.: A Naive algorithm for feedback vertex set. In: SOSA 2018, pp. 1:1\u20131:9 (2018). https:\/\/doi.org\/10.4230\/OASIcs.SOSA.2018.1","DOI":"10.4230\/OASIcs.SOSA.2018.1"},{"issue":"1","key":"815_CR5","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/s00453-014-9904-6","volume":"73","author":"Y Cao","year":"2015","unstructured":"Cao, Y., Chen, J., Liu, Y.: On feedback vertex set: new measure and new structures. Algorithmica 73(1), 63\u201386 (2015). https:\/\/doi.org\/10.1007\/s00453-014-9904-6","journal-title":"Algorithmica"},{"issue":"7","key":"815_CR6","doi-asserted-by":"publisher","first-page":"1188","DOI":"10.1016\/j.jcss.2008.05.002","volume":"74","author":"J Chen","year":"2008","unstructured":"Chen, J., Fomin, F.V., Liu, Y., Lu, S., Villanger, Y.: Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci. 74(7), 1188\u20131198 (2008). https:\/\/doi.org\/10.1016\/j.jcss.2008.05.002","journal-title":"J. Comput. Syst. Sci."},{"key":"815_CR7","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1109\/FOCS.2011.23","volume":"2011","author":"M Cygan","year":"2011","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. FOCS 2011, 150\u2013159 (2011). https:\/\/doi.org\/10.1109\/FOCS.2011.23","journal-title":"FOCS"},{"issue":"1","key":"815_CR8","doi-asserted-by":"publisher","first-page":"3:1","DOI":"10.1145\/2462896.2462899","volume":"5","author":"M Cygan","year":"2013","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: On multiway cut parameterized above lower bounds. TOCT 5(1), 3:1-3:11 (2013). https:\/\/doi.org\/10.1145\/2462896.2462899","journal-title":"TOCT"},{"key":"815_CR9","doi-asserted-by":"publisher","unstructured":"Dell, H., Husfeldt, T., Jansen, B.M.P., Kaski, P., Komusiewicz, C., Rosamond, F.A.: The first parameterized algorithms and computational experiments challenge. In: IPEC 2016, pp. 30:1\u201330:9 (2016). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2016.30","DOI":"10.4230\/LIPIcs.IPEC.2016.30"},{"key":"815_CR10","unstructured":"Downey, R.G., Fellows, M.R.: Fixed parameter tractability and completeness. In: Complexity Theory: Current Research, pp. 191\u2013225 (1992)"},{"key":"815_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity. Monographs in Computer Science","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, Berlin (1999). https:\/\/doi.org\/10.1007\/978-1-4612-0515-9"},{"issue":"5","key":"815_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1552285.1552286","volume":"56","author":"FV Fomin","year":"2009","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact algorithms. J. ACM 56(5), 1\u201332 (2009). https:\/\/doi.org\/10.1145\/1552285.1552286","journal-title":"J. ACM"},{"key":"815_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential. Algorithms Texts in Theoretical Computer Science. An EATCS Series","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential. Algorithms Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2010). https:\/\/doi.org\/10.1007\/978-3-642-16533-7"},{"key":"815_CR14","unstructured":"Gaspers, S.: Exponential Time Algorithms\u2014Structures, Measures, and Bounds. VDM (2010). http:\/\/www.cse.unsw.edu.au\/~sergeg\/SergeBookETA2010_print.pdf"},{"key":"815_CR15","unstructured":"Imanishi, K., Iwata, Y.: Feedback vertex set solver (2016). http:\/\/github.com\/wata-orz\/fvs. Entry to PACE challenge 2016"},{"key":"815_CR16","doi-asserted-by":"publisher","unstructured":"Iwata, Y.: Linear-time kernelization for feedback vertex set. In: ICALP 2017, pp. 68:1\u201368:14 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2017.68","DOI":"10.4230\/LIPIcs.ICALP.2017.68"},{"key":"815_CR17","unstructured":"Iwata, Y., Kobayashi, Y.: Improved analysis of highest-degree branching for feedback vertex set. In: IPEC 2019, pp. 22:1\u201322:11 (2019)"},{"issue":"4","key":"815_CR18","doi-asserted-by":"publisher","first-page":"1377","DOI":"10.1137\/140962838","volume":"45","author":"Y Iwata","year":"2016","unstructured":"Iwata, Y., Wahlstr\u00f6m, M., Yoshida, Y.: Half-integrality, LP-branching and FPT algorithms. SIAM J. Comput. 45(4), 1377\u20131411 (2016). https:\/\/doi.org\/10.1137\/140962838","journal-title":"SIAM J. Comput."},{"key":"815_CR19","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1109\/FOCS.2018.00051","volume":"2018","author":"Y Iwata","year":"2018","unstructured":"Iwata, Y., Yamaguchi, Y., Yoshida, Y.: 0\/1\/all CSPs, half-integral A-path packing, and linear-time FPT algorithms. FOCS 2018, 462\u2013473 (2018). https:\/\/doi.org\/10.1109\/FOCS.2018.00051","journal-title":"FOCS"},{"key":"815_CR20","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume":"1972","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. Complex Comput Comput 1972, 85\u2013103 (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","journal-title":"Complex Comput Comput"},{"key":"815_CR21","doi-asserted-by":"publisher","unstructured":"Kiljan, K., Pilipczuk, M.: Experimental evaluation of parameterized algorithms for feedback vertex set. In: SEA 2018, pp. 12:1\u201312:12 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.SEA.2018.12","DOI":"10.4230\/LIPIcs.SEA.2018.12"},{"issue":"10","key":"815_CR22","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1016\/j.ipl.2014.05.001","volume":"114","author":"T Kociumaka","year":"2014","unstructured":"Kociumaka, T., Pilipczuk, M.: Faster deterministic feedback vertex set. Inf. Process. Lett. 114(10), 556\u2013560 (2014). https:\/\/doi.org\/10.1016\/j.ipl.2014.05.001","journal-title":"Inf. Process. Lett."},{"key":"815_CR23","doi-asserted-by":"publisher","unstructured":"Li, J., Nederlof, J.: Detecting feedback vertex sets of size k in O*(2.7$${}^{k}$$) time. In: SODA 2020, pp. 971\u2013989. SIAM (2020). https:\/\/doi.org\/10.1137\/1.9781611975994.58","DOI":"10.1137\/1.9781611975994.58"},{"issue":"2","key":"815_CR24","doi-asserted-by":"publisher","first-page":"15:1","DOI":"10.1145\/2566616","volume":"11","author":"D Lokshtanov","year":"2014","unstructured":"Lokshtanov, D., Narayanaswamy, N.S., Raman, V., Ramanujan, M.S., Saurabh, S.: Faster parameterized algorithms using linear programming. ACM Trans. Algorithms 11(2), 15:1-15:31 (2014). https:\/\/doi.org\/10.1145\/2566616","journal-title":"ACM Trans. Algorithms"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00815-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00815-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00815-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,22]],"date-time":"2021-07-22T14:03:46Z","timestamp":1626962626000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00815-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,15]]},"references-count":24,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["815"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00815-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,3,15]]},"assertion":[{"value":"27 December 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 February 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 March 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}