
Boost Users : 
Subject: Re: [Boostusers] [BGL] Shared nodes on path
From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 20140228 11:58:02
On Fri, Feb 28, 2014 at 4:49 AM, Sensei <senseiwa_at_[hidden]> wrote:
> On 27/02/14 18:11, Aaron Windsor wrote:
>
>> Hi,
>>
>> As described, your problem is NPhard, which means that if you were to
>> find a way to solve it in polynomial time in the number of vertices in
>> the graph, you'd also be able to solve a lot of other hard problems that
>> nobody's ever been able to solve in polynomial time. For example, given
>> an algorithm that solves your problem, you could use that algorithm to
>> find Hamiltonian paths in graphs: for any graph G with n vertices, just
>> run the algorithm on that graph and the path (u, x_0, ..., x_{n2}, v),
>> where the x_i's are vertices not appearing in G (or, say, isolated
>> vertices in G) and u and v are two vertices from G. If the algorithm
>> outputs a path, it's a path of length n1 and thus Hamiltonian. [...]
>>
>
> Maybe there are some additional constraints on your actual problem or
>> the graphs you're dealing with that make it simpler than what you've
>> described above? If so, those would be good to know. If not, and you
>> still want to write an algorithm to do this, I'd suggest that you don't
>> try to do anything fancy with the BGL. Your best bet will just
>> enumerating through all candidate paths of the appropriate length and
>> checking if the candidate is an actual path in G.
>>
>
>
> Hi Aaron,
>
> Unfortunately, you're right, it is NPhard, however, I have some
> dimensions that can be relied on.
>
> The graph G can be very huge, but each node has *at most* four outgoing
> edges.
>
> The path P consists usually of ~50 nodes.
>
> A solution is either complete, i.e., the length of a solution is equal to
> the length of P, or the solution is not acceptable.
>
>
> The only thing I could do with BGL, then, is just to find all paths from
> one vertices to another, and check the length. Am I right?
Yes, pretty much. Even then, you're going to have to do some bookkeeping to
keep track of nodes you've already seen on a path and backtrack correctly 
e.g., you used nodes a, b, and c on a path from x to y so when you find
paths from y to something else you'll have to remove a, b, and c from the
graph you explore. And even with nodes of degree 4, you've still got an
NPhard problem and the possibility of an exponential number of paths being
output from your algorithm.
Aaron
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net