23
$\begingroup$

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

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

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Perfect matching problem in bipartite graphs is in $P$ while Exact Weight Perfect Matching of Bipartite Graph is NP-Complete $\endgroup$
    – Mohammad Al-Turkistany
    Feb 18, 2014 at 0:08
  • 1
    $\begingroup$ Thank you, it is an interesting example. You could add it as an answer, rather than a comment. $\endgroup$
    – Andras Farago
    Feb 18, 2014 at 0:53
  • 3
    $\begingroup$ 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. $\endgroup$
    – Chandra Chekuri
    Feb 18, 2014 at 4:07

10 Answers 10

Reset to default
12
$\begingroup$

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

Improve this answer
$\endgroup$
12
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – Saeed
    Aug 23, 2014 at 23:27
12
$\begingroup$

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), the unweighted version is polynomially solvable in chordal graphs. Gerard Chang proves that the weighted version is NP-complete for chordal graphs (see here).

Improve this answer
$\endgroup$
11
$\begingroup$

Perfect matching problem in bipartite graphs is in $P$ while Exact Weight Perfect Matching of Bipartite Graph is $NP$-Complete.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – Saeed
    May 30, 2014 at 11:48
10
$\begingroup$

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

Improve this answer
$\endgroup$
8
$\begingroup$

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 (where it is usually assumed that the graph is complete). Note that the unweighted version is Hamiltonian Cycle, which is trivial for complete graphs.

Improve this answer
$\endgroup$
7
$\begingroup$

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, which is known to be NP-complete even on DAGs.

Improve this answer
$\endgroup$
5
$\begingroup$

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

Improve this answer
$\endgroup$
3
$\begingroup$

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

Improve this answer
$\endgroup$
3
$\begingroup$

On 2K_1-free Maximum cut is polynomial and Weighted maximum cut is NP-complete.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.