Re: [Boost-users] [BGL] Shared nodes on path

Subject: Re: [Boost-users] [BGL] Shared nodes on path
From: Sensei (senseiwa_at_[hidden])
Date: 2014-02-28 07:49:54

On 27/02/14 18:11, Aaron Windsor wrote:
> Hi,
>
> As described, your problem is NP-hard, 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_{n-2}, 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 n-1 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 NP-hard, 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!