2025/07/31 by Ishizuka, Takashi
#Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2507.23345
Ward and Szabó [WS94] have shown that a complete graph with N2 nodes whose edges are colored by N colors and that has at least two colors contains a bichromatic triangle. This fact leads us to a total search problem: Given an edge-coloring on a complete graph with N2 nodes using at least two colors and at most N colors, find a bichromatic triangle. Bourneuf, Folwarczný, Hubácek, Rosen, and Schwartzbach [Bou+23] have proven that such a total search problem, called Ward-Szabó, is PWPP-hard and belongs to the class TFNP, a class for 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 will improve 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.