On probe permutation graphs Original Research Article

Given a class of graphs image, a graph image is a probe graph of image if its vertices can be partitioned into two sets, image, the probes, and an independent set image, the nonprobes, such that image can be embedded into a graph of image by adding edges between certain vertices of image. If the partition of the vertices into probes and nonprobes is part of the input, then we call the graph a partitioned probe graph of image. In this paper, we provide a recognition algorithm for partitioned probe permutation graphs with time complexity image, where image is the number of vertices of the input graph. We show that a probe permutation graph has at most image minimal separators. As a consequence, for probe permutation graphs there exist polynomial-time algorithms solving problems like treewidth and minimum fill-in. We also characterize those graphs for which the probe graphs must be weakly chordal.