On Finding Paths Passing through Specified Vertices

Abstract

We consider undirected finite graphs that have no loops and no multiple edges. A graph is denoted G = (VG, EG), where VG is the set of vertices and EG is the set of edges. A graph containment problem is to decide whether one graph can be modified into some other graph by using a number of specified graph operations. For example, by allowing any combination of the four operations edge deletions, edge contractions, vertex deletions and vertex dissolutions the following containment problems are captured: testing on (induced) minors, (induced) topological minors, (induced) subgraphs, induced spanning subgraphs, dissolutions and contractions. Algorithms for detecting specific induced subgraphs such as paths and cycles have been proven to be useful in the design of algorithms that solve more general graph containment problems. We will discuss one open problem in this area and give a potential application afterwards. We first state some terminology required. Two (not necessarily induced) paths P and Q in a graph G are called mutually induced if the following two conditions are both satisfied: (i) P and Q are vertex-disjoint; (ii) G has no edges with one end-vertex in P and the other one in Q.