Given an undirected graph @math and a fixed "pattern" graph @math with @math vertices, we consider the @math -Transversal and @math -Packing problems. The former asks to find the smallest @math such that the subgraph induced by @math does not have @math as a subgraph, and the latter asks to find the maximum number of pairwise disjoint @math -subsets @math such that the subgraph induced by each @math has @math as a subgraph. We prove that if @math is 2-connected, @math -Transversal and @math -Packing are almost as hard to approximate as general @math -Hypergraph Vertex Cover and @math -Set Packing, so it is NP-hard to approximate them within a factor of @math and @math respectively. We also show that there is a 1-connected @math where @math -Transversal admits an @math -approximation algorithm, so that the connectivity requirement cannot be relaxed from 2 to 1. For a special case of @math -Transversal where @math is a (family of) cycles, we mention the implication of our result to the related Feedback Vertex Set problem, and give a different hardness proof for directed graphs.
For arbitrary graphs G and H, a G-factor of H is a spanning subgraph of H composed of disjoint copies of G. G-factors are natural generalizations of l-factors (or perfect matchings), in which G replaces the complete graph on two vertices. Our results show that the perfect matching problem is essentially the only instance of the G-factor problem that is likely to admit a polynomial time bounded solution. Specifically, if G has any component with three or more vertices then the existence question for G-factors is NP-complete. (In all other cases the question can be resolved in polynomial time.) .br The notion of a G-factor is further generalized by replacing G by an arbitrary family of graphs. This generalization forms the foundation for an extension of the traditional theory of matching. This theory, whose details will be developed elsewhere, includes, in addition to further NP-completeness results, new polynomial algorithms and simple duality results. Some indication of the nature and scope of this theory are presented here. An H-decomposition of a graph G=(V,E) is a partition of E into subgraphs isomorphic to H. Given a fixed graph H, the H-decomposition problem is to determine whether an input graph G admits an H-decomposition. In 1980, Holyer conjectured that H-decomposition is NP-complete whenever H is connected and has three edges or more. Some partial results have been obtained since then. A complete proof of Holyer's conjecture is the content of this paper. The characterization problem of all graphs H for which H-decomposition is NP-complete is hence reduced to graphs where every connected component contains at most two edges. We consider the following class of problems: given a graph, find the maximum number of nodes inducing a subgraph that satisfies a desired property π, such as planar, acyclic, bipartite, etc. We show that this problem is hard to approximate for any property π on directed or undirected graphs that is nontrivial and hereditary on induced subgraphs.