The price of connectedness in expansions
Fedor V. Fomin, Pierre Fraigniaud, Dimitrios Thilikos Touloupas · LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas) · 2004
Expansion is the way of generalizing different graph layout and searching problems. We initiate the study of connected expansion which naturally arises in a number of applications. Our main tool for this investigation is the branchwidth of a graph. In particular, we prove that any 2-edge-connected graph of branchwidth k has a {em connected} branch decom-po-si-tion of width k, i.e., a branch decomposition in which any cut separates two edge-sets that induce two connected subgraphs. Our proof is constructive, and is inspired from the existential proof of Seymour and Thomas (1994) for carvings. We also prove that the {em connected} search number (i.e., connected pathwidth) of any n-node graph of branchwidth k is at most O(klog n) and this bound is the best possible for parameters k and n. A first consequence of these results is that, for any graph, the connected search number is at most O(log n) times larger than the (standard) search number. The only bound known so far held for trees only. Another consequence is that the connected search number can be approximated in polynomial time up to a factor O(log{n}cdotlog{OPT}). That is, for any connected graph G, one can compute in polynomial time a connected search strategy for G that uses at most O (log{n}cdotlog{OPT}) times the optimal number OPT of searchers. The ratio O(log{n}cdotlog{OPT}) is the same as the best known approximation ratio for (standard) pathwidth, and any improvement for the approximation of connected search (i.e., connected pathwidth) would indeed produce an improvement for the approximation of pathwidth.