2026-08-11T08:34:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22230 2024-12-05T15:32:40Z ddc:004 open_access

On the Parameterized Complexity of Eulerian Strong Component Arc Deletion Blažej, Václav Jana, Satyabrata Ramanujan, M. S. Strulo, Peter Parameterized complexity Eulerian graphs Treewidth 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 tractable (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 these algorithms have near-optimal asymptotic dependence on the treewidth assuming the Exponential Time Hypothesis. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Václav Blažej and Satyabrata Jana and M. S. Ramanujan and Peter Strulo 2024 Is Part Of LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2024.4 urn:nbn:de:0030-drops-222306 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.4 eng https://creativecommons.org/licenses/by/4.0/legalcode