×

Ordering without forbidden patterns. (English) Zbl 1425.05134

Schulz, Andreas S. (ed.) et al., Algorithms – ESA 2014. 22nd annual European symposium, Wrocław, Poland, September 8–10, 2014. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 8737, 554-565 (2014).
Summary: Let \({\mathcal{F}}\) be a set of ordered patterns, i.e., graphs whose vertices are linearly ordered. An \({\mathcal{F}}\)-free ordering of the vertices of a graph \(H\) is a linear ordering of \(V(H)\) such that none of the patterns in \({\mathcal{F}}\) occurs as an induced ordered subgraph. We denote by Ord\(({\mathcal{F}})\) the decision problem asking whether an input graph admits an \({\mathcal{F}}\)-free ordering; we also use Ord\(({\mathcal{F}})\) to denote the class of graphs that do admit an \({\mathcal{F}}\)-free ordering. It was observed by P. Damaschke [in: Topics in combinatorics and graph theory. Essays in honour of Gerhard Ringel. Heidelberg: Physica-Verlag. 219–229 (1990; Zbl 0736.05065)] (and others) that many natural graph classes can be described as Ord\(({\mathcal{F}})\) for sets \({\mathcal{F}}\) of small patterns (with three or four vertices). This includes recognition of split graphs, interval graphs, proper interval graphs, cographs, comparability graphs, chordal graphs, strongly chordal graphs, and so on. Damaschke also noted that for many sets \({\mathcal{F}}\) consisting of patterns with three vertices, Ord\(({\mathcal{F}})\) is polynomial-time solvable by known algorithms or their simple modifications. We complete the picture by proving that \(all\) these problems can be solved in polynomial time. In fact, we provide a single master algorithm, which solves in polynomial time the problem Ord\(_3\) in which the input is a set \({\mathcal{F}}\) of patterns, each with at most three vertices, and a graph \(H\), and the problem is to decide whether or not \(H\) admits an \({\mathcal{F}}\)-free ordering of the vertices. Our algorithm certifies non-membership by a forbidden substructure, and thus provides a single forbidden structure characterization for all the graph classes described by some Ord\(({\mathcal{F}})\) with \({\mathcal{F}}\) consisting of patterns with at most three vertices. This includes bipartite graphs, split graphs, interval graphs, proper interval graphs, chordal graphs, and comparability graphs. Many of the problems Ord\(({\mathcal{F}})\) with \({\mathcal{F}}\) consisting of larger patterns have been shown to be NP-complete by D. Duffus et al. [Random Struct. Algorithms 7, No. 3, 223–268 (1995; Zbl 0834.68052)], and we add some additional examples.
We also discuss a bipartite version of the problem, BiOrd\(({\mathcal{F}})\), in which the input is a bipartite graph \(H\) with a fixed bipartition of the vertices, and we are given a set \({\mathcal{F}}\) of bipartite patterns. We give a unified polynomial-time algorithm for all problems BiOrd\(({\mathcal{F}})\) where \({\mathcal{F}}\) has at most four vertices, i.e., we solve the analogous problem BiOrd\(_4\). This is also a certifying algorithm, and it yields a unified forbidden substructure characterization for all bipartite graph classes described by some BiOrd\(({\mathcal{F}})\) with \({\mathcal{F}}\) consisting of bipartite patterns with at most four vertices. This includes chordal bipartite graphs, co-circular-arc bipartite graphs, and bipartite permutation graphs. We also describe some examples of digraph ordering problems and algorithms.
We conjecture that for every set \({\mathcal{F}}\) of forbidden patterns, Ord\(({\mathcal{F}})\) is either polynomial or NP-complete.
For the entire collection see [Zbl 1295.68031].

MSC:

05C75 Structural characterization of families of graphs
05C85 Graph algorithms (graph-theoretic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI arXiv