Parameterized Eulerian strong component arc deletion problem on tournaments. (English) Zbl 1242.68113
Summary: In the problem Min-DESC, we are given a digraph \(D\) and an integer \(k\), and asked whether there exists a set \(A^{'}\) of at most \(k\) arcs in \(D\), such that if we remove the arcs of \(A^{'}\), in the resulting digraph every strong component is Eulerian. Min-DESC is NP-hard; K. Cechlárová and I. Schlotter [Lect. Notes Comput. Sci. 6478, 72–83 (2010; Zbl 1310.91109)] asked whether the problem is fixed-parameter tractable when parameterized by \(k\). We consider the subproblem of Min-DESC when \(D\) is a tournament. We show that this problem is fixed-parameter tractable with respect to \(k\).
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 05C45 | Eulerian and Hamiltonian graphs |
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
Citations:
Zbl 1310.91109References:
| [1] | Bang-Jensen, J.; Gutin, G., Digraphs: Theory, Algorithms and Applications (2008), Springer |
| [2] | Bodlaender, H. L.; Downey, R. G.; Fellows, M. R.; Hermelin, D., On problems without polynomial kernels, J. Comput. System Sci., 75, 8, 423-434 (2009) · Zbl 1192.68288 |
| [3] | Bodlaender, H. L.; Thomasse, S.; Yeo, A., Kernel bounds for disjoint cycles and disjoint paths, (Proc. ESA 2009. Proc. ESA 2009, Lecture Notes in Comput. Sci., vol. 5757 (2009), Springer), 635-646 · Zbl 1256.68081 |
| [4] | Cechlárová, K.; Schlotter, I., Computing the deficiency of housing markets with duplicate houses, (Proc. IPEC 2010. Proc. IPEC 2010, Lecture Notes in Comput. Sci., vol. 6478 (2010), Springer), 72-84 · Zbl 1310.91109 |
| [5] | Crowston, R.; Gutin, G.; Jones, M.; Yeo, A., Parameterized Eulerian strong component arc deletion problem on tournaments · Zbl 1242.68113 |
| [6] | M. Cygan, D. Marx, M. Pilipczuk, M. Pilipczuk, I. Schlotter, Parameterized complexity of Eulerian deletion problems, in: Proc. WG 2011, 2011, pp. 131-142.; M. Cygan, D. Marx, M. Pilipczuk, M. Pilipczuk, I. Schlotter, Parameterized complexity of Eulerian deletion problems, in: Proc. WG 2011, 2011, pp. 131-142. · Zbl 1341.05141 |
| [7] | Downey, R. G.; Fellows, M. R., Parameterized Complexity (1999), Springer-Verlag · Zbl 0914.68076 |
| [8] | Dom, M.; Lokshtanov, D.; Saurabh, S., Incompressibility through colors and IDs, (Proc. ICALP 2009, Part I. Proc. ICALP 2009, Part I, Lecture Notes in Comput. Sci., vol. 5555 (2009), Springer), 378-389 · Zbl 1248.68243 |
| [9] | Flum, J.; Grohe, M., Parameterized Complexity Theory (2006), Springer-Verlag · Zbl 1143.68016 |
| [10] | Niedermeier, R., Invitation to Fixed-Parameter Algorithms (2006), Oxford University Press · Zbl 1095.68038 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
