zbMATH — the first resource for mathematics

A linear-time kernelization for the rooted $$k$$-leaf outbranching problem. (English) Zbl 1317.05072
Summary: In the rooted $$k$$-leaf outbranching problem, a digraph $$G = (V, E)$$, a vertex $$r$$ of $$G$$, and an integer $$k$$ are given, and the goal is to find an $$r$$-rooted spanning outtree of $$G$$ with $$\geq k$$ leaves (a subtree of $$G$$ with vertex set $$V$$, all edges directed away from $$r$$, and $$\geq k$$ leaves). We present a linear-time algorithm that computes a problem kernel with $$O(k^6)$$ vertices and $$O(k^7)$$ edges for the rooted $$k$$-leaf outbranching problem. By combining the new result with a result of J. Daligault and S. Thomassé [Lect. Notes Comput. Sci. 5917, 86–97 (2009; Zbl 1273.68162)], a kernel with a quadratic number of vertices and edges can be found on $$n$$-vertex $$m$$-edge digraphs in time $$O(n + m + k^{14})$$.

MSC:
 05C20 Directed graphs (digraphs), tournaments 05C05 Trees 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) 68Q25 Analysis of algorithms and problem complexity
Full Text:
References:
 [1] Alstrup, S.; Harel, D.; Lauridsen, P. W.; Thorup, M., Dominators in linear time, SIAM J. Comput., 28, 2117-2132, (1999) · Zbl 0939.68158 [2] Bevern, R. v., Fixed-parameter linear-time algorithms for NP-hard graph and hypergraph problems arising in industrial applications, (2014), Universitätsverlag der TU Berlin [3] Bevern, R. v.; Hartung, S.; Kammer, F.; Niedermeier, R.; Weller, M., Linear-time computation of a linear problem kernel for dominating set on planar graphs, (Proc. 6th International Symposium on Parameterized and Exact Computation, IPEC 2011, LNCS, vol. 7112, (2011), Springer), 194-206 · Zbl 1352.68119 [4] Binkele-Raible, D.; Fernau, H.; Fomin, F. V.; Lokshtanov, D.; Saurabh, S.; Villanger, Y., Kernel(s) for problems with no kernel: on out-trees with many leaves, ACM Trans. Algorithms, 8, 4, 38, (2012) · Zbl 1295.68120 [5] Bodlaender, H. L., A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput., 25, 6, 1305-1317, (1996) · Zbl 0864.68074 [6] Chen, J.; Kanj, I. A.; Jia, W., Vertex cover: further observations and further improvements, J. Algorithms, 41, 2, 280-301, (2001) · Zbl 1017.68087 [7] Daligault, J.; Thomassé, S., On finding directed trees with many leaves, (Proc. 4th International Symposium on Parameterized and Exact Computation, IWPEC 2009, LNCS, vol. 5917, (2009), Springer), 86-97 · Zbl 1273.68162 [8] Downey, R. G.; Fellows, M. R., Parameterized complexity, (1999), Springer · Zbl 0914.68076 [9] Downey, R. G.; Fellows, M. R., (Fundamentals of Parameterized Complexity, Texts in Computer Science, (2013), Springer) · Zbl 1358.68006 [10] Nemhauser, G. L.; L. E. Trotter, Vertex packings: structural properties and algorithms, Math. Program., 8, 1, 232-248, (1975) · Zbl 0314.90059 [11] Fafianie, S.; Kratsch, S., Streaming kernelization, (Proc. 39th International Symposium on Mathematical Foundations of Computer Science, MFCS 2014, Part II, LNCS, vol. 8635, (2014), Springer), 275-286 · Zbl 1426.68120 [12] Fellows, M. R.; Langston, M. A.; Rosamond, F. A.; Shaw, P., Efficient parameterized preprocessing for cluster editing, (Proc. 16th International Symposium on Fundamentals of Computation Theory, FCT 2007, LNCS, vol. 4639, (2007), Springer), 312-321 · Zbl 1135.68511 [13] Grohe, M., Descriptive and parameterized complexity, (Proc. 13th International Workshop on Computer Science Logic, CSL 1999, LNCS, vol. 1683, (1999), Springer), 14-31 · Zbl 0943.03029 [14] Guo, J., A more effective linear kernelization for cluster editing, Theoret. Comput. Sci., 410, 8-10, 718-726, (2009) · Zbl 1162.68025 [15] Hagerup, T., Linear-time kernelization for planar dominating set, (Proc. 6th International Symposium on Parameterized and Exact Computation, IPEC 2011, LNCS, vol. 7112, (2011), Springer), 181-193 · Zbl 1352.68109 [16] Harel, D., A linear time algorithm for finding dominators in flow graphs and related problems, (Proc. 17th Annual ACM Symposium on Theory of Computing, STOC 1985, vol. 17, (1985), ACM), 185-194 [17] Kammer, F., A linear-time kernelization for the rooted $$k$$-leaf outbranching problem, (Proc. 39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2013, LNCS, vol. 8165, (2013), Springer), 310-320 · Zbl 1417.05086 [18] Kloks, T.; Lee, C.-M.; Liu, J., New algorithms for $$k$$-face cover, $$k$$-feedback vertex set, and $$k$$-disjoint cycles on plane and planar graphs, (Proc. 28th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2002, LNCS, vol. 2573, (2002), Springer), 282-295 · Zbl 1022.68100 [19] Protti, F.; Dantas da Silva, M.; Szwarcfiter, J., Applying modular decomposition to parameterized cluster editing problems, Theory Comput. Syst., 44, 91-104, (2009) · Zbl 1179.68111
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.