On the Parameterized Complexity of Eulerian Strong Component Arc Deletion

Area of Science:

• Graph Theory
• Computational Complexity

Background:

• The Eulerian Strong Component Arc Deletion problem aims to minimize arc deletions in a directed multigraph so that each resulting strongly connected component is Eulerian.
• This problem extends the Directed Feedback Arc Set problem and has applications in housing market analysis.
• The parameterized complexity of this problem, particularly concerning solution size, was a previously unresolved question.

Purpose of the Study:

• To resolve the fixed-parameter tractability of the Eulerian Strong Component Arc Deletion problem parameterized by solution size.
• To conduct a comprehensive complexity analysis for various parameterizations, including treewidth and maximum degree.

Main Methods:

• Utilized parameterized complexity theory to establish lower bounds on computational complexity.
• Developed algorithms for specific parameterizations, analyzing their efficiency.
• Employed techniques from graph theory and complexity theory to prove hardness and tractability results.

Main Results:

• Ruled out a fixed-parameter tractable (FPT) algorithm for the problem when parameterized by solution size, assuming standard complexity conjectures.
• Demonstrated W[1]-hardness or para-NP-hardness when parameterized solely by treewidth or maximum degree.
• Established XP-completeness for treewidth parameterization and FPT results for combined parameters (treewidth and maximum degree, or treewidth and solution size).

Conclusions:

• The Eulerian Strong Component Arc Deletion problem is computationally hard for several natural parameterizations.
• Efficient algorithms exist when parameters are combined, offering practical solutions for certain graph structures.
• The study provides a complete picture of the problem's parameterized complexity, with implications for related graph problems.