The PPP -completeness of Ward-Szabó

• Consider the complexity of edge-coloring on a complete graph. • Prove the PPP - and PWPP - completeness of the problems based on the Ward and Szabó theorem. • Introduce some new variants of Pigeon , a PPP -complete problem. • Show the computational aspects of our new variant of Pigeon . Ward and Szabó [1] have shown that a complete graph with N 2 nodes whose edges are colored by at most N colors and at least two colors contains a bichromatic triangle. This fact leads us to a total search problem: Given such a coloring on the complete graph with N 2 nodes, find a bichromatic triangle. Bourneuf et al. [2] have proven that such a total search problem, called Ward-Szabó , is PWPP -hard and belongs to the class TFNP , a class of total search problems in which the correctness of every candidate solution is efficiently verifiable. However, it is open which TFNP subclass contains Ward-Szabó . This paper shows better upper and lower bounds on the computational complexity of Ward-Szabó . We prove that Ward-Szabó is a complete problem for the complexity class PPP , a TFNP subclass of problems in which the existence of solutions is guaranteed by the pigeonhole principle.