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...
Tags:
• #### (no subject)

A paper on describing circuits in an agda DSL: http://www.staff.science.uu.nl/~swier004/publications/2015-types-draft.pdf

• #### (no subject)

Going more carefully now through this little tutorial on fpga programming with the iCEstick. It's in spanish, which makes it slightly more…

• #### (no subject)

Some further progress cleaning up the https://xkcd.com/1360/ -esque augean stables that is my hard drive. Tomato chicken I made a couple days ago…

• #### Error

Anonymous comments are disabled in this journal

default userpic