Interval-graph subcoloring with an input color budget → Minimum-cost flow Complexity open
Unsolved
Why this question matters
Moderate: the result would settle a 2002 question that the 2025 subcoloring paper still lists as open and could yield exact channel or interval-resource grouping. It would not resolve subcoloring of general co-comparability graphs.
Marin and Watrigant explicitly list variable-k interval-graph subcoloring as open and cite the fixed-k polynomial algorithm. Their hardness for co-comparability graphs at k at least three does not transfer to interval graphs.
The reduction to construct
An interval graph is given by an explicit list of rational closed intervals and a binary-encoded positive integer k. A valid output partitions the intervals into at most k classes such that the intersection graph induced by each class is a disjoint union of cliques, equivalently has no induced three-vertex path; output NO-SOLUTION exactly when no such partition exists.
An explicit directed network with integer capacities, integer costs and specified supplies and demands is given. A valid output is any minimum-cost integral feasible flow, or INFEASIBLE exactly when no feasible flow exists. All numbers are binary encoded.
Construct deterministic polynomial-time F and G that map every interval-subcoloring instance to a minimum-cost-flow instance and recover a valid class partition from every optimal target flow, preserving infeasibility. This structured reduction would place variable-budget interval subcoloring in P.
High: the known interval-graph algorithm runs in O(k n^(2k+1)), so its state grows with the input budget. A plausible route is to aggregate symmetric color classes along sorted interval endpoints into flow conservation states; the missing step is showing that this aggregation preserves all induced-path constraints.
What a complete answer must include
Define the network and decoder, prove that every optimal flow yields a valid partition and every feasible source partition has a corresponding target flow, and bound network size, costs and both algorithms in bits. Later tests should compare recovered partitions with an independent interval-graph oracle.
References
Literature checked 2026-09-26. Checked MFCS 2025 primary paper, Introduction Section 1.1 and Theorem 9; searched 2026-09-26 for 'interval graph k-subcoloring variable k complexity', 'interval subchromatic number polynomial 2026' and later versions. No matching resolution was found in indexed coverage. Gates 1-4 pass; Gate 5 is a route hold pending a flow state compression lemma; Gate 6 was not assessed.