
Boost Users : 
Subject: Re: [Boostusers] [BGL] Shared nodes on path
From: Sensei (senseiwa_at_[hidden])
Date: 20140228 07:49:54
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?
Thanks!
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