An algorithmic Friedman-Pippenger theorem on tree embeddings and applications
type: Item
instance of: scholarly article
title: An algorithmic Friedman-Pippenger theorem on tree embeddings and applications
zbMATH Open document ID: 1165.05318
author: Domingos Dellamonica
author: Yoshiharu Kohayakawa
published in: The Electronic Journal of Combinatorics
publication date: 2009-04-07T00:00:00Z
full work available at URL: https://eudml.org/doc/130279
full work available at URL: v15i1r127.html
review text: Summary: An \((n, d)\)-expander is a graph \(G = (V, E)\) such that for every \(X \subseteq V\) with\(|X| \leq 2n - 2\) we have \(|\Gamma_G(X)| \geq (d+1)|X|\). A tree \(T\) is small if it has at most \(n\) vertices and has maximum degree at most \(d\). \textit{J. Friedman} and \textit{N. Pippenger} [Combinatorica 7, 71--76 (1987; Zbl 0624.05028)] proved that any\((n, d)\)-expander contains every small tree. However, their elegant proof does not seem to yield an efficient algorithm for obtaining the tree. In this paper, we give an alternative result that does admit a polynomial time algorithm for finding the immersion of any small tree in subgraphs \(G\) of \((N,D,\lambda)\)-graphs \(\Lambda\), as long as \(G\) contains a positive fraction of the edges of \(\Lambda\) and \(\lambda/D\) is small enough. In several applications of the Friedman--Pippenger theorem, including the ones in the original paper of those authors, the \((n,d)\)-expander \(G\) is a subgraph of an \((N,D,\lambda)\)-graph as above. Therefore, our result suffices to provide efficient algorithms for such previously non-constructive applications. As an example, we discuss a recent result of \textit{N. Alon}, \textit{M. Krivelevich}, and \textit{B. Sudakov} [Combinatorics 27, No.\,6, 629--644 (2007; Zbl 1164.05032)] concerning embedding nearly spanning bounded degree trees, the proof of which makes use of the Friedman--Pippenger theorem. We shall also show a construction inspired on Wigderson--Zuckerman expander graphs for which any sufficiently dense subgraph contains all trees of sizes and maximum degrees achieving essentially optimal parameters. Our algorithmic approach is based on a reduction of the tree embedding problem to a certain on-line matching problem for bipartite graphs, solved by Aggarwal et al.(1996).
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 5541032
zbMATH Keywords: expander
zbMATH Keywords: tree embedding problem
zbMATH Keywords: matching problem for bipartite graphs
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5541032