Skip to main content
added 1269 characters in body
Source Link
Thinh D. Nguyen
  • 2.3k
  • 3
  • 24
  • 71

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

This isbecomes $\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.

This is $\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.

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.

Post Undeleted by Thinh D. Nguyen
Post Deleted by Thinh D. Nguyen
Source Link
Thinh D. Nguyen
  • 2.3k
  • 3
  • 24
  • 71

This is $\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.