Exact Fair Correlation Clustering on a Path with Ratio 1:c → Integral Minimum-Cost Flow Complexity open
Unsolved
Why this question matters
Moderate: it would settle a path case explicitly left open in fair correlation clustering, beyond fixed fairlet-size algorithms, and give an exact algorithm for group-balanced clustering on sparse networks.
Böhm et al. (FORC 2023, Lemmas 4–5 and Conclusion) identify the 1:c path case as open. The 2026 follow-up proves XP in treewidth plus fairlet size and FPT at fairlet size two; neither is polynomial for unbounded input c on paths.
The reduction to construct
Input is an explicitly listed path whose vertices are colored red or blue with |blue|=c|red| for an input integer c≥2. Positive pairs are path edges and all other pairs are negative. A valid output is any partition into clusters each containing red:blue in ratio 1:c that minimizes the number of positive pairs separated plus negative pairs kept together; if no fair partition exists, output NO-SOLUTION.
Input is a directed network with integral capacities and binary rational costs plus supplies and demands. Valid outputs are all integral feasible flows of minimum total cost, or NO-SOLUTION if infeasible.
Construct deterministic polynomial-time F and G such that every minimum-cost integral flow decodes to an optimal fair clustering of the given path, with matching no-solution behavior. This proves polynomial-time solvability for variable c.
High: optimal clusters may be disconnected even on a path, so a flow state cannot simply track contiguous blocks. Variable c makes the natural fairlet-state dynamic program superpolynomial.
What a complete answer must include
Provide deterministic polynomial-time F and G with bit-size bounds. Prove correctness for every legal input and every valid target output, including NO-SOLUTION where defined; independently check recovered answers on representative instances. A generic SAT or ILP encoding alone does not meet the novelty goal.
References
Literature checked 2026-09-26. Web searches 2026-09-26: "fair correlation clustering paths 1:c complexity open", "Fair Correlation Clustering Meets Graph Parameters", and board aliases. Read FORC 2023 Section 2.6 and arXiv:2602.15683 Theorems 1.2–1.4. No later matching classification found. Gate 5 route: combine the minimum-size-fairlet lemma with a flow over red anchors and counts of assigned blue vertices; missing is a polynomial representation of crossing/disconnected clusters. Untested; Gate 6 not assessed.