Share Your Experience: Take the 2024 Developer Survey

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

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.) ...
• 12.1k

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 ...
• 18.2k

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 ...
• 10.8k
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

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 ...
• 10.8k

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