Skip to main content
Share Your Experience: Take the 2024 Developer Survey

New answers tagged

0 votes

Least interrupted max flow after removing K edges algorithm

There is a polynomial solution. Give each edge cost $1$. Using minimum-cost flow algorithm find the maximum capacity $f$ of a flow with cost at most $k$. Take as $E'$ all edges of the minimum cost ...
Smylic's user avatar
  • 225
0 votes

Robust maximum weight forests with weights on edges

The problem may not be NP-hard! Let us look at the following facts: The maximum-spanning tree problem is polynomial-time solvable There are only $n\choose 3$ ways the deletion and addition of edges ...
codeR's user avatar
  • 987
3 votes
Accepted

Proving that the shortest simple path problem between two vertices 𝑠 and 𝑡 in a graph with given path upperbound be positive is NP-complete

There is an easy reduction from s-t-Hamilton path, to prove your problem is NP-hard: Given a Graph (V, E) and two vertices s and t (the s-t-Hamilton path instance), construct an instance for your ...
SimonNW's user avatar
  • 86
0 votes

Show that it is Np-hard to determine whether a given graph has the crossing number k

The crossing number problem has been well studied. From wiki: In general, determining the crossing number of a graph is hard; Garey and Johnson showed in 1983 that it is an NP-hard problem [ref]. In ...
codeR's user avatar
  • 987

Top 50 recent answers are included