It seems like there are a number of states (beards), with transitions only being possible between some of those states. Map that all out and it's a graph theory problem - how many can you visit in one go?
We can transform it into a more classic problem (visit every single node) by adding more edges with weights, where the weight is how long it would take to grow enough beard to make an otherwise invalid transition.
What's the minimal number of such beard-paths required to cover the beard-graph, and what's the best algorithm to construct such a cover? Now, suppose we weight each beard-vertex by how long it takes to grow -- what's the least-weight beard-path cover, where the weight of a beard-path is determined by the maximum-weight (starting) beard-vertex?
Well you can get from any beard to any other with time and a trim, so the graph would be complete, and thus have n(n-1)/2 edges. As for constructing the cover, I guess you could divide the face into the relevant areas (sideburns, lower sideburns, cheek, center chin, edge chin, middle moustache, edge moustache, moustache to chin connectors, etc) and note how long each section is for a given beard style. Given the rate of hair growth (or if it's non-linear, an equation for the time to get from one length to another), you can then work out how much growth (if any) is required to get from one style to another.
I'm confident the graph construction can be done in poly time (O(n^2) edges), solving it is harder obviously! However, if this work is correct, we have a polytime reduction to TSP, thus showing that the "beard problem" is NP-complete.
Edit: Crap, that's the wrong way round to show NP completeness isn't it? You'd have to show that, given a TSP problem you can reformulate it as a beard problem. I'm not sure if a beard problem necessarily exists for every TSP problem, I'll think on it...
Update: Ok, the first part is to make sure we can represent all the nodes / edges, and we can. We just need to increase the number of segments (areas of hair growth we are concerned with) to match the number of nodes. If we have three nodes, A, B, C, then we need three areas corresponding to them. For a given node, we set the area corresponding to it to the maximum distance between that node and other nodes. Once this is done, we set the other areas so that the distance, in hair growth, from each node to the others matches the graph. This then works.
However, this only works for a complete graph. I can't think of a way to easily resolve that, i.e. make it not permissable to get from some nodes to others without going via intermediaries... You could make it so going from one beard style to another means you will have a third along the way, but it seems non-trivial to enforce that.
So, we can reduce TSP on a complete graph to a beard problem. I think we can maybe convert a non-complete TSP to a complete one by adding arbitrarily heavy edges? However, this would necessitate extremely long beards, perhaps impossibly long. Thoughts?
I was imagining a simpler model, where different areas of the beard are either present or not; length doesn't matter. If you're growing one part out, you might as well grow all of it out. Therefore, in this model, you only "grow" to the full beard vertex.
I'm not sure that your reduction from TSP works. Given two nodes A and B, I understand that you're setting their distance on the associated facial areas to match the distance in TSP, but what if they're forced to be even more distant on the area corresponding to some other node C?
We can transform it into a more classic problem (visit every single node) by adding more edges with weights, where the weight is how long it would take to grow enough beard to make an otherwise invalid transition.