Hi Johan and Doug and Josh:

The Mendelzon paper is in:

/proj/adaptive/www/related-work/toronto/siam-graphs-automata.ps

From Garey and Johnson:

subgraph homeomorphism problem

instance: graph G = (V,E)
question: does G contain a subgraph homeomorphic to H, i.e.,
a subgraph G'=(V',E') that can be converted to a graph isomorphic to H by
repeatedly removing any vertex of degree 2
and adding the edge joining its two neighbors?

Below are recent references.
The problem is NP-complete in general when H is variable.
But notice below Chu-Algs-87 that the problem is solvable in polynomial time
for trees. Many of our strategies are trees.

Is the following correct? We assume the strategy graphs don't have
constraint maps for now.

Strategy s1 is a substrategy of strategy s2 iff s1 contains
a subgraph homeomorphic to s2?

-- Karl
======================================

@article{Asa-TCS-85,
  title = {{An approach to the subgraph homeomorphism problem}},
    author = {Tetsuo Asano},
      journal = {Theoretical Computer Science},
	volume = {38},
	  pages = {249--267},
	    year = {1985},
	      abstract = {The subgraph homeomorphism problem for a fixed pattern graph $H$ is stated as follows: given an input graph $G=(V, E)$, determine whether $G$ has a subgraph homeomorphic to $H$. The author shows that the subgraph homeomorphism problem for the fixed graph $K_3,3$ is solvable in polynomial time, where $K_3,3$ is the Thomsen graph, one of the Kuratowski graphs used to characterize planar graphs. Specifically, the author presents an $O(|V|)$-time algorithm for this problem. This problem was suspected to be NP-complete by Fortune, Hopcroft and Wyllie (1980). He also presents several pattern graphs for each of which an $O(|B|)$-time algorithm exists.}}

@article{Chu-Algs-87,
  title = {{$O(N^{2.5})$ time algorithms for the subgraph homeomorphism problem on trees}},
    author = {Moon Jung Chung},
      journal = {J. Algorithms},
	volume = {8},
	  pages = {106--112},
	    year = {1987},
	      abstract = {The complexity of the subgraph homeomorphism problems have been open. The author shows $O(n^2.5)$ time algorithms when the problems are restricted to trees, directed or undirected. The algorithm can be applied to the subtree isomorphism problem for unrooted trees with the same complexity, and improves over S. W. Reyner's $O(n^3.5)$ algorithm (see SIAM J. Comput., vol.6, p.730-2, 1977) for the subtree isomorphism problem.}}

@article{ForHopWyl-TCS-80,
title = {{The directed subgraph homeomorphism problem}},
author = {S. Fortune and John Hopcroft and J. Wyllie},
journal = {Theoretical Computer Science},
volume = {10},
pages = {111--121},
year = {1980},
abstract = {The set of pattern graphs for which the fixed directed subgraph homeomorphism problem is NP-complete is characterized. A polynomial time algorithm is given for the remaining cases. The restricted problem where the input graph is a directed acyclic graph is in polynomial time for all pattern graphs and an algorithm is given.}}

@article{LaPRiv-JCSS-80,
title = {{The subgraph homeomorphism problem}},
author = {A. S. LaPaugh and Ronald L. Rivest},
journal = {J. Computer {\&} System Sciences},
volume = {20},
pages = {133--149},
year = {1980},
abstract = {Investigates the problem of finding a homeomorphic image of a 'pattern' graph H in a larger input graph G. The authors view this problem as finding specified sets of edge disjoint or node disjoint paths in G. The main result is a linear time algorithm to determine if there exists a simple cycle containing three given nodes in G (here H is a triangle). No polynomial time algorithm for this problem was previously known. They also discuss a variety of reductions between related versions of this problem and a number of open problems.}}