A Polynomial-Time Algorithm for the Fractional f-Density

This thesis studies the exact computation of fractional f-density in loopless multigraphs with positive rational edge weights. Fractional f-density is a weighted density parameter arising in f-edge coloring, where each color may be used at a vertex v up to a prescribed capacity f(v). It gives a structural lower bound for the f-chromatic index and generalizes the classical density parameter from ordinary edge-coloring theory. The method uses a linear-fractional optimization framework whose fixed-threshold subproblems are solved through minimum-cut and minimum T-cut computations on an auxiliary graph. The analysis supplies an explicit T-cut encoding of the f-parity condition, restores admissibility for relaxed cut solutions, and handles rational edge weights through denominator-clearing integral scaling. The main result gives an exact computation of fractional f-density with a denominator-aware polynomial-time bound in the graph-size and scaled-weight parameters, placing the computation on a rigorous algorithmic foundation.