Exact and Approximate Digraph Bandwidth

Abstract In this paper, we introduce a directed variant of the classical Bandwidthproblem 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 Digraph Bandwidth as follows. Given a digraph $$\varvec{D}$$ D and an ordering $$\varvec{\sigma }$$ σ of its vertices, the digraph bandwidth of $$\varvec{\sigma }$$ σ with respect to $$\varvec{D}$$ D is equal to the maximum value of $$\varvec{\sigma (v)}-\varvec{\sigma (u)}$$ σ ( v ) - σ ( u ) over all arcs $$\varvec{(u,v)}$$ ( u , v ) of $$\varvec{D}$$ D going forward along $$\varvec{\sigma }$$ σ (that is, when $$\varvec{\sigma (u)} < \varvec{\sigma (v)}$$ σ ( u ) < σ ( v ) ). The Digraph Bandwidth problem takes as input a digraph $$\varvec{D}$$ D and asks to output an ordering with the minimum digraph bandwidth. The undirected Bandwidtheasily reduces to Digraph Bandwidth and thus, it immediately implies that Digraph Bandwidth is -hard. While an $$\varvec{\mathcal {O}}^{\star }\varvec{(n!)}$$ O ⋆ ( n ! ) time algorithm for the problem is trivial, the goal of this paper is to design algorithms for Digraph Bandwidth which have running times of the form $$\varvec{2}^{\varvec{\mathcal {O}(n)}}$$ 2 O ( n ) . In particular, we obtain the following results. Here, $$\varvec{n}$$ n and $$\varvec{m}$$ m denote the number of vertices and arcs of the input digraph $$\varvec{D}$$ D , respectively. Digraph Bandwidth can be solved in $$\varvec{\mathcal {O}}^\star (\varvec{3}^{\varvec{n}} \cdot \varvec{2}^{\varvec{m}})$$ O ⋆ ( 3 n · 2 m ) time. This result implies a $$\varvec{2}^{\varvec{\mathcal {O}}(\varvec{n})}$$ 2 O ( n ) time algorithm on sparse graphs, such as graphs of bounded average degree (planar graphs). Let $$\varvec{G}$$ G be the underlying undirected graph of the input digraph. If the treewidth of $$\varvec{G}$$ G is at most $$\varvec{t}$$ t , then Digraph Bandwidth can be solved in time $$\varvec{\mathcal {O}}^\star (\varvec{2}^{\varvec{n} + (\varvec{t}+\varvec{2})\, \varvec{\log }\, \varvec{n}})$$ O ⋆ ( 2 n + ( t + 2 ) log n ) . This result implies a $$\varvec{2}^{\varvec{n}+\varvec{\mathcal {O}}(\sqrt{\varvec{n}}\, \varvec{\log }\, \varvec{n})}$$ 2 n + 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 $$\varvec{H}$$ H as a minor. Digraph Bandwidth can be solved in $$\varvec{\min } \{ \varvec{\mathcal {O}}^{\star }(\varvec{4}^{\varvec{n}} \cdot \varvec{b}^{\varvec{n}}), \varvec{\mathcal {O}}^{\star }(\varvec{4}^{\varvec{n}} \cdot \varvec{2}^{\varvec{b}\, \varvec{\log }\, \varvec{b}\, \varvec{\log }\, \varvec{n}})\}$$ min { O ⋆ ( 4 n · b n ) , O ⋆ ( 4 n · 2 b log b log n ) } time, where $$\varvec{b}$$ b denotes the optimal digraph bandwidth of $$\varvec{D}$$ D . This allow us to deduce a $$\varvec{2}^{\varvec{\mathcal {O}}(\varvec{n})}$$ 2 O ( n ) algorithm in many cases, for example when $$\varvec{b} \le \frac{\varvec{n}}{\varvec{\log }^{\varvec{2}}\,\varvec{n}}$$ b ≤ n log 2 n . Finally, we give a (Single) Exponential Time Approximation Scheme for Digraph Bandwidth. In particular, we show that for any fixed real $$\varvec{\epsilon } > \varvec{0}$$ ϵ > 0 , we can find an ordering whose digraph bandwidth is at most $$(\varvec{1}+\varvec{\epsilon })$$ ( 1 + ϵ ) times the optimal digraph bandwidth, in time $$\varvec{\mathcal {O}}^{{\star }}(\varvec{4}^{\varvec{n}} \cdot (\lceil \varvec{4}/{\varvec{\epsilon }} \rceil )^n)$$ O ⋆ ( 4 n · ( ⌈ 4 / ϵ ⌉ ) n ) .