Kernelization of Arc Disjoint Cycle Packing in α-Bounded Digraphs
Tóm tắt
In the Arc Disjoint Cycle Packing problem, we are given a simple directed graph (digraph) G, a positive integer k, and the task is to decide whether there exist k arc disjoint cycles. The problem is known to be W[1]-hard on general digraphs parameterized by the standard parameter k. In this paper we show that the problem admits a polynomial kernel on α-bounded digraphs. That is, we give a polynomial-time algorithm, that given an instance (D,k) of Arc Disjoint Cycle Packing, outputs an equivalent instance
$(D^{\prime },k^{\prime })$
of Arc Disjoint Cycle Packing, such that
$k^{\prime }\leq k$
and the size of
$D^{\prime }$
is upper-bounded by a polynomial function of k. For any integer α ≥ 1, the class of α-bounded digraphs, denoted by
${\mathcal D}_{\alpha }$
, contains a digraph D such that the maximum size of an independent set in D is at most α. That is, in D, any set of α + 1 vertices has an arc with both end-points in the set. For α = 1, this corresponds to the well-studied class of tournaments. Our results generalize the recent result by Bessy et al. [MFCS, 2019] about Arc Disjoint Cycle Packing on tournaments.
Tài liệu tham khảo
Abu-Khzam, F.N.: An improved kernelization algorithm for r-set packing. Inf. Process. Lett. 110(16), 621–624 (2010)
Bessy, S., Bougeret, M., Krithika, R., Sahu, A., Saurabh, S., Thiebaut, J., Zehavi, M.: Packing arc-disjoint cycles in tournaments. In: 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, Aachen, Germany, volume 138 of LIPIcs, pp 27:1–27:14,2019 (2019)
Bessy, S., Bougeret, M., Krithika, R., Sahu, A., Saurabh, S., Thiebaut, J., Zehavi, M.: Packing arc-disjoint cycles in tournaments. Algorithmica 83(5), 1393–1420 (2021). https://doi.org/10.1007/s00453-020-00788-2
Bodlaender, H. L.: On disjoint cycles. Int. J. Found. Comput. Sci. 5(1), 59–68 (1994)
Bodlaender, H.L., Thomassé, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. 412(35), 4570–4578 (2011)
Caprara, A., Panconesi, A., Rizzi, R.: Packing cycles in undirected graphs. J. Algorithms 48(1), 239–256 (2003)
Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015)
Diestel, R.: Graph theory. Springer-Verlag, Berlin Heidelberg (2006)
Dorninger, D.: Hamiltonian circuits determining the order of chromosomes. Discret. Appl. Math. 50(2), 159–168 (1994)
Downey, R.G., Fellows, M.R.: Fundamentals of parameterized complexity. Springer-Verlag, london (2013)
Erdős, P., Pósa, L.: On independent circuits contained in a graph. Canadian J. Math. 17, 347–352 (1965)
Fellows, M. R., Langston, M.A.: Nonconstructive tools for proving polynomial-time decidability. J. ACM 35(3), 727–739 (1988)
Flum, J., Grohe, M.: Parameterized complexity theory springer (2006)
Lochet, W., Lokshtanov, D., Misra, P., Saurabh, S., Sharma, R., Zehavi, M.: Fault tolerant subgraphs with applications in kernelization. In: Vidick, T. (ed.) 11th Innovations in theoretical computer science conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, vol. 151 of LIPIcs, pp. 47:1–47:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ITCS.2020.47 (2020)
Lokshtanov, D., Mouawad, A.E., Saurabh, S., Meirav Zehavi.: Packing cycles faster than Erdős-Pósa. SIAM J. Discrete Math. 33(3), 1194–1215 (2019)
Reed, B.A., Robertson, N., Seymour, P.D., Thomas, R.: Packing directed circuits. Combinatorica 16(4), 535–554 (1996)
Robertson, N., Seymour, P.D.: Graph, minors. XIII the disjoint paths problem. Journal of Combinatorial Theory Series B 63(1), 65–110 (1995)