{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:40:41Z","timestamp":1781077241376,"version":"3.54.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2025,8,7]],"date-time":"2025-08-07T00:00:00Z","timestamp":1754524800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,8,7]],"date-time":"2025-08-07T00:00:00Z","timestamp":1754524800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100014013","name":"UK Research and Innovation","doi-asserted-by":"publisher","award":["EP\/V044621\/1"],"award-info":[{"award-number":["EP\/V044621\/1"]}],"id":[{"id":"10.13039\/100014013","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014013","name":"UK Research and Innovation","doi-asserted-by":"publisher","award":["EP\/V044621\/1"],"award-info":[{"award-number":["EP\/V044621\/1"]}],"id":[{"id":"10.13039\/100014013","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014013","name":"UK Research and Innovation","doi-asserted-by":"publisher","award":["EP\/V044621\/1"],"award-info":[{"award-number":["EP\/V044621\/1"]}],"id":[{"id":"10.13039\/100014013","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014013","name":"UK Research and Innovation","doi-asserted-by":"publisher","award":["EP\/V044621\/1"],"award-info":[{"award-number":["EP\/V044621\/1"]}],"id":[{"id":"10.13039\/100014013","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,11]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>In this paper, we study the Eulerian Strong Component Arc Deletion problem, where the input is a directed multigraph and the goal is to delete the minimum number of arcs to ensure every strongly connected component of the resulting digraph is Eulerian. This problem is a natural extension of the Directed Feedback Arc Set problem and is also known to be motivated by certain scenarios arising in the study of housing markets. The complexity of the problem, when parameterized by solution size (i.e., size of the deletion set), has remained unresolved and has been highlighted in several papers. In this work, we answer this question by ruling out (subject to the usual complexity assumptions) a fixed-parameter algorithm (FPT algorithm) for this parameter and conduct a broad analysis of the problem with respect to other natural parameterizations. We prove both positive and negative results. Among these, we demonstrate that the problem is also hard (W[1]-hard or even para-NP-hard) when parameterized by either treewidth or maximum degree alone. Complementing our lower bounds, we establish that the problem is in XP when parameterized by treewidth and FPT when parameterized either by both treewidth and maximum degree or by both treewidth and solution size. We show that on simple digraphs, these algorithms have near-optimal asymptotic dependence on the treewidth assuming the Exponential Time Hypothesis.<\/jats:p>","DOI":"10.1007\/s00453-025-01336-6","type":"journal-article","created":{"date-parts":[[2025,8,7]],"date-time":"2025-08-07T07:04:59Z","timestamp":1754550299000},"page":"1669-1709","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the Parameterized Complexity of Eulerian Strong Component Arc Deletion"],"prefix":"10.1007","volume":"87","author":[{"given":"V\u00e1clav","family":"Bla\u017eej","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Satyabrata","family":"Jana","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M. S.","family":"Ramanujan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Strulo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,8,7]]},"reference":[{"key":"1336_CR1","first-page":"13","volume":"1","author":"CA Barefoot","year":"1987","unstructured":"Barefoot, C.A., Entringer, R., Swart, H.C.: Vulnerability in graphs\u2013a comparative survey. JCMCC 1, 13\u201322 (1987)","journal-title":"JCMCC"},{"key":"1336_CR2","doi-asserted-by":"publisher","unstructured":"Blazej, V., Jana, S., Ramanujan, M.\u00a0S., Strulo, P.: On the parameterized complexity of eulerian strong component arc deletion. In \u00c9douard Bonnet and Pawel Rzazewski, editors, 19th International Symposium on Parameterized and Exact Computation, IPEC 2024, September 4-6, 2024, Royal Holloway, University of London, Egham, United Kingdom, volume 321 of LIPIcs, pages 4:1\u20134:20. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2024). https:\/\/doi.org\/10.4230\/LIPICS.IPEC.2024.4","DOI":"10.4230\/LIPICS.IPEC.2024.4"},{"issue":"2","key":"1336_CR3","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/130947374","volume":"45","author":"HL Bodlaender","year":"2016","unstructured":"Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: A $$\\text{ c}^{\\text{ k }}$$ n 5-approximation algorithm for treewidth. SIAM J. Comput. 45(2), 317\u2013378 (2016). https:\/\/doi.org\/10.1137\/130947374","journal-title":"SIAM J. Comput."},{"key":"1336_CR4","doi-asserted-by":"crossref","unstructured":"Cechl\u00e1rov\u00e1, K., Schlotter, I.: Computing the deficiency of housing markets with duplicate houses. In IPEC, volume 6478 of Lecture Notes in Computer Science, pages 72\u201383. Springer, (2010)","DOI":"10.1007\/978-3-642-17493-3_9"},{"issue":"6","key":"1336_CR5","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/J.IPL.2011.11.014","volume":"112","author":"R Crowston","year":"2012","unstructured":"Crowston, R., Gutin, G.Z., Jones, M., Yeo, A.: Parameterized Eulerian strong component arc deletion problem on tournaments. Inf. Process. Lett. 112(6), 249\u2013251 (2012). https:\/\/doi.org\/10.1016\/J.IPL.2011.11.014","journal-title":"Inf. Process. Lett."},{"key":"1336_CR6","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., D\u00e1niel, M., Michal, P., Saket, S.: Parameterized algorithms. Springer, Cham (2015)"},{"issue":"1","key":"1336_CR7","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/S00453-012-9667-X","volume":"68","author":"M Cygan","year":"2014","unstructured":"Cygan, M., Marx, D., Pilipczuk, M., Pilipczuk, M., Schlotter, I.: Parameterized complexity of Eulerian deletion problems. Algorithmica 68(1), 41\u201361 (2014). https:\/\/doi.org\/10.1007\/S00453-012-9667-X","journal-title":"Algorithmica"},{"key":"1336_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of parameterized complexity. Texts in computer science","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of parameterized complexity. Texts in computer science. Springer, London (2013)"},{"issue":"4","key":"1336_CR9","doi-asserted-by":"publisher","first-page":"1181","DOI":"10.1007\/S00453-016-0127-X","volume":"76","author":"PG Drange","year":"2016","unstructured":"Drange, P.G., Dregi, M.S., van \u2019t Hof, P.: On the computational complexity of vertex integrity and component order connectivity. Algorithmica 76(4), 1181\u20131202 (2016). https:\/\/doi.org\/10.1007\/S00453-016-0127-X","journal-title":"Algorithmica"},{"key":"1336_CR10","doi-asserted-by":"publisher","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"LR Ford","year":"1956","unstructured":"Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Can. J. Math. 8, 399\u2013404 (1956). https:\/\/doi.org\/10.4153\/CJM-1956-045-5","journal-title":"Can. J. Math."},{"issue":"1","key":"1336_CR11","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF02579200","volume":"7","author":"A Frank","year":"1987","unstructured":"Frank, A., Tardos, \u00c9.: An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7(1), 49\u201365 (1987). https:\/\/doi.org\/10.1007\/BF02579200","journal-title":"Combinatorica"},{"key":"1336_CR12","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/J.TCS.2022.03.021","volume":"918","author":"T Gima","year":"2022","unstructured":"Gima, T., Hanaka, T., Kiyomi, M., Kobayashi, Y., Otachi, Y.: Exploring the gap between treedepth and vertex cover through vertex integrity. Theor. Comput. Sci. 918, 60\u201376 (2022). https:\/\/doi.org\/10.1016\/J.TCS.2022.03.021","journal-title":"Theor. Comput. Sci."},{"key":"1336_CR13","doi-asserted-by":"publisher","DOI":"10.1016\/J.DISOPT.2022.100740","volume":"46","author":"A G\u00f6ke","year":"2022","unstructured":"G\u00f6ke, A., Marx, D., Mnich, M.: Parameterized algorithms for generalizations of directed feedback vertex set. Discret. Optim. 46, 100740 (2022). https:\/\/doi.org\/10.1016\/J.DISOPT.2022.100740","journal-title":"Discret. Optim."},{"key":"1336_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/J.JCSS.2018.03.001","volume":"97","author":"P Goyal","year":"2018","unstructured":"Goyal, P., Misra, P., Panolan, F., Philip, G., Saurabh, S.: Finding even subgraphs even faster. J. Comput. Syst. Sci. 97, 1\u201313 (2018). https:\/\/doi.org\/10.1016\/J.JCSS.2018.03.001","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"1336_CR15","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/J.JCSS.2012.04.004","volume":"79","author":"K Jansen","year":"2013","unstructured":"Jansen, K., Kratsch, S., Marx, D., Schlotter, I.: Bin packing with fixed number of bins revisited. J. Comput. Syst. Sci. 79(1), 39\u201349 (2013). https:\/\/doi.org\/10.1016\/J.JCSS.2012.04.004","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"1336_CR16","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/MOOR.8.4.538","volume":"8","author":"HW Lenstra Jr","year":"1983","unstructured":"Lenstra, H.W., Jr.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538\u2013548 (1983). https:\/\/doi.org\/10.1287\/MOOR.8.4.538","journal-title":"Math. Oper. Res."},{"issue":"3","key":"1336_CR17","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1287\/MOOR.12.3.415","volume":"12","author":"R Kannan","year":"1987","unstructured":"Kannan, R.: Minkowski\u2019s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415\u2013440 (1987). https:\/\/doi.org\/10.1287\/MOOR.12.3.415","journal-title":"Math. Oper. Res."},{"key":"1336_CR18","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: 50 Years of Integer Programming, pages 219\u2013241. Springer, (2010)","DOI":"10.1007\/978-3-540-68279-0_8"},{"key":"1336_CR19","doi-asserted-by":"publisher","unstructured":"Korhonen, T.: A single-exponential time 2-approximation algorithm for treewidth. In: 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 184\u2013192. IEEE, (2021). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00026","DOI":"10.1109\/FOCS52979.2021.00026"},{"key":"1336_CR20","doi-asserted-by":"publisher","unstructured":"Korhonen, T., Lokshtanov, D.: An improved parameterized algorithm for treewidth. In STOC, pages 528\u2013541. ACM, (2023). https:\/\/doi.org\/10.1145\/3564246.3585245","DOI":"10.1145\/3564246.3585245"},{"issue":"1","key":"1336_CR21","doi-asserted-by":"publisher","first-page":"85","DOI":"10.4086\/TOC.2010.V006A005","volume":"6","author":"D Marx","year":"2010","unstructured":"Marx, D.: Can you beat treewidth? Theory Comput. 6(1), 85\u2013112 (2010). https:\/\/doi.org\/10.4086\/TOC.2010.V006A005","journal-title":"Theory Comput."},{"issue":"1","key":"1336_CR22","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. J. Comb. Theory B 63(1), 65\u2013110 (1995). https:\/\/doi.org\/10.1006\/jctb.1995.1006","journal-title":"J. Comb. Theory B"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01336-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01336-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01336-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,20]],"date-time":"2025-09-20T20:13:15Z","timestamp":1758399195000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01336-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,7]]},"references-count":22,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2025,11]]}},"alternative-id":["1336"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01336-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,7]]},"assertion":[{"value":"24 October 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 July 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 August 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}