Largest weight-limited connected subgraph: NP-complete?

Question

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:

• 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?

Answer 1

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:

1. 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.

2. 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)$.

3. 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:

1. 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.

2. 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.

Answer 2

The decision version of the Terra Mystica Network problem is NP-hard.

Hee's a reduction from $k$-MST with edge weights in $\{1, 2, 3\}$, see https://en.wikipedia.org/wiki/K-minimum_spanning_tree.

Let's recap the decision version: you're given a graph $G = (V, E)$, an edge cost function $W: E \mapsto \{1, 2, 3\}$, a target size $t$ and a cost limit $c$. An instance is a yes-instance if there exists a $t$-vertex tree with total edge lost at most $c$.

To turn this into an instance of the Terra Mystica network decision problem, add a vertex $v_e$ on the middle of each edge $e$; replace $e = \{v, w\}$ with two edges $\{v, v_e\}$ and $\{w, v_e\}$. Let $C(v_e) = W(e)$, and let $C(v) = 0$ for all $v \in V$. Also attach a path of length $|E|$ and total cost $0$ to each vertex in $V$. Let $k = t(|E|+1) + (t - 1)$ and let $s = c$.

If we can find a $k$-MST, we can easily turn it into a Terra Mystica network: simply use $v_e$ in the network for all edges $e$ used in the tree, carry over the vertices and flood-fill into the attached paths. This obeys the cost constraint because they're equal and the flood-filled vertices are free. Each vertex turned into $|E|+1$ vertices, all of which are in the solution, as are $t-1$ edges, so the total solution size is $t \cdot \left(|E|+1\right) + (t-1)$, exactly what's required. Trees are connected, so the Terra Mystica network is as well.

On the other hand, let a (connected) Terra Mystica network be given of size at least $t \cdot \left(|E|+1\right) + (t-1)$ and cost at most $s = c$. If it includes at most $t - 1$ of the vertices carried over from the $k$-MST instance, and at most all the $v_e$s, then its total size is at most $$(t-1)(|E|+1) + |E| = t|E| - |E| + t - 1 + |E| = t|E| + t - 1 = t \cdot (|E|+1) - 1 < t \cdot (|E|+1) + (t-1)$$

This is because each of the length-$|E|$ paths is only accessible through the vertices carried over from $V$. But this is impossible, as we assumed the solution size is at least $t \cdot (|E|+1) + (t-1)$.

If it has more than $t$ of the vertices from $V$, we can drop some of them while keeping the solution connected: $t$ vertices plus $t$ paths of length $|E|$ plus $(t-1)$ of the $v_e$ vertices to connect them also form a solution; we may need to flood-fill into partially included attached paths. If the solution includes more than $t-1$ of the $v_e$ vertices, we can eliminate some by computing any (e.g. a minimum-weight) spanning tree only on the vertices and edges in the solution (treating the $v_e$ vertices as edges). The solution includes at least $t-1$ of the $v_e$ vertices, else it wouldn't be connected.

Then the vertices from $V$ and the edges corresponding to the $v_e$ vertices form a $t$-vertex tree in $G$ with cost at most $c$. So if we have a solution to the Terra Mystica network problem, we also have a solution to the $k$-MST problem.

QED.

Commentary

Terra Mystica is played on the faces of a hexagon tessellation of the plane—or rather, a finite subset of such hexes. The $k$-MST problem is NP-hard for planar graphs with edge weights in $\{1, 2, 3\}$. The reduction preserves planarity. Hence, with this reduction we can (hopefully) abstract away fewer parts of Terra Mystica than with xskxzr's reduction from 3SAT, and still have a hardness result.

One step is missing: we need to be able to embed a planar graph on a hex face grid. My 15 second literature search came up empty handed, which is probably mostly to blame on its duration.

One might hope that if we can draw it this way, we can fill the "empty space" with (enough) prohibitively expensive vertices and have something that vaguely resembles a Terra Mystica board. Maybe we can even put in a river somewhere and not have the reduction fall apart.

More commentary

I reduced one constrained optimization problem to another. The decision version of a constrained optimization problem (one of maximizing $f(x)$ subject to $g(x) >= t$) becomes a constraint satisfaction problem, one of finding an $x$ such that $f(x) >= t_1$ and $g(x) >= t_2$. Hence, when looking for reduction candidates you don't have to be concerned about "oh well this one constrains on x and optimizes for y but the other problem is the other way around"—when you work with the decision versions it all becomes the same thing. It's all just constraints.