Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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 ...
David Eppstein's user avatar
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.) ...
D.W.'s user avatar
  • 12.1k
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 ...
Christian Komusiewicz's user avatar
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 ...
Christian Komusiewicz's user avatar
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 ...
Sasho Nikolov's user avatar
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 ...
Neal Young's user avatar
  • 10.8k
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 ...
lacker's user avatar
  • 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 ...
Neal Young's user avatar
  • 10.8k
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$ ...
Richard's user avatar
  • 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:...
David Eppstein's user avatar
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....
Mohammad Al-Turkistany's user avatar

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