From lieber@ccs.neu.edu Fri Jun 26 20:35:01 1998
Received: from stockberg.ccs.neu.edu (lieber@stockberg.ccs.neu.edu [129.10.116.114])
	by amber.ccs.neu.edu (8.8.6/8.8.6) with ESMTP id UAA03829;
	Fri, 26 Jun 1998 20:35:00 -0400 (EDT)
From: Karl Lieberherr <lieber@ccs.neu.edu>
Received: (from lieber@localhost)
	by stockberg.ccs.neu.edu (8.8.6/8.8.6) id UAA25632;
	Fri, 26 Jun 1998 20:35:43 -0400 (EDT)
Date: Fri, 26 Jun 1998 20:35:43 -0400 (EDT)
Message-Id: <199806270035.UAA25632@stockberg.ccs.neu.edu>
To: dougo@ccs.neu.edu, lieber@ccs.neu.edu
Subject: Re: subgraph homeomorphism
Cc: jayantha@ccs.neu.edu, johan@ccs.neu.edu
Status: R

Hi Doug:

>From dougo@ccs.neu.edu Wed Jun 24 17:00:57 1998
>From: Doug Orleans <dougo@ccs.neu.edu>
>To: Karl Lieberherr <lieber@ccs.neu.edu>
>Cc: jayantha@ccs.neu.edu, johan@ccs.neu.edu
>Subject: Re: subgraph homeomorphism
>
>Karl Lieberherr writes:
> > 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.
>
>What about DAGs?  Pretty much all of our strategies are DAGs, and I
>have yet to see a practical use for a cyclic strategy graph.
>

I think the answer is in:

@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 home
omorphism problem is NP-complete is characterized. A polynomial time algorithm i
s 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 al
 gorithm is given.}} 

The way I read this:

Given a strategy graph S1 which is acyclic (i.e., a dag) and a
substrategy S2 it is polynomial to check whether S2 contains a subgraph
homeomorphic to S1. Is this the same as "S2 is a substrategy of S1"?
The problem might be with "contains".

We also have to check how fast the algorithm is.

Johan: please can you get the paper and make a copy for you, Doug and me.

>
> > 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?
>
>I think you want to replace "contains a subgraph" with "is".
>Otherwise you could have extra nodes in s1 that aren't in s2.
>
>--Doug
>

Yeah, we have to check that with ForHopWyl-TCS-80.

-- Karl