Find optimal room from which to visit all other rooms in a rectangular floorplan
(This is joint with Jeff Phillips, who refuses to visit cstheory regularly ;))
I'm working with the problem formulation as stated and evolved in the comments. Namely, the goal is to find a minimum number of &quot;robots&quot; who can traverse a partition of an orthogonal polygon into rectangles, with the constraint that:

A room can be entered and exited only in diametrically opposed directions (so north-south OR east-west)
A robot can only cross room boundaries along one (globally chosen) axis (so no 90 degree turns allowed)
Within a room though, a robot can do whatever it likes, as long it crosses room boundaries as specified.
Robots can backtrack arbitrarily as long as they follow the above rules.

So a solution looks like an assignment of &quot;colors&quot; axes (NS or EW) to each room, and a traversal plan where each robot only traverses rooms having the same &quot;color&quot;.
Construct a graph where each rectangle is a vertex and two rectangles are marked as adjacent if they share a boundary. The edge is &quot;colored&quot; NS or EW, depending on the nature of the adjacency.
Claim 1: If we are limited to one axis (NS or EW) then the minimum number of robots is merely the number of components in graph induced by edges of the corresponding color.
Proof: Every edge represents a legal transition in that axis, so placing one robot in each connected component suffices, and you need at least one for each component for coverage.
Now consider the two partitions of the rectangle collection induced by the two colors. Notice that the minimum cardinality partition among these two might be far from optimal if for example your polygon is an L shape with each leg subdivided into n/2 rectangles. The individual graphs each have n/2 components, but the optimal solution is of size 2.
Construct a bipartite graph, in each node is one of the connected components of either of the partitions, and two nodes are connected if their corresponding components intersect. This graph is bipartite because the two sets of components were partitions.
Claim: the size of minimum vertex cover in this graph is the desired optimal soln.
Proof.
Firstly note that in any optimal solution, the set of rectangles covered by any robot must be a subset of one of the components by reachability. Further, it costs nothing for this robot to cover any of the other rectangles in this partition. Hence wlog we can assume that OPT consists of a set of components that together cover all rectangles, i.e a set cover.
Secondly, since the graph is bipartite, we know that any rectangle is represented by exactly one edge between left and right sides. Thus, covering all rectangles actually requires covering all edges in this graph.
QED
VC in bipartite graphs can be solved in polynomial time, so the overall problem can be solved in polynomial time.
Comments ?