The algorithmic use of hypertree structure and maximum neighbourhood orderings

The use of (generalized) tree structure in graphs is one of the main topics in the field of efficient graph algorithms. The well-known partial k-tree (resp. treewidth) approach belongs to this kind of research and bases on a tree structure of constant-size bounded maximal cliques. Without size bound on the cliques this tree structure of maximal cliques characterizes chordal graphs which are known to be important also in connection with relational database schemes where hypergraphs with tree structure (acyclic hypergraphs) and their elimination orderings (perfect elimination orderings for chordal graphs, Graham-reduction for acyclic hypergraphs) are studied. We consider here graphs with a tree structure which is dual (in the sense of hypergraphs) to that one of chordal graphs (therefore we call these graphs dually chordal). The corresponding vertex elimination orderings of these graphs are the maximum neighbourhood orderings. These orderings were studied recently in several papers and some of the algorithmic consequences of such orderings are given. The aim of this paper is a systematic treatment of the algorithmic use of maximum neighbourhood orderings. These orderings are useful especially for dominating-like problems (including Steiner tree) and distance problems. Many problems efficiently solvable for strongly chordal and doubly chordal graphs remain efficiently solvable for dually chordal graphs too. Our results on dually chordal graphs not only generalize, but also improve and extend the corresponding results on strongly chordal and doubly chordal graphs, since a maximum neighbourhood ordering (if it exists) can be constructed in linear time and we consequently use the underlying structure properties of dually chordal graphs closely connected to hypergraphs. Furthermore, a collection of problems remaining NP-complete on dually chordal graphs is given. (C) 1998 Elsevier Science B.V. All rights reserved.