Graph Path and Cycle Formulations for Combinatorial Scheduling

40 concepts32 papers1 proposal

Combinatorial optimization problems—such as scheduling sports tournaments, allocating cloud resources, routing autonomous vehicle fleets, or designing personalized curricula—are notoriously difficult. Their search spaces grow exponentially with the number of variables, and they are frequently burdened by a messy web of real-world constraints.

To bypass this exponential complexity, a powerful research direction reformulates these discrete, highly constrained problems as path or cycle optimization problems on structured directed graphs. The core intuition is elegant: by embedding feasibility constraints directly into the graph's topology, we turn a global constraint-satisfaction nightmare into a local network traversal. Once an optimization problem is mapped onto a graph where nodes represent valid states and edges represent permissible transitions, classical graph algorithms (like Dijkstra's algorithm, dynamic programming, or minimum-weight cycle covers) can find exact or near-optimal global solutions in polynomial time.

Mapping Constraints to Graph Topology

The first step in this strategy is translating a complex combinatorial space into a graph where invalid sequences are physically impossible to traverse. Instead of evaluating a massive space of all potential schedules and filtering out those that violate rules, researchers construct a graph where every path automatically represents a valid, feasible solution.

In sports scheduling, for example, creating a tournament schedule requires balancing home/away sequences, stadium availability, and travel logistics. Richard Hoshino in The Multi-Round Balanced Traveling Tournament Problem demonstrates that this can be achieved by representing a tournament schedule as a directed graph. Here, each vertex corresponds to a valid, pre-computed sub-schedule block, and edges denote permissible transitions between them. The authors of Balancing the Traveling Tournament Problem for Weekday and Weekend Games leverage this exact structure, applying Dijkstra's algorithm to find the shortest path from a source node to a sink node, which directly yields a globally optimal schedule that respects complex weekday and weekend constraints.

[Start] ---> (Valid Sub-Schedule Block A) ---> (Valid Sub-Schedule Block B) ---> [End]
                  \                                 ^
                   \---> (Valid Sub-Schedule Block C)------/

This structural mapping applies across diverse domains:

Translating Global Objectives to Edge Weights

Once the graph's topology guarantees that any path is feasible, the global optimization objective—whether it is minimizing energy consumption, financial cost, human effort, or latency—is mapped directly onto the edge weights. The problem of finding the best possible configuration is thus reduced to finding the shortest path.

For instance, in hardware optimization, Yumin Zhang et al. tackle processor energy reduction in Energy minimization of real-time tasks on variable voltage processors with transition energy overhead. They construct a complete bipartite graph where nodes signify possible voltage configurations for tasks, and edges represent the energy overhead of switching between those voltages. The minimum-energy voltage schedule is simply the shortest path through this network.

Similarly, in mobile edge computing, Xuejun Li et al. present a deterministic strategy in A Novel Graph-based Computation Offloading Strategy for Workflow Applications in Mobile Edge Computing. By mapping parallel, selective, and iterative task dependencies into a specialized transitive graph, they use shortest-path algorithms to find the most energy-efficient offloading strategy within strict deadline constraints, running up to 540 times faster than iterative meta-heuristics.

This paradigm of mapping costs to edge weights appears repeatedly across the literature:

Scaling to Multi-Agent Coordination and Cyclic Tasks

While single shortest-path formulations work well for individual trajectories or sequential decisions, many real-world problems require coordinating multiple entities simultaneously or managing infinite, recurring horizons. To handle this, the framework scales from finding a single path to optimizing path covers, disjoint paths, or closed cycle covers.

Multi-Agent and Fleet Routing

When multiple agents must be routed without conflict, the problem can be framed as finding multiple disjoint paths across a shared network. In Learning-based Online Optimization for Autonomous Mobility-on-Demand Fleet Control, Kai Jungel et al. model autonomous taxi fleet routing as a $k$-disjoint shortest paths problem on a directed graph. Nodes represent service requests or locations, and paths represent individual vehicle trajectories. Because this formulation allows for polynomial-time optimization, it enables city-scale dispatching and rebalancing in real-time.

Similarly, Abhimanyu Das et al. in Minimizing Latency in Online Ride and Delivery Services utilize concatenation graphs to determine the optimal sequence for visiting groups of requests, converting abstract tree-based request sets into concrete, time-ordered vehicle trajectories that minimize user wait times. For workforce management, Hoong Chuin Lau in COMBINATORIAL APPROACHES FOR HARD PROBLEMS IN MANPOWER SCHEDULING reduces non-cyclic shift assignment problems with ordered workstretches to finding an optimal path cover in a DAG, enabling polynomial-time scheduling solutions.

Multi-Agent Routing (k-Disjoint Paths):
Node 1 ----> Node 2 ----> Node 3  (Vehicle Path 1)
Node 4 ----> Node 5 ----> Node 6  (Vehicle Path 2)

Cycle Covers for Tournaments and Persistent Tasks

For problems that naturally repeat or require entities to return to their starting states, schedules are modeled as closed loops, or cycle covers.

In inter-league sports scheduling, Richard Hoshino tackles the Bipartite Traveling Tournament Problem in The Inter-League Extension of the Traveling Tournament Problem and its Application to Sports Scheduling and Scheduling Bipartite Tournaments to Minimize Total Travel Distance. By modeling schedules as minimum-weight 4-cycle-covers and triangle packings, teams are grouped into closed loops of road trips (e.g., three consecutive away games before returning home). This graph-theoretic grouping minimizes total league travel distance by optimizing the sequence of interactions within tightly bounded cycles.

To provide theoretical guarantees for these types of problems, Jingyang Zhao 0001 et al. in The Linear Distance Traveling Tournament Problem Allows an EPTAS use an optimal $k$-path packing within a selected subgraph of teams. This packing serves as a structural backbone that guides team interactions, yielding a schedule within $(1 + \varepsilon)$ of the absolute theoretical minimum travel distance.

Cycle-Cover Optimization (Closed Loops):
  (Team A) --------> (Team B)
     ^                  |
     |                  v
  (Team D) <-------- (Team C)

For infinite-horizon robotic missions, Alphan Ulusoy et al. in Optimal Multi-Robot Path Planning with Temporal Logic Constraints transition from simple paths to optimal prefix-suffix cycles within a finite state graph. This formulation guarantees that high-level Linear Temporal Logic constraints (such as persistent surveillance or data gathering rules) are satisfied indefinitely while minimizing the maximum latency between recurring tasks.

Finally, this perspective can be inverted to optimize the underlying graph structure itself. In data center scheduling, Samir Khuller et al. in Energy Efficient Scheduling via Partial Shutdown use configuration graphs to represent valid job assignments, finding a shortest path to select an optimal machine activation subset. Taking this topology-driven view to reinforcement learning, the authors of Discovering Options That Minimize Average Planning Time show that planning time in a Markov Decision Process can be minimized by directly optimizing the graph topology of temporal abstractions (options) to reduce the average shortest-path distance between all state pairs, accelerating value iteration convergence.

Why the Idea Works

Reframing combinatorial scheduling as graph path optimization works because it decouples feasibility from optimality:

  1. Feasibility via Construction: By making invalid schedules topologically impossible within the graph, the algorithm never wastes clock cycles exploring dead ends or illegal states.
  2. Optimality via Network Flow: Once the graph is built, the global optimization objective is offloaded to highly mature, mathematically rigorous network flow and shortest-path algorithms.

Whether navigating a single optimal path for a student's curriculum or packing disjoint cycles to route a professional sports league, this direction transforms intractable combinatorial explosions into structured, verifiable, and efficient graph traversals.

Key Foundational Work

COMBINATORIAL APPROACHES FOR HARD PROBLEMS IN MANPOWER SCHEDULING (1996) — contributed 1 concept elements to this direction.
Membership Questions for Timed and Hybrid Automata (1998) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_cycle_cover_optimization_73703953,
  title = {cycle-cover optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/cycle-cover-optimization/rdr_73703953116849b780c7612f079dc6ed},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_cycle_cover_optimization_73703953_v1,
  title = {cycle-cover optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/cycle-cover-optimization/rdr_73703953116849b780c7612f079dc6ed/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake