Generalized Connectors

Abstract

An n-connector is an acyclic directed graph having n inputs and n outputs and satisfying the following condition: given any one-to-one correspondence between inputs and distinct outputs, there exists a set of vertex-disjoint paths that join each input to the corresponding output. It is known that the minimum possible number of edges in an n-connector lies between lower and upper bounds that are asymptotic to $3n\log _3 n$ and $6n\log _3 n$ respectively. A generalized n-connector satisfies the following stronger condition: given any one-to-many correspondence between inputs and disjoint sets of outputs, there exists a set of vertex-disjoint trees that join each input to the corresponding set of outputs. It is shown that the minimum number of edges in a generalized n-connector is asymptotic to the minimum number in an n-connector.