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

This question shows that Vasek ChvatalVašek Chvátal is a hero.

Reduce from graph kernel.

In the GRAPH KERNELGRAPH KERNEL problem, the input data is a digraph and the task is to determine whether it has a kernel.

A kernel of a digraph is a subset $S$ of its vertex set which satisfies (i)(i) no two vertices osof $S$ are adjacent, and (ii)(ii) for every vertex not in $S$ there exists an arc from some vertexinvertex in $S$ pointing to it.

So, we need to transform a digraph to your set matrixset matrix problem.

For each original vertex, create an element. Call these elements vertex-elements. Denote this set of element by $V$.

For each original arc, create an element. Call these elements arc-elements.

Now, to ensure T$T$ is an independent set in this digraph. For each arc-elemnentelement $a=(u,v)$, set $A[u,a]=V\setminus\{v\}$ and $A[v,a]=V\setminus\{u\}$. Also, just in case none of $u$ and $v$ is included in $T$, for every $w\neq u, v$, set $A[w,a]=V\setminus\{u,v\}$.

To ensure $T$ is a dominating set in a digraph, for each arc $a=(u,v)$ set $A[u,v]=V$

All the other entries of $A$ are set to $\emptyset$.

This question shows that Vasek Chvatal is a hero.

Reduce from graph kernel.

In the GRAPH KERNEL problem, the input data is a digraph and the task is to determine whether it has a kernel.

A kernel of a digraph is a subset $S$ of its vertex set which satisfies (i) no two vertices os $S$ are adjacent, and (ii) for every vertex not in $S$ there exists an arc from some vertexin $S$ pointing to it.

So, we need to transform a digraph to your set matrix problem.

For each original vertex, create an element. Call these elements vertex-elements. Denote this set of element by $V$.

For each original arc, create an element. Call these elements arc-elements.

Now, to ensure T is an independent set in this digraph. For each arc-elemnent $a=(u,v)$, set $A[u,a]=V\setminus\{v\}$ and $A[v,a]=V\setminus\{u\}$. Also, just in case none of $u$ and $v$ is included in $T$, for every $w\neq u, v$, set $A[w,a]=V\setminus\{u,v\}$.

To ensure $T$ is a dominating set in a digraph, for each arc $a=(u,v)$ set $A[u,v]=V$

All the other entries of $A$ are set to $\emptyset$.

This question shows that Vašek Chvátal is a hero.

Reduce from graph kernel.

In the GRAPH KERNEL problem, the input data is a digraph and the task is to determine whether it has a kernel.

A kernel of a digraph is a subset $S$ of its vertex set which satisfies (i) no two vertices of $S$ are adjacent, and (ii) for every vertex not in $S$ there exists an arc from some vertex in $S$ pointing to it.

So, we need to transform a digraph to your set matrix problem.

For each original vertex, create an element. Call these elements vertex-elements. Denote this set of element by $V$.

For each original arc, create an element. Call these elements arc-elements.

Now, to ensure $T$ is an independent set in this digraph. For each arc-element $a=(u,v)$, set $A[u,a]=V\setminus\{v\}$ and $A[v,a]=V\setminus\{u\}$. Also, just in case none of $u$ and $v$ is included in $T$, for every $w\neq u, v$, set $A[w,a]=V\setminus\{u,v\}$.

To ensure $T$ is a dominating set in a digraph, for each arc $a=(u,v)$ set $A[u,v]=V$

All the other entries of $A$ are set to $\emptyset$.

Source Link
Thinh D. Nguyen
  • 2.3k
  • 3
  • 24
  • 71

This question shows that Vasek Chvatal is a hero.

Reduce from graph kernel.

In the GRAPH KERNEL problem, the input data is a digraph and the task is to determine whether it has a kernel.

A kernel of a digraph is a subset $S$ of its vertex set which satisfies (i) no two vertices os $S$ are adjacent, and (ii) for every vertex not in $S$ there exists an arc from some vertexin $S$ pointing to it.

So, we need to transform a digraph to your set matrix problem.

For each original vertex, create an element. Call these elements vertex-elements. Denote this set of element by $V$.

For each original arc, create an element. Call these elements arc-elements.

Now, to ensure T is an independent set in this digraph. For each arc-elemnent $a=(u,v)$, set $A[u,a]=V\setminus\{v\}$ and $A[v,a]=V\setminus\{u\}$. Also, just in case none of $u$ and $v$ is included in $T$, for every $w\neq u, v$, set $A[w,a]=V\setminus\{u,v\}$.

To ensure $T$ is a dominating set in a digraph, for each arc $a=(u,v)$ set $A[u,v]=V$

All the other entries of $A$ are set to $\emptyset$.