Critical path graphs are used for modeling dependencies among the tasks in a project. One representation (an activity-on-edge graph, which we call a critical path graph, or CPG) labels edges with tasks, so that each task has a start vertex and an end vertex. The dependencies among tasks are modeled with additional unlabeled edges (of length zero). Given a nonnegative weight function on the task-labeled edges, the critical path of a CPG is defined the longest path. The longest path is also the shortest possible project completion time. The question arises whether one can find a graph of minimum size (number of vertices) which under every weight function preserves the critical paths of a given graph. We answer this question in the affirmative with a greedy algorithm which repeatedly applies a set of four reduction rules. We further show that the output graph is unique regardless of the order in which the rules are applied.
(Joint work with David Eppstein and Elham Havvaei)