How do I make a sub class return a less general typedef in C++?

Disclaimer: I appreciate that the following might not be the correct way to do things, and would appreciate suggestions on how I might do things correctly.

I have the following typedef.

typedef boost::adjacency_list<boost::setS, boost::vecS, boost::directedS, VertexProperties, boost::no_property, GraphProperties> Witness;

and the following function in my Solver interface.

virtual Witness solve(const Graph& graph) = 0;

My intention is that a Witness will be the (abstract) return type of Solver.solve(). I would like to implement classes that inherit from Solver and implement their own versions of the function solve(). One such class will be a SpecialSolver : public Solver. This SpecialSolver should return something more specialised than a Witness, say, a SpecialWitness. So, the implementation of solve() in SpecialSolver should look something like the following.

Witness SpecialSolver::solve(const Graph& graph)
{
    SpecialWitness Special;

    // Do some stuff

    return Special;
}

My knowledge of templates in C++ is not good. I initially thought that I could do something like this:

typedef boost::adjacency_list<boost::setS, boost::vecS, boost::directedS, SpecialVertexProperties, boost::no_property, SpecialGraphProperties> SpecialWitness;

where SpecialVertexProperties : VertexProperties and SpecialGraphProperties : GraphProperties. Then, SpecialWitness would be a sub type of Witness and I would achieve my desired result. Alas, this is not correct, and I am wondering what the correct design would instead be? How can I make a SpecialWitness a specialised form of Witness, so that I can write the clients of all implementations Solver, simple to the solver interface?