# Tagged Questions

The tag has no usage guidance.

209 views

### Minimum vertex k-cut

Given an undirected graph $G = (V, E)$ and an integer $k$, the well-known minimum (edge) $k$-cut problem asks to find $E' \subseteq E$ with minimum $|E'|$ that the graph $(V, E \setminus E')$ has at ...
99 views

### Fractional but not integer multi-commodity minimum cost flow

I'm searching for an example digraph for the multi-commodity minimum cost flow problem with integer demand. There shouldn't be an integer but fractional optimal solution. I found here a similar ...
255 views

### Can the optimal minimum cost two-commodities flow be fractional on this special case?

Suppose that we have a two commodities flow network $N=<G=(V,E), s_1,s_2,t_1,t_2\in V>$. The problem is to find a minimum cost two-commodity flow in which there a flow $f_1$ from $s_1$ to $t_1$ ...
340 views

### Maximum matching versus preferential assignment

There are several ways to solve the marriage problem. The "preferential assignment" approach consists in forming couples on the basis of preferred characteristics expressed by each individual. An ...
229 views

### another solution problem (ASP) of integer multicommodity flow: is it NP-complete?

I know that integer multicommodity flow is NP-complete. It was proven in "On the complexity of time table and multi-commodity flow problems" (http://dl.acm.org/citation.cfm?id=1382492) that any SAT ...
43 views

### Approximating BLEDP on restricted graph classes

In the edge-disjoint paths (EDP) problem, we are given an undirected graph $G$, and a set $\{ (s_i,t_i) \mid 1 \leq i \leq k \}$ of $k$ source-sink pairs. The objective is to maximize the number of ...
181 views

### How can we derive this lower bound of a special cut in a graph?

I have another question about this paper. There the authors prove a special version of the maximal flow-minimal cut theorem for uniform exactly-$k$-splittable $s$-$t$-flows. They define the cut in ...
197 views

### Finding the perfomance ratio in a multicommodity-flow

I am reading the following paper about multicommodity-flows. I have not a very strong background in graph theory and hence most of my question regarding the paper are fundamental. My questions are ...
200 views

### On the optimal solution of the CKR formulation for MULTIWAY CUT

Currently the best approximation algorithm for the MULTIWAY CUT problem is obtained via the linear program based on geometrical embedding by CKR [1]. Let $U_i$ be those vertices in $V-T$ which is ...
232 views

### Request for references on multicommodity flow-cut results

This is a somewhat subjective question. I am interested in studying the literature on multicommodity flow-cut results, especially the 'positive' results which show that flow is a good approximation to ...