val = get(pmap, k)

So apparently, the concept definition actually requires that property maps are never const - which is admittedly a little weird.

It sounds like we're now on the same page! The above essentially means that it becomes literally impossible to write perfectly const-correct code (from a user standpoint). While const-incorrect code is bad enough, it also means that I may be missing out on potential compiler optimizations, that bugs me quite a bit more.

What may be done to remedy this?

I will admit that writing perfectly const-correct code can be very, very difficult in many situations :) However, I'll defer to more experienced Boosters with regards that its impossible. I will also say that const-incorrect code isn't necessarily "bad". There are times that ignoring const-ness is quite useful.

In this particular instance, I will cautiously say that the concept definition is implemented incorrectly. If the constraints() funciton did this:

property_map<Key, Graph>::type pm = get(...);

instead of:

pm = get(),

It would preserve the const'ness of the pmap object, and the compiler error might not exist.

I also wouldn't worry about compiler optimizations in this case. The compiler is going to elide all or most of the pmap copies and inline all off the function calls to the underlying data structures. Generally, you'll never see the statement (pm = get(...)) in Boost.Graph algorithms.