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 ...
3
Let $n := |V| = rk$ be the total number of vertices in the graph. Basically, we are looking for a partition of $V$ into $r$ sets each of size $k$. The total cost will be then the sum of the weights of all edges present in the graph induced by each of these sets. Note that the edges having one end in one of these sets and the other endpoint in another set ...
2
An easy contradicting example is three points forming an obtuse triangle. Note that any Axis-parallel square containing $A$ and $B$ on its boundaries, contains $C$ in its interior and hence, the outer face is not bounded by a cycle since $AB$ is not an edge in the graph.
2
The minimum number of vertices that have to be removed in order to disconnect the graph is known at the connectivity of the graph. Wikipedia outlines an algorithm for finding the connectivity of a graph. More efficient algorithms might exist.
A related problem is the vertex separator problem, in which we want to disconnect two specific vertices by removing ...
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.
Only top voted, non community-wiki answers of a minimum length are eligible
