11
votes
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 ...
- 50.7k
8
votes
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$ ...
- 50.7k
5
votes
Minimum cut through vertices/nodes - not edges
It is not very difficult to transform the vertices problem to an equivalent edge version.
...
3
votes
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.)
...
- 11.3k
3
votes
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 ...
- 1,700
3
votes
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 ...
- 1,700
3
votes
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 ...
- 18.1k
3
votes
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 ...
- 9,555
3
votes
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 ...
- 256
2
votes
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 ...
- 9,555
2
votes
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$ ...
- 198
2
votes
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:...
- 50.7k
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....
- 20.8k
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 ...
- 171
Only top scored, non community-wiki answers of a minimum length are eligible