# Tag Info

Accepted

### Finding vertex separator such that the induced subgraph has minimal number of edges

An independent set that disconnects its graph is called an "independent cut", graphs that contain an independent cut are called "fragile graphs", and recognizing fragile graphs is ...

### Second Smallest $s$-$t$-Cut in a Network

The second smallest cut, and more generally the $k$ smallest cuts, can be found in time polynomial in $k$ and the network size. See: H. W. Hamacher. An $(K\cdot n^4)$ algorithm for finding the $k$ ...

### Minimum cut through vertices/nodes - not edges

It is not very difficult to transform the vertices problem to an equivalent edge version. ...

### Max flow with restriction of individual flows

That constraint is linear, so the entire problem is an instance of linear programming, thus can be solved in polynomial time. (I am assuming there is no restriction or requirement for integer flows.) ...

### Minimum graph cut with constraints

The problem that you describe is NP-hard even on stars as we can reduce Multicut in Trees to its decision version (where we have a cost bound). In Multicut in Trees the input is a tree $G=(V,E)$, a ...

### generate a graph with fixed min cut

In his 1962 paper "The Maximum Connectivity of a Graph", Harary describes a way to construct for integers $p$ and $q$ with $q\ge p-1$ a way to construct a graph with $p$ vertices and $q$ edges that ...
Accepted

### Name of graph partition that balances edges between sets with edges remaining within sets

This is the Min-Disagreements version of the correlation clustering problem (on complete graphs), defined by Bansal, Blum, and Chawla (full version). They give a (huge) constant factor approximation ...

### Increasing the capacity to maximize the min cut

Theorem. The problem in the post is NP-hard. By "the problem in the post", I mean, given a graph $G=(V,E)$ and integer $k$, to choose $k$ edges to raise the capacities of so as to maximize the min ...
Accepted

### Interval partitioning with restrictions: NP-complete or efficiently solvable?

Here's a reduction from 3SAT. For each of your 3SAT variables $x_0$, imagine there is one event $x_0$ and two rooms called "Room $x_0$ is true" and "Room $x_0$ is false". The event $x_0$ has to be in ...

### Max flow with restriction of individual flows

Lemma 1. The problem (assuming integer flow is required) is NP-hard. Proof sketch. The proof is by reduction from 3D-matching. The reduction is similar to the reduction for equal flow referred to ...

### Number of mincuts of a graph without using Karger's algorithm

Informally, one can argue that in order to have the maximum number of min-cuts, all nodes in a graph must have the same degree. Let a cut divide a graph $G$ into two set of nodes $C$ and $\bar C$ ...

### Name of graph partition that balances edges between sets with edges remaining within sets

In the parameterized complexity community, it is called cluster editing. See e.g. "Cluster graph modification problems", Ron Shamir, Roded Sharan and Dekel Tsur, Discrete Applied Mathematics 2004, doi:...
1 vote

### Minimum cut with size bounds $k\leq |S| \leq |V|-k$

The NP-complete Balanced min cut problem ($|S|< c|V|$ and $|V-S|<c|V|$ for $0<c<1$) is a special case of your problem. Hence your problem is NP-complete. Reference: Garey, M.R., Johnson, D....
1 vote
Accepted

### Length bounded minimum cardinality cut in DAGs

The paper mentioned in the question uses a reduction from Vertex Cover problem to show that the length bounded cut problem is NP Hard. The instance they construct given an instance of vertex cover, is ...

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