Exact and Approximate Digraph Bandwidth

Abstract Note: Please see pdf for full abstract with equations. In this paper, we introduce a directed variant of the classical BANDWIDTH problem and study it from the view-point of moderately exponential time algorithms, both exactly and approximately. Motivated by the definitions of the directed variants of the classical CUTWIDTH and PATHWIDTH problems, we define DIAGRAPH BANDWIDTH as follows. Given a digraph D and an ordering σ of its vertices, the digraph bandwidth of σ with respect to D is equal to the maximum value of σ(v) − σ(u) over all arcs (u, v) of D going forward along σ (that is, when σ(u) < σ(v)). The DIAGRAPH BANDWIDTH problem takes as input a digraph D and asks to output an ordering with the minimum digraph bandwidth. The undirected BANDWIDTHeasily reduces to DIAGRAPH BANDWIDTH and thus, it immediately implies that DIAGRAPH BANDWIDTH is NP-hard. While an O⋆(n!)∗ time algorithm for the problem is trivial, the goal of this paper is to design algorithms for DIAGRAPH BANDWIDTH which have running times of the form 2O(n). In particular, we obtain the following results. Here, n and m denote the number of vertices and arcs of the input digraph D, respectively. • DIAGRAPH BANDWIDTH can be solved in O⋆(3n · 2m) time. This result implies a 2O(n) time algorithm on sparse graphs, such as graphs of bounded average degree (planar graphs). • Let G be the underlying undirected graph of the input digraph. If the treewidth of G is at most t, then DIAGRAPH BANDWIDTH can be solved in time O⋆(2n+(t+2) log n). This result implies a 2n+O(√ n log n) algorithm, for directed planar graphs and, in general, for the class of digraphs whose underlying undirected graph excludes some fixed graph H as a minor. • DIAGRAPH BANDWIDTH can be solved in min{O∗(4n · bn),O∗(4n · 2b log b log n)} time, where b denotes the optimal digraph bandwidth of D. This allow us to deduce a 2O(n) algorithm in many cases, for example when b ≤ n / log2n. • Finally, we give a (Single) Exponential Time Approximation Scheme for DIAGRAPH BANDWIDTH. In particular, we show that for any fixed real ϵ > 0, we can find an ordering whose digraph bandwidth is at most (1+ϵ) times the optimal digraph bandwidth, in time O∗(4n · (⌈4/ϵ⌉)n). ∗The O⋆ notation hides the polynomial factors in the instance size.