[en] We consider the problem LIS of deciding whether there exists an induced subtree with exactly 𝑖≤𝑛 vertices and ℓ leaves in a given graph G with n vertices. We study the associated optimization problem, that consists in computing the maximal number of leaves, denoted by 𝐿𝐺(𝑖), realized by an induced subtree with i vertices, for 0≤𝑖≤𝑛. We begin by proving that the LIS problem is NP-complete in general. Then, we describe a nontrivial branch and bound algorithm that computes the function 𝐿𝐺 for any simple graph G. In the special case where G is a tree of maximum degree 𝛥, we provide a O(𝛥𝑛^3) time and O(𝑛^2) space algorithm to compute the function 𝐿𝐺.
Disciplines :
Mathematics
Author, co-author :
Blondin Massé, Alexandre; Université du Québec à Montréal
De Carufel, Julien; Université du Québec à Trois Rivières
Goupil, Alain; Université du Québec à Trois Rivières
Lapointe, Mélodie; Université du Québec à Montréal
Nadeau, Émile; Université du Québec à Montréal
Vandomme, Elise ; Université de Liège - ULiège > Département de mathématique > Probabilités et statistique mathématique
Language :
English
Title :
Fully leafed induced subtrees
Publication date :
2018
Event name :
29th International Workshop on Combi- natorial Algorithms (IWOCA)
Bodlaender, H.L.: On linear time minor tests and depth first search. In: Dehne, F., Sack, J.-R., Santoro, N. (eds.) WADS 1989. LNCS, vol. 382, pp. 577–590. Springer, Heidelberg (1989). https://doi.org/10.1007/3-540-51542-9 48
Boukerche, A., Cheng, X., Linus, J.: A performance evaluation of a novel energy-aware data-centric routing algorithm in wireless sensor networks. Wirel. Netw. 11(5), 619–635 (2005)
Chen, S., Ljubić, I., Raghavan, S.: The generalized regenerator location problem. INFORMS J. Comput. 27(2), 204–220 (2015)
Deepak, A., Fernández-Baca, D., Tirthapura, S., Sanderson, M.J., McMahon, M.M.: EvoMiner: frequent subtree mining in phylogenetic databases. Knowl. Inf. Syst. 41(3), 559–590 (2014)
Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Heidelberg (2010)
Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: on completeness for W[1]. Theoret. Comput. Sci. 141(1), 109–131 (1995)
Downey, R.G., Fellows, M.R.: Parameterized computational feasibility. In: Clote, P., Remmel, J.B. (eds.) Feasible Mathematics II, pp. 219–244. Birkhäuser Boston, Boston (1995)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999). https://doi.org/10.1007/978-1-4612-0515-9
Erdős, P., Saks, M., Sós, V.T.: Maximum induced trees in graphs. J. Combin. Theory Ser. B 41(1), 61–79 (1986)
Garey, M.R., Johnson, D.S.: Computers and Intractability. W. H. Freeman and Co., San Francisco (1979)
Payan, C., Tchuente, M., Xuong, N.H.: Arbres avec un nombre maximum de som-mets pendants (Trees with a maximal number of vertices with degree 1). Discrete Math. 49(3), 267–273 (1984)
Székely, L.A., Wang, H.: On subtrees of trees. Adv. Appl. Math. 34(1), 138–155 (2005)
Wasa, K., Arimura, H., Uno, T.: Efficient enumeration of induced subtrees in a K-degenerate graph. In: Ahn, H.-K., Shin, C.-S. (eds.) ISAAC 2014. LNCS, vol. 8889, pp. 94–102. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13075-0 8
Zaki, M.J.: Efficiently mining frequent trees in a forest. In: Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2002, pp. 71–80. ACM, New York (2002)
