Fully leafed induced subtrees

[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)

Event place :

Singapour, Singapore

Event date :

16-19 July 2018

Audience :

International

Journal title :

Lecture Notes in Computer Science

ISSN :

0302-9743

eISSN :

1611-3349

Publisher :

Springer, Germany

Volume :

10979

Peer reviewed :

Peer reviewed

Additional URL :

https://link.springer.com/chapter/10.1007/978-3-319-94667-2_8

Available on ORBi :

since 17 January 2019

Statistics

Number of views

46 (4 by ULiège)

Number of downloads

103 (0 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

See more details

Bibliography

Blondin Massé, A., de Carufel, J., Goupil, A., Lapointe, M., Nadeau, É., Van-domme, É.: Fully leafed induced subtrees (2017). arXiv.org/abs/1709.09808
Blondin Massé, A., de Carufel, J., Goupil, A., Samson, M.: Fully leafed tree-like polyominoes and polycubes. In: Brankovic, L., Ryan, J., Smyth, W.F. (eds.) IWOCA 2017. LNCS, vol. 10765, pp. 206–218. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78825-8 17
Blondin Massé, A., Nadeau, É.: Fully leafed induced subtrees, GitHub Repository. https://github.com/enadeau/fully-leafed-induced-subtrees
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)

Name	Provider / Domaine	Expiration	Description
JSESSIONID	Oracle Corporation www.uliege.be	Session	General purpose platform session cookie, used by sites written in JSP. Usually used to maintain an anonymous user session by the server.
CookieScriptConsent	CookieScript .uliege.be	1 year	This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.

Name	Provider / Domaine	Expiration	Description
_pk_id	InnoCraft Ltd .uliege.be	1 year	Used to store a few details about the user such as the unique visitor ID
_pk_ses	InnoCraft Ltd .uliege.be	30 minutes	Short lived cookies used to temporarily store data for the visit
_pk_ref	InnoCraft Ltd .uliege.be	6 months	Used to store the attribution information, the referrer initially used to visit the website