patternMinor
Largest weight-limited connected subgraph: NP-complete?
Viewed 0 times
weightlargestcompleteconnectedlimitedsubgraph
Problem
When playing Terra Mystica, it might be useful to predict how many spades you will get throughout the game, and use this information to decide where to build, such that you stand a good chance of having the longest network. Let's abstract that into the following problem:
Your goal is to find a set of vertices $V^*$ such that:
The decision version takes a threshold parameter $k$ and asks "is there a vertex set $T$ with size $|T| \geq k$ and which satisfies the first two criteria?"
What is the complexity of this problem? By eyeball, it's obviously in NP; is it NP-complete? Is it well-studied under some name unknown to me?
- Let a graph $G$ be given, $G = (V, E)$.
- Associate a terraforming cost with each vertex, $C : V \mapsto \{0, 1, 2, 3\}$.
- You're given some number of spades, $s$.
Your goal is to find a set of vertices $V^*$ such that:
- You can afford to build on all of them, $\Sigma_{v \in V^*} C(v) \leq s$
- They're all next to each other: the graph $(V^, V^ \times V^* \cap E)$ is connected.
- It is the largest such set: for all $V'$ which satisfy the previous conditions, $|V^*| \geq |V'|$.
The decision version takes a threshold parameter $k$ and asks "is there a vertex set $T$ with size $|T| \geq k$ and which satisfies the first two criteria?"
What is the complexity of this problem? By eyeball, it's obviously in NP; is it NP-complete? Is it well-studied under some name unknown to me?
Solution
The decision version is NP-complete so the problem is NP-hard. The following is a reduction from 3SAT.
For an instance of 3SAT with $n$ variables $x_1,\ldots, x_n$ and $m$ clauses, create a graph as follows:
-
For each variable $x_i$ create two vertices $v_i^0, v_i^1$ with cost $1$. Create an edge between each two vertices of these $2n$ vertices, i.e. the $2n$ vertices induce a clique.
-
For each variable $x_i$ create a vertex $v_i$ with cost $0$, and two edges $(v_i, v_i^0)$ and $(v_i,v_i^1)$.
-
For each clause $c_l$ with variables $x_i,x_j,x_k$, create a vertex $u_l$ with cost $0$, and three edges $(u_l, v_i^{b_i})$ (if the literal is positive, $b_i=1$, otherwise $b_i=0$, and the same below), $(u_l, v_j^{b_j})$ and $(u_l, v_k^{b_k})$.
Then we ask if there is a connected vertex set $T$ with size at least $2n+m$ and the sum of cost is no more than $n$.
Now if the instance of 3SAT has a feasible solution where $x_i=b_i$, we can make $T$ consist of all $v_i$s, $u_l$s and $v_i^{b_i}$s.
On the other hand, if $T$ exists, because you can afford at most $n$, at most $n$ vertices among $v_i^0, v_i^1$s are chosen, thus all $n+m$ vertices with cost $0$ must be chosen. This means:
-
Since $v_i$ is chosen, at least one vertex of $v_i^0$ and $v_i^1$ is chosen. Because at most $n$ vertices among $v_i^0, v_i^1$s are chosen, exactly one of $v_i^0$ and $v_i^1$ is chosen. We assign $x_i$ accordingly.
-
Since $u_l$ is chosen, at least one corresponding literal has value $1$, thus the clause is satisfied.
So the instance of 3SAT has a feasible solution.
For an instance of 3SAT with $n$ variables $x_1,\ldots, x_n$ and $m$ clauses, create a graph as follows:
-
For each variable $x_i$ create two vertices $v_i^0, v_i^1$ with cost $1$. Create an edge between each two vertices of these $2n$ vertices, i.e. the $2n$ vertices induce a clique.
-
For each variable $x_i$ create a vertex $v_i$ with cost $0$, and two edges $(v_i, v_i^0)$ and $(v_i,v_i^1)$.
-
For each clause $c_l$ with variables $x_i,x_j,x_k$, create a vertex $u_l$ with cost $0$, and three edges $(u_l, v_i^{b_i})$ (if the literal is positive, $b_i=1$, otherwise $b_i=0$, and the same below), $(u_l, v_j^{b_j})$ and $(u_l, v_k^{b_k})$.
Then we ask if there is a connected vertex set $T$ with size at least $2n+m$ and the sum of cost is no more than $n$.
Now if the instance of 3SAT has a feasible solution where $x_i=b_i$, we can make $T$ consist of all $v_i$s, $u_l$s and $v_i^{b_i}$s.
On the other hand, if $T$ exists, because you can afford at most $n$, at most $n$ vertices among $v_i^0, v_i^1$s are chosen, thus all $n+m$ vertices with cost $0$ must be chosen. This means:
-
Since $v_i$ is chosen, at least one vertex of $v_i^0$ and $v_i^1$ is chosen. Because at most $n$ vertices among $v_i^0, v_i^1$s are chosen, exactly one of $v_i^0$ and $v_i^1$ is chosen. We assign $x_i$ accordingly.
-
Since $u_l$ is chosen, at least one corresponding literal has value $1$, thus the clause is satisfied.
So the instance of 3SAT has a feasible solution.
Context
StackExchange Computer Science Q#93877, answer score: 3
Revisions (0)
No revisions yet.