New insights on GA-H reduced graphs

Let GA be a hereditary family of graphs and H a family of acyclically directed graphs. A graph G(V,E) is a GA-H reduced graph if it can be obtained from a graph GA(V,D)∈GA by deleting the edges of an edge subgraph H(V,E′)∈H. The present paper complements reference [9] by proving that the following properties are equivalent: Property 1: u→v∈E′ implies NGA[u]⊆NGA[v]. Property 2: u→v∈E′ and v-w∉E∪E′=D implies u-w∉E∪E′=D. This equivalence implies that most of the algorithms in the above reference apply to the GA-H reduced graphs where H is the family of transitive edge subgraphs of the closed neighborhoods containment graphs of the graphs in GA. We also describe a polynomial time algorithm for maximum weight independent set under the weaker condition that H(V,E′) is a locally transitive edge subgraph of the closed neighborhoods containment graph of GA(V,D).