May 19th, 2011

beartato phd

(no subject)

I find myself daydreaming about little graph-theoretic/complexity-theoretic puzzlers lately during lunch and on the train and stuff. Here's one I like, with the mathy bits in gray if you want to ignore (or pay special attention to) them:

Imagine a company that has lots of required one-on-one weekly meetings, say, between managers and the people that report to them. This set of meetings can be described as an undirected graph G: every person is a vertex, and there's an edge between them if they have a weekly meeting. A given employee may report to multiple other employees. That is, G is not necessarily tree-shaped. All employees at this company are very lazy, and are only willing to actually stand up and walk to two meetings a week. They have infinite patience, however, for meetings that involve staying at their own desk and having someone else come to them. Is there a way of choosing the meeting-place for every weekly meeting so that no employee has to walk too much? Given a G, is there an assignment of directions to all edges in G such that no vertex has in-degree more than 2? Is there an algorithm that can efficiently answer this question for any set of meetings?

I think I have solved it to my satisfaction, but I'm curious if anyone maybe comes up with a simpler answer, or knows that it is a famous named problem that I just happened to not have heard of already...