# Tag Info

11

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 known NP-complete [C. deFigueiredo, S. Klein, "NP-completeness of multipartite cutset testing", Congr. Numer. 119 (1996) 217–222, as cited by Guantao ...

8

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$ best cuts in a network. Oper. Res. Lett. 1(5):186–189, 1982, doi:10.1016/0167-6377(82)90037-2. H. W. Hamacher, J.-C. Picard, and M. Queyranne. On finding the $K$ ...

7

It depends on how you define "solvable via network flows". If you allow the preprocessing step to take arbitrarily long, then anything is solvable using network flows by simply solving it an then outputting a trivial network flow that has the desired answer. Under log-space reductions, network flow is $P$-complete so any problem in $P$ can be solved "...

5

It is not very difficult to transform the vertices problem to an equivalent edge version. Consider a vertex v. Replace v with v1 and v2. Join v1 and v2 with an edge of capacity 1. All the incoming edges into v go into v1 and all the outgoing edges from v, leave v2. ie (u v) -> (u v1) and (v w) -> (v2 w) This is equivalent to edge version of the s-t ...

3

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.) In general if you allow arbitrary constraints, the problem can become NP-hard.

3

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 set $S\subseteq {V\choose 2}$ of vertex pairs, and an integer $k$ and one asks whether one can separate all vertex pairs of $S$ by removing at most $k$ edges. The ...

3

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 is $k=\lfloor 2q/p\rfloor$-connected. Roughly, the idea is to give indices from $0$ to $p-1$ to the $p$ vertices and then add edges between vertices whose ...

3

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 for the problem and prove it's NP-hard. Charikar, Guruswami, and Wirth show the problem is APX-hard, and improve the approximation factor to 4 via region growing....

3

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 one of those two rooms. Whichever statement is true, that's the room we don't use. And it is going to take all day. So the only rooms generally available for ...

3

There is a randomized algorithm for computing Gomory-Hu tree in $\tilde{O}(|E||V|)$ time when all edges have capacity 1. Once you have the Gomory-Hu tree, you can process it so you can answer maximum flow queries between two vertices in constant time.

3

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 cut in the modified graph. The idea is to reduce from Max Cut. Roughly, a given graph $G=(V,E)$ has max cut size $s$ if and only if you can increase the ...

2

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$ such that $C \cap \bar C=\emptyset$. Let the number of min-cuts in a graph be denoted as $mc(G)$. Consider a connected graph with $n$ vertices in which each ...

2

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 in @JeffE's answer to this cstheory.stackexchange post. Fix a 3D-matching input $(X, Y, Z, E)$. Recall that $X$, $Y$, and $Z$ are disjoint, with $|X|=|Y|=|Z|$ ...

2

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:10.1016/j.dam.2004.01.007, "Efficient Parameterized Preprocessing for Cluster Editing", Michael Fellows, Michael Langston, Frances Rosamond, and Peter Shaw, ...

1

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 nothing but a DAG. In this case all the edge has unit weight which corresponds to the minimum cardinality case. Therefore, the problem of L-length bounded ...

1

You can model the constraint of not using two edges (u,v) and (u,w) of capacity one simultaneously in a flow network by introducing a vertex u' and an edge (u',u) with capacity one, but I'm not aware of a more general way to do this without extending the concept of a flow network. If your idea for reducing the maximum independent set problem to a network ...

1

Here I'll show that the statement is true, assuming that $V=U\cup\{s,t\}$, i.e. source and sink are not elements of $U$. Let $S=\bigcap\limits_{R\in\mathcal R}R$, $P=\bigcup\limits_{R\in\mathcal R}R\setminus S$ and $T=U\setminus(S\cup P)$. Construct a flow network $N$ with nodes $U\cup\{s,t\}$ and the following edges: From $s$ to every element of $S$. From ...

1

The run-time of Karger-Stein is usually represented as a function of the number of vertices $n$, not of the number of edges. Therefore, placing an edge of weight $0$ between two vertices that previously did not share an edge would make your algorithm identical to theirs and not change the run-time.

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