IIT Kharagpur's new paper shows fair allocation is NP-hard even on paths

A team from IIT Kharagpur — Susobhan Bandopadhyay, Anish Datta, Palash Dey, Ashlesha Hota, and Abhishek Sahu — has published a new paper, "Fair, Efficient and Connected Allocations on Graphs" (arXiv:2608.18703), accepted to the Algorithmic Decision Theory (ADT) 2026 conference in Paris. The work maps the computational complexity of dividing resources when allocations must be both fair (maximizing egalitarian or utilitarian welfare) and connected on a graph structure. The authors establish a sharp dichotomy: the problem is NP-hard even on extremely simple graph classes like paths, trees, and cycles, yet polynomial-time solvable on stars. However, that tractability breaks down immediately — even two disjoint stars become hard.

Moving to parameterized complexity, the researchers show the problems become fixed-parameter tractable (FPT) when parameterized by the number of agents, specifically on trees. They also prove a robust transfer theorem: if a connected graph class is tractable, then disjoint unions of graphs from that class inherit tractability. Looking at treewidth and treedepth, the utilitarian version is FPT for both parameters, but the egalitarian version stays para-NP-hard even on graphs of treedepth two. When parameterizing by the number of connected components, the problems remain hard except for star collections, where egalitarian is para-NP-hard and utilitarian is W[2]-hard but admits an XP algorithm. These results give a near-complete complexity landscape for connected fair allocation.