ON THE COMPUTATIONAL-COMPLEXITY OF ORDERED SUBGRAPH RECOGNITION

Let (G, <) be a finite graph G with a linearly ordered vertex set V. We consider the decision problem (G, <)ORD to have as an instance an (unordered) graph Gamma and as a question whether there exists a linear order < on V/(Gamma) and an order preserving graph isomorphism of (G, <) onto an induced subgraph of Gamma. Several familiar classes of graph are characterized as the yes-instances of (G, <)ORD for appropriate choices of (G, <). Here the complexity of (G, <)ORD is investigated. We conjecture that for any 2-connected graph G, G not congruent to K-k, (G, <)ORD is NP-complete. This is verified for almost all 2-connected graphs. Several related problems are formulated and discussed. (C) 1995 John Wiley & Sons, Inc.