<p>In the world of approximation algorithms there is the capacitated vertex cover problem.
Given $G=(V,E)$ and integer capacities $c(v)$ for each $v \in V$ the goal is to find
a minimum sized vertex cover for $G$ where the number of edges covered by $v$ is at most $c(v)$. This problem has a constant factor approximation in the unweighted case (that is, we want to minimize the size of the vertex cover) while it is $\Omega(\log n)$-hard (unless $P = NP$) in the weighted case (each vertex has a weight $w(v)$ and we want to minimize the weight of the cover). </p>

CC BY-SA 3.0
2014-02-18T03:23:03.813Z
2014-02-18T03:23:03.813Z
Chandra Chekuri
<p>Following up Mohammad Al-Turkistany's answer, it seems that many of the polynomial-time solvable unweighted problems could be turned $NP$-complete in the weighted case, if we ask whether there is a solution that has <strong>exactly</strong> a given weight. The reason is that this may allow to encode the Subset Sum Problem into the considered task. </p>

<p>For example, in the case of Exact Weight Perfect Matching, we can take a complete bipartite graph as input, assigning given weights to the edges of a particular matching, and 0 weight to all other edges. It is easy to see that this weighted graph has a perfect matching of weight exactly $W$ if and only if there is a subset of the weights that sums exactly to $W$. (If there is such a subset,  then we can take the corresponding  edges from the fixed matching, and extending it to a perfect matching with 0-weight  edges, using that it is a complete bipartite graph.)  I think, a similar simple trick may work for a number of  other problems, as well. </p>

CC BY-SA 3.0
2014-08-23T23:27:08.617Z
Same comment as I left for Al-Turkistany's answer holds here. e.g Consider a problem of finding a cycle of length $k$ in a graph $G$ this is NP-complete both in weighted or unweighted graph (e.g Hamiltonian cycle), how we can say one is NP-complete and the other one is in P? This is irrelevant to the weight.
Saeed
CC BY-SA 3.0
2014-02-18T17:42:00.060Z
2014-02-18T17:42:00.060Z
Andras Farago
<p>My favorite example is the independent domination problem (given graph $G$ and integer $k$, 
does $G$ have an inclusion-maximal independent set of at most $k$ vertices?). 
By a nice result due to Martin Farber (<a href="http://www.sciencedirect.com/science/article/pii/0167637782900153">see here</a>), the unweighted version is polynomially solvable in chordal graphs. 
Gerard Chang proves that the weighted version is NP-complete for chordal graphs 
(<a href="http://www.sciencedirect.com/science/article/pii/S0166218X03006449#">see here</a>). </p>

CC BY-SA 3.0
2014-08-23T21:51:09.067Z
2014-08-23T21:51:09.067Z
vb le
<p>Perfect matching problem in bipartite graphs is in $P$ while <a href="http://www.iaeng.org/publication/WCE2008/WCE2008_pp878-880.pdf">Exact Weight Perfect Matching of Bipartite Graph is $NP$-Complete</a>.</p>

CC BY-SA 3.0
2014-05-30T11:48:42.250Z
I don't consider them as a same problem. looks like comparing complexity of shortest s-t path which is trivially P and a s-t path of size $\alpha$, which is trivially np-complete.
Saeed
CC BY-SA 3.0
2014-02-18T04:47:22.257Z
2014-02-18T04:47:22.257Z
Mohammad Al-Turkistany
<p>Maybe this is just a trivial example and you may consider it a degenerate case, but the first example that came to my mind is the <a href="http://en.wikipedia.org/wiki/Travelling_salesman_problem" rel="nofollow">Travelling Salesman Problem</a> (where it is usually assumed that the graph is complete). Note that the unweighted version is Hamiltonian Cycle, which is trivial for complete graphs.</p>

CC BY-SA 3.0
2014-02-18T22:13:00.260Z
2014-05-30T14:40:38.313Z
2014-05-30T14:40:38.313Z
Vinicius dos Santos
<p>Graph Balancing (also known as Min Out-degree Orientation) is another example of this phenomenon. In this problem we are given an undirected edge-weighted graph. The goal is to orient the edges so that the resulting digraph's (weighted) maximum out-degree is minimized. </p>

<p>The problem is often motivated by a scheduling scenario. Imagine that each vertex is a processor and each edge is a job which is only allowed to run on one of its two endpoints. The weight of an edge is the length of the corresponding job and the goal is to minimize the makespan.</p>

<p>The problem is NP-hard and APX-hard, even if all weights are 1 or 2 (see Ebenlendr et al. "Graph balancing: a special case of scheduling unrelated parallel machines" in SODA 2008). It is however in P for unweighted graphs (see Asahiro et al. "Graph classes and the complexity of the graph orientation
minimizing the maximum weighted outdegree" in CATS 2008).</p>

CC BY-SA 3.0
2014-02-18T09:07:26.077Z
2014-02-18T09:07:26.077Z
Michael Lampis
<p>Finding the minimum cost path under delay constraint (a.k.a. the Constrained Shortest Path problem) seems to fit here.</p>

<p>Suppose you have a graph $G=(V,E)$, a delay function $d:V\to\mathbb {N}^+$, a cost function $c:\to\mathbb {N}^+$, a number $D\in \mathbb {N}^+$ and two vertices $s,t\in V$.</p>

<p>The problem is finding the minimum cost $s-t$ path, such that the delay of the path no more than $D$.</p>

<p>If the problem is unweighted ($\forall v\in V:d(v) =1$, a.k.a $hop-count$),  the problem is trivial (given as homework in basic algo courses sometimes).</p>

<p>If the problem is weighted, it becomes the <a href="http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=B3DA001EDB3D8C1D95BBCF056ADE7A1C?doi=10.1.1.159.7347&amp;rep=rep1&amp;type=pdf" rel="nofollow">Constrained Shortest Path</a>, which is known to be NP-complete even on DAGs.</p>

CC BY-SA 3.0
2014-02-18T00:25:24.000Z
2014-05-29T10:52:08.267Z
2014-05-29T10:52:08.267Z
R B
<p>The problem Local Max Cut with the FLIP neighbourhood is PLS-complete in general integer-weighted graphs. </p>

<p>A.A. Schaeffer and M. Yannakakis. (1991). Simple local search problems that are hard to solve. SIAM Journal on Computing, 20(1):56-87.</p>

<p>However, if the largest weight is polynomial in the size of the graph, then local improvements to the potential (weight of a cut) will converge in polynomial time, since each improvement will increase the potential function by at least one, and the potential function is polynomially bounded. (With general weights, finding a solution reachable by local improvements from a specific starting cut is PSPACE-complete.)</p>

<p>A similar thing happens also in other "potential games".</p>

CC BY-SA 3.0
2014-02-18T08:16:51.647Z
2014-02-18T08:16:51.647Z
Rahul Savani
<p>On <a href="http://www.graphclasses.org/classes/gc_1227.html" rel="nofollow">2K_1-free</a> Maximum cut is polynomial and Weighted maximum cut is NP-complete.</p>

CC BY-SA 3.0
2015-01-26T14:09:37.667Z
2015-01-26T14:09:37.667Z
joro
<p>Traveling salesman is open on sold grid graphs, but Hamilton cycle (the unweighted variant) is known to be polynomial. </p>

<p>Discussion of both on the open problems project:</p>

<p><a href="http://cs.smith.edu/~orourke/TOPP/P54.html" rel="nofollow">http://cs.smith.edu/~orourke/TOPP/P54.html</a></p>

CC BY-SA 3.0
2014-05-31T22:50:29.773Z
2014-05-31T22:50:29.773Z
SamM
<p>Many algorithmic graph problems can be solved in polynomial time both on unweighted and weighted graphs. Some  examples are shortest path, min spanning tree, longest path (in directed acyclic graphs), max flow, min cut, max matching, optimum arborescence, certain densest subgraph problems, max disjoint directed cuts, max clique in certain graph classes, max independent set in certain graph classes, various max disjoint path problems,  etc. </p>

<p>There are, however, some (although probably significantly fewer) problems that are solvable in polynomial time in the <strong><em>unweighted</em></strong> case, but become hard (or have open status) in the <strong><em>weighted</em></strong> case. Here are two <strong>examples:</strong></p>

<ol>
<li><p>Given the $n$-vertex complete graph, and an integer $k\geq 1$, find a spanning $k$-connected subgraph with the minimum possible number of edges. This is solvable in polynomial time, using a theorem of F. Harary, which tells the structure of the optimal graphs. On the other hand, if the edges are weighted, then finding the minimum weight $k$-connected spanning subgraph is $NP$-hard. </p></li>
<li><p>A recent (Dec 2012) paper of S. Chechik, M.P. Johnson, M. Parter, and D. Peleg (see 
<a href="http://arxiv.org/pdf/1212.6176v1.pdf" rel="nofollow noreferrer">http://arxiv.org/pdf/1212.6176v1.pdf</a>) considers, among other things, a path problem they call <em>Minimum Exposure Path.</em> Here one looks for a path between two specified nodes, such that the number of nodes on the path, <em>plus</em> the number of nodes that have a neighbor  on the path is minimum. They prove that in bounded degree graphs this can be solved in polynomial time for the unweighted case, but becomes $NP$-hard in the weighted case, even with degree bound 4. (Note: The reference was found as an answer to the question <a href="https://cstheory.stackexchange.com/questions/21085/what-is-the-complexity-of-this-path-problem">What is the complexity of this path problem?</a>)</p></li>
</ol>

<p><strong>What are some other interesting problems of this nature, that is, when switching to the weighted version causes a "complexity jump?"</strong></p>

CC BY-SA 3.0
2014-02-18T00:08:45.017Z
Perfect matching problem in bipartite graphs is in $P$ while [Exact Weight Perfect Matching of Bipartite Graph is NP-Complete](http://www.iaeng.org/publication/WCE2008/WCE2008_pp878-880.pdf)
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-02-18T00:53:00.500Z
Thank you, it is an interesting example. You could add it as an answer, rather than a comment.
Andras Farago
CC BY-SA 3.0
2014-02-18T04:07:54.673Z
Knapsack is a simple example. If all profits are 1 then problem is easy (greedily inserting by size will be optimal) while it is NP-Hard when profits can be different and large. Not a graph problem but just to explain the phenomena.
Chandra Chekuri
<cc.complexity-theory><graph-algorithms><np-hardness>
Problems that are easy on unweighted graphs, but hard for weighted graphs
Andras Farago
# Problems that are easy on unweighted graphs, but hard for weighted graphs

(Asked by: username_0 on 2014-02-17)

Many algorithmic graph problems can be solved in polynomial time both on unweighted and weighted graphs. Some examples are shortest path, min spanning tree, longest path (in directed acyclic graphs), max flow, min cut, max matching, optimum arborescence, certain densest subgraph problems, max disjoint directed cuts, max clique in certain graph classes, max independent set in certain graph classes, various max disjoint path problems, etc.

There are, however, some (although probably significantly fewer) problems that are solvable in polynomial time in the ***unweighted*** case, but become hard (or have open status) in the ***weighted*** case. Here are two **examples:**

1. Given the $n$-vertex complete graph, and an integer $k\geq 1$, find a spanning $k$-connected subgraph with the minimum possible number of edges. This is solvable in polynomial time, using a theorem of F. Harary, which tells the structure of the optimal graphs. On the other hand, if the edges are weighted, then finding the minimum weight $k$-connected spanning subgraph is $NP$-hard.
2. A recent (Dec 2012) paper of S. Chechik, M.P. Johnson, M. Parter, and D. Peleg (see
   <http://arxiv.org/pdf/1212.6176v1.pdf>) considers, among other things, a path problem they call *Minimum Exposure Path.* Here one looks for a path between two specified nodes, such that the number of nodes on the path, *plus* the number of nodes that have a neighbor on the path is minimum. They prove that in bounded degree graphs this can be solved in polynomial time for the unweighted case, but becomes $NP$-hard in the weighted case, even with degree bound 4. (Note: The reference was found as an answer to the question [What is the complexity of this path problem?](https://cstheory.stackexchange.com/questions/21085/what-is-the-complexity-of-this-path-problem))

**What are some other interesting problems of this nature, that is, when switching to the weighted version causes a "complexity jump?"**

**Tags:** cc.complexity-theory, graph-algorithms, np-hardness
> **Comments:**
> **username_1**: Perfect matching problem in bipartite graphs is in $P$ while [Exact Weight Perfect Matching of Bipartite Graph is NP-Complete](http://www.iaeng.org/publication/WCE2008/WCE2008_pp878-880.pdf)  
> **username_0**: Thank you, it is an interesting example. You could add it as an answer, rather than a comment.  
> **username_2**: Knapsack is a simple example. If all profits are 1 then problem is easy (greedily inserting by size will be optimal) while it is NP-Hard when profits can be different and large. Not a graph problem but just to explain the phenomena.  

---

## 10 answers

### Answer by username_2 on 2014-02-18. Score: 12

In the world of approximation algorithms there is the capacitated vertex cover problem.
Given $G=(V,E)$ and integer capacities $c(v)$ for each $v \in V$ the goal is to find
a minimum sized vertex cover for $G$ where the number of edges covered by $v$ is at most $c(v)$. This problem has a constant factor approximation in the unweighted case (that is, we want to minimize the size of the vertex cover) while it is $\Omega(\log n)$-hard (unless $P = NP$) in the weighted case (each vertex has a weight $w(v)$ and we want to minimize the weight of the cover).


---

### Answer by username_0 on 2014-02-18. Score: 12

Following up Mohammad Al-Turkistany's answer, it seems that many of the polynomial-time solvable unweighted problems could be turned $NP$-complete in the weighted case, if we ask whether there is a solution that has **exactly** a given weight. The reason is that this may allow to encode the Subset Sum Problem into the considered task.

For example, in the case of Exact Weight Perfect Matching, we can take a complete bipartite graph as input, assigning given weights to the edges of a particular matching, and 0 weight to all other edges. It is easy to see that this weighted graph has a perfect matching of weight exactly $W$ if and only if there is a subset of the weights that sums exactly to $W$. (If there is such a subset, then we can take the corresponding edges from the fixed matching, and extending it to a perfect matching with 0-weight edges, using that it is a complete bipartite graph.) I think, a similar simple trick may work for a number of other problems, as well.

> **Comments:**
> **username_3**: Same comment as I left for Al-Turkistany's answer holds here. e.g Consider a problem of finding a cycle of length $k$ in a graph $G$ this is NP-complete both in weighted or unweighted graph (e.g Hamiltonian cycle), how we can say one is NP-complete and the other one is in P? This is irrelevant to the weight.  

---

### Answer by username_4 on 2014-08-23. Score: 12

My favorite example is the independent domination problem (given graph $G$ and integer $k$,
does $G$ have an inclusion-maximal independent set of at most $k$ vertices?).
By a nice result due to Martin Farber ([see here](http://www.sciencedirect.com/science/article/pii/0167637782900153)), the unweighted version is polynomially solvable in chordal graphs.
Gerard Chang proves that the weighted version is NP-complete for chordal graphs
([see here](http://www.sciencedirect.com/science/article/pii/S0166218X03006449#)).


---

### Answer by username_1 on 2014-02-18. Score: 11

Perfect matching problem in bipartite graphs is in $P$ while [Exact Weight Perfect Matching of Bipartite Graph is $NP$-Complete](http://www.iaeng.org/publication/WCE2008/WCE2008_pp878-880.pdf).

> **Comments:**
> **username_3**: I don't consider them as a same problem. looks like comparing complexity of shortest s-t path which is trivially P and a s-t path of size $\alpha$, which is trivially np-complete.  

---

### Answer by username_6 on 2014-02-18. Score: 10

Graph Balancing (also known as Min Out-degree Orientation) is another example of this phenomenon. In this problem we are given an undirected edge-weighted graph. The goal is to orient the edges so that the resulting digraph's (weighted) maximum out-degree is minimized.

The problem is often motivated by a scheduling scenario. Imagine that each vertex is a processor and each edge is a job which is only allowed to run on one of its two endpoints. The weight of an edge is the length of the corresponding job and the goal is to minimize the makespan.

The problem is NP-hard and APX-hard, even if all weights are 1 or 2 (see Ebenlendr et al. "Graph balancing: a special case of scheduling unrelated parallel machines" in SODA 2008). It is however in P for unweighted graphs (see Asahiro et al. "Graph classes and the complexity of the graph orientation
minimizing the maximum weighted outdegree" in CATS 2008).


---

### Answer by username_5 on 2014-02-18. Score: 8

Maybe this is just a trivial example and you may consider it a degenerate case, but the first example that came to my mind is the [Travelling Salesman Problem](http://en.wikipedia.org/wiki/Travelling_salesman_problem) (where it is usually assumed that the graph is complete). Note that the unweighted version is Hamiltonian Cycle, which is trivial for complete graphs.


---

### Answer by username_7 on 2014-02-18. Score: 7

Finding the minimum cost path under delay constraint (a.k.a. the Constrained Shortest Path problem) seems to fit here.

Suppose you have a graph $G=(V,E)$, a delay function $d:V\to\mathbb {N}^+$, a cost function $c:\to\mathbb {N}^+$, a number $D\in \mathbb {N}^+$ and two vertices $s,t\in V$.

The problem is finding the minimum cost $s-t$ path, such that the delay of the path no more than $D$.

If the problem is unweighted ($\forall v\in V:d(v) =1$, a.k.a $hop-count$), the problem is trivial (given as homework in basic algo courses sometimes).

If the problem is weighted, it becomes the [Constrained Shortest Path](http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=B3DA001EDB3D8C1D95BBCF056ADE7A1C?doi=10.1.1.159.7347&rep=rep1&type=pdf), which is known to be NP-complete even on DAGs.


---

### Answer by username_8 on 2014-02-18. Score: 5

The problem Local Max Cut with the FLIP neighbourhood is PLS-complete in general integer-weighted graphs.

A.A. Schaeffer and M. Yannakakis. (1991). Simple local search problems that are hard to solve. SIAM Journal on Computing, 20(1):56-87.

However, if the largest weight is polynomial in the size of the graph, then local improvements to the potential (weight of a cut) will converge in polynomial time, since each improvement will increase the potential function by at least one, and the potential function is polynomially bounded. (With general weights, finding a solution reachable by local improvements from a specific starting cut is PSPACE-complete.)

A similar thing happens also in other "potential games".


---

### Answer by username_9 on 2015-01-26. Score: 3

On [2K\_1-free](http://www.graphclasses.org/classes/gc_1227.html) Maximum cut is polynomial and Weighted maximum cut is NP-complete.


---

### Answer by username_10 on 2014-05-31. Score: 3

Traveling salesman is open on sold grid graphs, but Hamilton cycle (the unweighted variant) is known to be polynomial.

Discussion of both on the open problems project:

<http://cs.smith.edu/~orourke/TOPP/P54.html>


---

