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

Subject: Re: [Boost-users] [BGL] Shared nodes on path
From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2014-02-28 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 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?

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
NP-hard problem and the possibility of an exponential number of paths being
output from your algorithm.

-Aaron