Karp hardness of a vector system allocation

Question

Given an undirected graph $G(V,E)$, a vector system is a set $S$ of ordered pair (intuitively called vector) $(u,v)$ (we shall call $u$ the initial point, and $v$ the terminal point) that satisfies the following criteria:

• For each vector $(u,v)\in S$, we have that $uv \in E(G)$. So, each vector must be an orientation of an edge

• No two vectors share the same initial point. Formally, for every two vectors $(u,v),(w,x)\in S$, we have that $u\neq w$

• An initial point of a vector cannot be the terminal point of other vector. Formally, for every two vectors $(u,v),(w,x)\in S$, we have that $v\neq w$

Now, our problem is defined as follows:

Input: An undirected graph $G(V, E)$ and a natural number $k$

Output: YES if it is possible to allocate a vector system of size $k$ in $G$, otherwise NO

What is the hardness of this problem?

Answer 1

Omitting the second requirement (allowing vectors to share initial points):

This becomes $\mathrm{NP}$-complete since it is exactly $\mathrm{MAX}$-$\mathrm{CUT}$.

Consider the set of all terminal points of the vector system. Exclude all the edges between any two vertices of this set. All the edges inwards constitute the cut.

Putting back the second requirement (vectors required not to share inital points)

This is $\mathrm{NP}$-complete by a reduction from $\mathrm{DOMINATING\ SET}$.

Reverse the direction of the vector system.

We see that now the set of initial points (originally terminal points) are dominating the set of terminal points (originally initial points). Note that these two sets are disjoint.

So, given an instance $(G,k)$ of $\mathrm{DOMINATING\ SET}$. Our reduction just produces $(G,n-k)$ where $n=|V(G)|$ as an instance of the vector allocation system.

If there is a dominating set of size $k$, then for each of the dominated $n-k$ vertices, we can assign for it a dominating vertex among $k$ dominating vertices. The direction is from the dominating vertex to the dominated vertex (this is the reversed direction). We have formed a (reversed) vector system of size $n-k$.

Conversely, if there exists a vector system of size $n-k$. The set of terminal points (originally initial points) are of size exactly $n-k$. Take the remaining $k$ vertices as a dominating set. This shows that the original instance of $\mathrm{DOMINATING\ SET}$ is a YES instance.