On integer linear programs for treewidth based on perfect elimination orderings (extended version)

Abstract We analyze integer programming formulations for determining the treewidth of a graph that are based on perfect elimination orderings. For the first time, we prove structural properties that explain their limitations in providing convenient lower bounds and show how the latter are constituted. Moreover, we investigate a flow metric approach that proved promising to achieve approximation guarantees for the pathwidth of a graph, and we show why these techniques cannot be carried over to improve the addressed treewidth formulations. In addition, we present two complementary formulations for treewidth that employ positional rather than relational variables. Via computational experiments, we provide an impression on the quality and proportionality of the lower bounds on the treewidth obtained with different relaxations of perfect elimination ordering formulations.