Bandwidth on AT-free graphs

We study the classical Bandwidth problem from the viewpoint of parametrised algorithms. Given a graph G = ( V, E ) and a positive integer k, the Bandwidth problem asks whether there exists a bijective function β: { 1, …, ∣ V ∣ } → V such that for every edge u v ∈ E, ∣ β − 1 ( u ) − β − 1 ( v ) ∣ ≤ k. It is known that under standard complexity assumptions, no algorithm for Bandwidth with running time of the form f ( k ) n O ( 1 ) exists, even when the input is restricted to trees. We initiate the search for classes of graphs where such algorithms do exist. We present an algorithm with running time n ⋅ 2 O ( k log k ) for Bandwidth on AT-free graphs, a well-studied graph class that contains interval, permutation, and cocomparability graphs. Our result is the first non-trivial algorithm that shows fixed-parameter tractability of Bandwidth on a graph class on which the problem remains NP -complete.

Authors

• Petr Golovach University of Bergen
• Pinar Heggernes
• Dieter Kratsch
• Daniel Lokshtanov
• Daniel Meister
• Saket Saurabh

Keywords

• Algorithm
• Fixed-parameter tractable
• Bandwidth
• AT-free graph