TR06-016 Authors: Tomas Feder, Carlos Subi

Publication: 6th February 2006 12:33

Downloads: 709

Keywords:

The $H$-matching problem asks to partition the vertices of an input graph $G$

into sets of size $k=|V(H)|$, each of which induces a subgraph of $G$

isomorphic to $H$. The $H$-matching problem has been classified as polynomial

or NP-complete depending on whether $k\leq 2$ or not. We consider a variant

of the problem, in which a homomorphism from $G$ to $H$ is given, so that

$G$ is $k$-partite, and each chosen set of size $k$ must contain exactly

one vertex from each of the $k$ parts. We classify the problem as polynomial

or NP-complete depending on whether $H$ is a forest or not.

The polynomial case with $H$ a forest generalizes to the case where each set of

size $k$ must contain a subgraph satisfying certain degree constraints,

provided that the skip between consecutive allowed degrees is at most two;

a skip of at least three gives NP-completeness. More generally, one may

specify which sets of incident edges for a vertex in the subgraph are allowed,

and the problem has complexity related to delta-matroids. Several of the

polynomial cases extend to a weighted version.

An optimization variant of the problem asks to maximize the number of chosen

sets of size $k$ that induce a subgraph isomorphic to $H$. This problem is

shown polynomial if every component of $H$ is a path, and NP-complete

otherwise. The polynomial cases extend to a weighted version, while the

NP-complete cases are hard to approximate within a constant even for bounded

degree instances, allowing a $\frac{k}{2}+\epsilon$ approximation. We similarly

classify the problem of asking that each chosen set of size $k$

contain at least $r$ edges forming a connected subgraph, for all $H$

and $r$, and nearly classify the case where the $r$ edges are not required

to form a connected subgraph.