Tag Info

Hot answers tagged minimum-cuts

5

You pretty much have the answer in front of you. For any vertex $v$, the cut $\left(\left\{v\right\},V\setminus\left\{v\right\}\right)$ has $\text{deg}(v)$ crossing edges. If there exists a vertex $v$ with degree $<k$, then its corresponding cut has less than $k$ crossing edges, contradicting the minimality of $(A,B)$.

4

Those answers assume that all edge capacities are integers. Assuming they are, this works. Suppose the min-cut in the original graph has total capacity $x$; then it will have total capacity $x(|E|+1)+k$ in the transformed graph, where $k$ counts the number of edges crossing that cut. Note that if you consider any cut in the original graph with larger ...

2

Consider the following graph. The min-cut is $[s][a,b,c,d,t]$ with value 3. After the weights of all edges are increased by 1, the min-cut becomes $[s,a,b,c,d][t]$ with value 5. It does not matter whether you are considering cuts with terminals or without terminals (if with terminals, the terminals are $s$ and $t$).

2

Most simple explanation: The problem has been written down at hackerearth in some markup "language" not mastered by the author. Multiplication has been denoted using an asterisk * instead of a multiplication sign × (regrettably common since the introduction of type-writers). The markup seems to define that as a toggle between "normal" and "stand-out" text ...

1

This problem is NP-hard if 0 weight is allowed. We can reduce Not-All-Equal 3SAT to the decision version of this problem. Given an instance of Not-All-Equal 3SAT with $n$ variables and $m$ clauses, for each variable $x_i$, we create two vertices $v_i$ and $v_i'$ with an edge between them for each variable. In addition, for each clause, for example, $x_1\... 1 It really depends on what do you exactly mean by "path". Edge-disjoint paths -- Given a graph$G=(V,E)$, a minimum edge-cut consists of one edge for every edge-disjoint path between$s$and$t$. Vertex-disjoint paths -- Given a graph$G=(V,E)$, a minimum vertex-cut consists of one vertex for every vertex-disjoint path between$s$and$t$. Therefore, the ... 1 The edge from$2$to$3$isn't part of the minimum cut. It's oriented in the wrong direction, from the sink side to the source side, so you can delete it from your cut and there's still no path from$s$to$t$. 1 Max flow and min cut are dual problems, in a technical sense: there are linear programming formulations of both, and these linear programs are dual to each other. This is explained in the Wikipedia article on the max-flow min-cut theorem. Given a variant of the max flow problem, you can find the corresponding min cut problem by writing the linear ... 1 Remove$u$and$v$(as well as all edges connected to them), and for any removed edge$(u,x)$, add an edge from$s$to$x$with the same capacity; for any removed edge$(y,v)$, add an edge from$y$to$t$with the same capacity. Now find a min cut in this new graph. The partition of nodes in this cut suggests a min cut among those including$e$in the ... 1 Some graphs have less than the maximum. This shouldn't be a surprise. 1 "Maximum" here means that no graph can have more than$n \choose 2$minimum cuts. Obviously, you can come up with graphs (or infinite families of graphs) that have fewer minimum cuts, like say$n-1$. This is less than$n \choose 2$which is perfectly fine, so this is no contradiction. In other words, the result only means that you can't come up with graphs ... 1 Wikipedia says that, for an undirected graph, you can say:$A$is the vertex separator for$v$and$F$.$A$is the separating set for$v$and$F$.$A$is the vertex cut for$v$and$F$. perhaps these terms are used for digraphs as well, even though "connected components" are not quite the same thing in digraphs. edit: @PålGD suggests the variant "... 1 In principle, the problem is NP-hard, in the worst case. If you have$n$candidate replacements, you might have to try all$2^n$combinations of replacements. Fortunately, in practice, there are often circumstances where you can find a reasonable solution more efficiently, because many call sites are at least somewhat independent. Then it becomes an ... 1 The problem you're trying to solve is undecidable, since you can't tell if any of the changes makes the program go into an infinite loop. 1 The Provan and Ball paper actually shows a 1-1 reduction from bipartite independent sets (BIS) to min st cuts. So an FPRAS for min cuts would imply an FPRAS for #BIS. However, #BIS is not known (and thought unlikely) to have an FPRAS .  Dyer, Martin, et al. "On the relative complexity of approximate counting problems." International Workshop on ... 1 Why 2 different edge min-cuts in an undirected multigraph must be completely disjoint? There is no "why" here since 2 different edge minimum-cuts in an undirected multigraph can have one edge in common. Here is an example. Edge set$\{AB,AC\}$is a minimum cut. Edge set$\{AB,BC\}\$ is another minimum cut. They have edge AB in common. For the proof of ...

Only top voted, non community-wiki answers of a minimum length are eligible