Recognizing triangle-free graphs with induced path-cycle double covers is NP-complete
✍ Scribed by Jacobson, Michael S.; K�zdy, Andr� E.; Lehel, Jen?
- Publisher
- John Wiley and Sons
- Year
- 1998
- Tongue
- English
- Weight
- 250 KB
- Volume
- 31
- Category
- Article
- ISSN
- 0028-3045
No coin nor oath required. For personal study only.
✦ Synopsis
An induced path-cycle double cover (IPCDC) of a simple graph G is a family F Å {F 1 , . . . , F k } of induced paths and cycles of G such that if F i ʝ F j x M, then F i ʝ F j is a vertex or an edge, for i x j, each edge of G appears in precisely two of the F i 's, and each vertex of G appears in precisely three of the F i 's. In this paper, we prove that recognizing triangle-free simple graphs with an IPCDC is NPcomplete by reducing the 3-Satisfiability problem to finding an IPCDC. The dependency graph of a 3uniform hypergraph H Å (V, E) is the graph with vertex set E in which two hyperedges are joined if and only if they share exactly two elements. We show that a triangle-free simple graph is the dependency graph of a 3-uniform hypergraph if and only if it has an IPCDC. Consequently, the problem of recognizing dependency graphs of 3-uniform hypergraphs is NP-complete.