We investigate the problem of finding a homeomorphic image of a "pattern" graph H in a larger input graph G. We view this problem as finding specified sets of edge disjoint or node disjoint paths in G. Our 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. We also discuss a variety of reductions between related versions of this problem and a number of open problems.
|Original language||English (US)|
|Number of pages||11|
|Journal||Proceedings of the Annual ACM Symposium on Theory of Computing|
|State||Published - May 1 1978|
|Event||10th Annual ACM Symposium on Theory of Computing, STOC 1978 - San Diego, United States|
Duration: May 1 1978 → May 3 1978
All Science Journal Classification (ASJC) codes