Premium
Recognizing triangle‐free graphs with induced path‐cycle double covers is NP‐complete
Author(s) -
Jacobson Michael S.,
Kézdy André E.,
Lehel Jenő
Publication year - 1998
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199801)31:1<1::aid-net1>3.0.co;2-n
Subject(s) - combinatorics , hypergraph , mathematics , vertex (graph theory) , discrete mathematics , independent set , graph
Abstract An induced path‐cycle double cover (IPCDC) of a simple graph G is a family ℱ = { F 1 , …, F k } of induced paths and cycles of G such that if F i ∩ F j ≠ ⊘, then F i ∩ F j is a vertex or an edge, for i ≠ 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 NP‐complete by reducing the 3‐Satisfiability problem to finding an IPCDC. The dependency graph of a 3‐uniform 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. © 1998 John Wiley & Sons, Inc. Networks 31: 1–10, 1998