### Abstract

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) |
---|---|

Pages (from-to) | 40-50 |

Number of pages | 11 |

Journal | Proceedings of the Annual ACM Symposium on Theory of Computing |

DOIs | |

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

- Software

## Fingerprint Dive into the research topics of 'The subgraph homeomorphism problem'. Together they form a unique fingerprint.

## Cite this

La Paugh, A. S., & Rivest, R. L. (1978). The subgraph homeomorphism problem.

*Proceedings of the Annual ACM Symposium on Theory of Computing*, 40-50. https://doi.org/10.1145/800133.804330