Square-Cut Pizza Sharing is PPA-complete

30^th June 2021, 13:00
Argyrios Deligkas
Royal Holloway University of London

Abstract

We study the computational complexity of computing solutions for the square-cut pizza sharing problem. In this problem, we have n mass distributions in the plane, and the task is to find a path that uses horizontal and vertical segments that splits each of the masses in half while making at most n−1 turns. We show that finding an approximate solution to this problem is PPA-complete, while finding an exact solution is FIXP-hard and in BU. Our PPA-hardness result applies even when all mass distributions are unions of non-overlapping squares, and our FIXP-hardness result applies even when all mass distributions are unions of weighted squares and right-angled triangles. When the path is restricted to have at most n−2 turns, we show that the approximate problem becomes NP-complete, and the exact problem becomes ETR-complete.

Additional Materials

• https://arxiv.org/abs/2012.14236