6
The problem is $NP$-complete by reduction from $3$-SAT. In the reduction, the goal will be to have at least one vertex of each labeled class left.
For every variable, we create $2$ vertices linked by an edge that have unique colors. Which of these two vertices we delete will determine the truth value of this variable. We create an additional copy of this ...
3
Create a new graph $G' = (W,F)$ as follows:
For every every $v\in V$, create three vertices $v_0,v_1,v_2$ in $W$. The index $i$ in $v_i$ represents the fact that any path to this vertex uses exactly $i$ red edges.
For every edge $(u,v)\in E\setminus E'$, create the edges $(u_0,v_0)$, $(u_1,v_1)$ and $(u_2,v_2)$ in $F$.
For every edge $(u,v)\in E'$, create ...
1
You can prove this by a reduction from the Hitting Set problem (which is NP-Complete):
Given a base set $U$, a family $F = \{S_1,\ldots,S_\ell\}$ of subsets of $U$ and an integer $q$, decide if there exists a set $H$ of size at most $q$ which intersects every set in $F$ (this is called a hitting set).
So suppose given an instance of the Hitting Set ...
1
If you think it's false, the easiest way to disprove it would be to find a counterexample. That is, find a graph where $E \leq \frac{1}{2}(V-1)(V-2)$. Try some easy connected graphs (e.g. a straight-line path graph) and see if you can find a suitable graph.
1
These are called the connected components of the graph.
For most purposes, any graph traversal algorithm will suffice for finding the connected components. However, if you have a really big graph, see this question on Stack Overflow for practical considerations.
1
As Juho already mentioned, Breadth First Search is a good choice but whether it is or not the most appropriate algorithm depends upon other factors. In the following I'm assuming that your graph $G(V, E)$ has been given explicitly, and that two vertices $s, t\in V$ are also known upfront.
First, note that Breadth First Search requires an amount of memory ...
1
At least in theory, the most appropriate algorithm is breadth-first search (BFS), which you execute by starting from your source vertex $s$. Once the BFS traversal hits your target vertex $t$, you halt and trace back a chain of predecessors originating from $t$. This procedure runs in linear time, which is optimal.
However, from a practical standpoint, the ...
Only top voted, non community-wiki answers of a minimum length are eligible
