7
$\begingroup$

Given an undirected graph $G$ and two vertices $s$ and $t$, i want to find a minimum set of edges $E$ in $G$ such that every (simple) $s$-$t$-path contains at least 2 edges from $E$.
Is this problem solvable in polynomial time? What if the paths should not contain 2, but $r$ edges in $E$?

I know that for $r=1$, this is equivalent to simply finding a minimum $s$-$t$-cut, so maybe the problem can be solved by using MaxFlowMinCut-techniques?

$\endgroup$

3 Answers 3

2
$\begingroup$

[EDIT: updated to apply to undirected graphs]

Lemma 1. The general problem (with $r$ given as input) is solvable in polynomial time.

Proof. 1. Fix a problem instance $(G=(V, E), s, t)$. For brevity, define an $r$-cut to be any edge subset $C\subseteq E$ such that every $s$-$t$ path contains at least $r$ edges in $C$. The goal is to find a minimum-size $r$-cut. (Note that we use $E$ for the given edge set, and $C$ for the solution, whereas the post uses $E$ for the solution.)

  1. Consider the following linear-program (LP) relaxation of the problem:

$$\begin{aligned} \textsf{minimize } &\textstyle ~\sum_{e\in E} \ell_e~ \textsf{ s.t.}\\ \pi_s &{} = 0 \\ \pi_t &{} \ge r \\ |\pi_w - \pi_u| & {} \le \ell_e \le 1 && (e=\{u,w\} \in E) \end{aligned} $$

  1. Note that the LP is indeed a relaxation of the original problem. Indeed, each solution $C$ to the given instance corresponds to the integer-valued LP solution $(\ell, \pi)$ of cost $|C|$ obtained by setting $\ell_e = 1$ for $e\in C$, and setting each $\pi_v$ to the distance from $s$ to $v$ in the graph where each edge $e$ is assigned length $\ell_e$. Conversely, given any integer-valued feasible LP solution $(\ell, \pi)$, taking $C=\{e \in E : \ell_e = 1\}$ gives a solution $C$ to the given instance, of size $|C|=\sum_{e\in E} \ell_e$.

  2. Now, using any polynomial-time LP algorithm, compute a min-cost (possibly fractional) solution $(\ell, \pi)$ to the LP. Since the LP is a relaxation of the original problem, the cost $\sum_{e\in E} \ell_e$ of $(\ell, \pi)$ is a lower bound on the minimum size of any $r$-cut.

  3. Compute a random integer LP solution $(\ell', \pi')$ and corresponding $r$-cut $C$ from $(\ell, \pi)$ using the following randomized-rounding scheme:

  1. choose $\lambda \in [0, 1)$ uniformly at random
  2. let $\pi'_v = \lfloor \pi_v + \lambda \rfloor$ for each vertex $v\in V$
  3. let $\ell'_e = |\pi'_w - \pi'_u|$ for each edge $e=\{u,w\}\in E$
  4. let $C=\{e\in E: \ell'_e = 1\}$ be the $r$-cut corresponding to $(\ell', \pi')$
  1. First observe that $(\ell', \pi')$ is feasible. In particular, for any edge $\{u, w\}\in E$, we have $$\ell'_e = |\pi'_w - \pi'_u| = |\lfloor \pi_w + \lambda \rfloor - \lfloor \pi_u + \lambda \rfloor| \le 1$$ because $|(\pi_w + \lambda) - (\pi_u + \lambda)| \le \ell_e \le 1$.

  2. Next we bound the expected size of $C$.

  3. Consider any edge $e=\{u,w\}\in E$. We will show $\Pr[e\in C] \le \ell_e$.

  4. Note $|\pi_w - \pi_u| \le \ell_e \le 1$, so $$\Pr[e\in C] = \Pr_\lambda[|\lfloor \pi_w + \lambda \rfloor - \lfloor \pi_u + \lambda \rfloor| = 1] = |\pi_w - \pi_u| \le \ell_e. $$ (The second equality above follows by calculation.)

  5. So $\Pr[e\in C] \le \ell_e$ for all $e\in E$.

  6. Now, using also linearity of expectation, we have $E[|C|] = \sum_{e\in E} \Pr[e\in C] \le \sum_{e\in E} \ell_e$.

  7. That is, the expected size of the $r$-cut $C$ is at most the cost of $(\ell, \pi)$. Since the latter cost is at most OPT (the minimum size of any $r$-cut), it follows that the expected size of $C$ is at most OPT. $~~~~\Box$

BTW, since $|C|$ can't be less than OPT in any outcome, it follows that $C$ must be optimal, for any choice of $\lambda\in [0, 1)$. Essentially, every optimal solution to the LP is a convex combination of optimal integer solutions.

$\endgroup$
5
  • 1
    $\begingroup$ Great answer! This solves the problem! In step 11 we can show the second equation by distinguishing between two cases: If $\lceil \pi_u \rceil = \lceil \pi_w \rceil$, then $\Pr_\lambda[\lfloor \pi_w + \lambda \rfloor - \lfloor \pi_u + \lambda \rfloor = 1] = \Pr[\lceil \pi_w \rceil - \pi_w \le \lambda < \lceil \pi_u \rceil - \pi_u] $, which is equal to $\pi_w - \pi_u$. $\endgroup$
    – tgnome
    Mar 14 at 11:39
  • 1
    $\begingroup$ If $\lceil \pi_w \rceil = \lceil \pi_u \rceil + 1$, then $\Pr_\lambda[\lfloor \pi_w + \lambda \rfloor - \lfloor \pi_u + \lambda \rfloor = 1] = \Pr[\lceil \pi_w \rceil - \pi_w \le \lambda] + \Pr[\lambda < \lceil \pi_u \rceil - \pi_u ]$, which again is equal to $\pi_w - \pi_u$. $\endgroup$
    – tgnome
    Mar 14 at 11:45
  • $\begingroup$ Upon further investigation, i don't think that this works. The inequations $\pi_w - \pi_u \le \ell_{(u,w)}$ for all $(u,w) \in E$ require an orientation of the edges, don't they? Same thing for $\ell'_{(u,w)} = \max(0, \pi'_w - \pi'_u)$. I can't see a way to adapt this argumentation to undirected graphs. Also in directed graphs i think the problem should be solvable way easier without using any probabilistic approaches. $\endgroup$
    – tgnome
    Mar 20 at 12:23
  • 1
    $\begingroup$ (i) I updated it to apply to undirected graphs. As far as I can tell there is no problem. (ii) Why do you think it's easier for directed graphs? (Maybe you are thinking of directed acyclic graphs?) In any case, it won't be easier than min-cut. (iii) The proof here really shows that any standard LP solver (which will return a basic feasible solution) will return an optimal integer solution. The randomness is just for the proof, not really needed for the algorithm. But probably there is also a combinatorial algorithm. $\endgroup$
    – Neal Young
    Mar 20 at 22:43
  • 1
    $\begingroup$ Thanks again! I think i got confused because i had the following thought: When writing the third inequation of the LP in matrix form, we obtain the node-edge-incidence matrix of $G$. In directed graphs, this is a totally unimodular matrix, which means there must always be an integral optimal solution. This is not the case for undirected graphs: But obviously total unimodularity is not necessary for an integral optimal solution to exist! And thanks also for the clarification on the random aspect of the proof $\endgroup$
    – tgnome
    Mar 21 at 10:21
1
$\begingroup$

Here's an idea, find the min-cut edge set $C$ with respect to the required $s$-$t$. Thus, all $s$-$t$ paths will have exactly one edge from this set $C$. Now collapse all end points of the edges present in $C$ into a single vertex (but do not include the edges as they would create self-loops). It is safe to assume that both $s$ and $t$ have not merged, otherwise, your required set does not exist. Now again, find a min-cut edge set $C'$ on this modified graph. Thus, all $s$-$t$ paths will have one edge from $C$ and another from $C'$. By construction, the set $C \cup C'$ would be minimal (but may not be minimum).

$\endgroup$
3
  • $\begingroup$ Nice answer, i think this should work for minimal sets! Now what about minimum sets? $\endgroup$
    – tgnome
    Mar 13 at 10:18
  • $\begingroup$ In the given graph, when we have $|C| = |C′|$ the result is optimal. In general, we have an approximation ratio of $|C| / |C′|$. $\endgroup$
    – codeR
    Mar 13 at 11:41
  • $\begingroup$ In my opinion, an optimal solution $S$ should exhibit a similar structure. That is, there must be two cut sets $S_1$ and $S_2$ of the graph such that $S_1 \cup S_2 = S$ and $S_1 \cap S_2 = \phi$. $\endgroup$
    – codeR
    Mar 13 at 11:48
0
$\begingroup$

Lemma 1: If all $s$-$t$ simple paths go through some edge $(u, v)$ then all of them also go through the nodes $u$ and $v$. Conversely if all if all $s$-$t$ simple paths go through $u$ and $v$ and there is only one path between $u$ and $v$ then all the paths go through the edge $(u, v)$.

Start BFS at $s$ and construct the BFS tree. Let $t \in L_{k}$.
Lemma 2: If there is a layer $L_{i}$ for $i$ < $k$ such that $L_{i} = \{ w \}$ (only have one node) then all $s$-$t$ paths go through $w$.

Outline of the Proof: If we remove the node from the BFS tree, then there are no paths between $s$ and $t$. This is since all non-tree edges in a BFS tree are between nodes of the same or successive layers.

Using Lemma 1 and 2, we can find all pairs of layers $L_{i}$, $L_{i+1}$ such that $|L_{i}| = |L_{i+1}| = 1$ and $i+1 \leq k$ and the set of edges between the pairs of layers, is the set of edges you're looking for.

$\endgroup$
4
  • $\begingroup$ Interesting approach! But from my understanding, there must not always exist two consecutive layers of cardinality one in such a BFS tree, or am i missing something $\endgroup$
    – tgnome
    Mar 11 at 13:18
  • $\begingroup$ I don't see how that's true. Unless there is something wrong in the proof (which can very well be the case) there should be two consecutive layers of cardinality one iff there is an edge through which all paths go. $\endgroup$ Mar 11 at 15:27
  • $\begingroup$ I understand that, but the question is not wether there is an edge through which all paths go. The problem is to find a minimal set of edges E such that every path contains some (two or r) edges from E. It is not necessary that all paths share an edge for this. $\endgroup$
    – tgnome
    Mar 11 at 19:47
  • $\begingroup$ Oh, I see! I misunderstood the question. I'll give this one a shot too. $\endgroup$ Mar 11 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.