Chordless Paths, Odd Holes, and Kernels in Graphs Without m-Obstructions

✍ Scribed by F. Gavril; V.T. Laredo; D. Dewerra

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 689 KB
• Volume: 17
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1994.1031

✦ Synopsis

An (m)-obstruction in a directed graph (\mathbf{G}(V, \mathbf{E})) is a chordless simple path (x_{1}, x_{2}, \ldots, x_{m+2}) having (x_{1} \rightarrow x_{2}, x_{m+2} \rightarrow x_{m+1} \in \mathbf{E}). A directed graph is fraternally oriented if it has no 1 -obstructions and it is perfectly oriented if it has no 2 -obstructions. A directed graph is normal if it has no directed triangles. We describe polynomial time algorithms for the recognition of a chordless directed path of a given parity between two vertices in a directed graph without (m)-obstructions, and when (m=2^{q}), for the recognition of odd holes. These are used to test whether a normal fraternally or perfectly oriented graph is perfect (assuming the Strong Perfect Graph Conjecture). In addition, we describe a polynomial time algorithm to find a kernel in a normal fraternally oriented graph using a structural characterization of the subgraph generated by two kernels. § 1994 Academic Press, Inc.