0
$\begingroup$

I have the following problem. I would like to know if it reduces to some standard problem in Graph theory. Particularly, I would like to know whether it is NP-hard, if yes, how to prove its NP-hardness, if not, is there any algorithm that solves it.
Any suggestions are much appreciated.

In a undirected graph, I want to find the maximal number of node-disjoint routes from a source node to a destination node. Compared with the classical node-disjoint routing problem, I have a particular constraint here, i.e., we are given a number of sets, each containing a number of nodes in the graph, for any two node-disjoint routes we find, they cannot both contain nodes in the same node set. For example, if route R1 contains nodes in node set S1, then any other route cannot contain nodes in S1.

Thx in advance.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Hypergraph matching can be reduced to this problem. Let $\mathcal H$ be a hypergraph on vertex set $C$, thought of as a set of colours. For each edge $E$ of $\mathcal H$, draw a path $P$ from the source to the destination such that the colours of the (internal) vertices of $P$ are precisely those in $E$. Then paths from the source to the destination are in direct correspondence with edges of $\mathcal H$, and two paths have no colours in common if and only if the corresponding edges are disjoint.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thank you Ben for your quick & nice response. Just a related question: if I modify my constraint and question as follows: now I want to calculate the max-flow of the graph (basically routes can share the same node), but still under the constraint of mutual exclusiveness given a number of node sets, as stated in my original question. $\endgroup$
    – lchen
    Jun 11, 2014 at 14:03
  • $\begingroup$ @user52871 Since edge-disjoint and vertex-disjoint paths from source to destination in the above example happen to coincide, hypergraph matching is also reducible to the max-flow problem. $\endgroup$
    – Ben Barber
    Jun 11, 2014 at 14:58
  • $\begingroup$ Thanks again Ben. I just have another thought on your response to the original problem. It seems to me that according to your answer, the problem of finding maximal number of node-disjoint routes can also be cast into the hypergraph matching problem and is thus NP-hard. However, if I recall correctly, this problem is not NP-hard. In my opinion, it is the constraint on the node mutual exclusivity as stated in the problem that makes the problem NP-hard (it seems that you didn't use this constraint in your answer). Could you pls clarify this for me (or am I wrong anywhere)? $\endgroup$
    – lchen
    Jun 12, 2014 at 8:26
  • $\begingroup$ Another related question in case where the problem is NP-hard, could you point me some directions to look at to develop heuristic routing algorithms with good approximation? Thanks! $\endgroup$
    – lchen
    Jun 12, 2014 at 8:27
  • $\begingroup$ The extra constraint is essential. In the reduction, every pair of paths from the source to the sink are vertex-disjoint, so the only restriction is that we must never use a colour more than once. I'm afraid I don't know anything about approximation. $\endgroup$
    – Ben Barber
    Jun 12, 2014 at 8:57

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.