Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.23345 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911639115137024 |
|---|---|
| author | Ishizuka, Takashi |
| author_facet | Ishizuka, Takashi |
| contents | Ward and Szabó [WS94] have shown that a complete graph with $N^2$ 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 $N^2$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_23345 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The PPP-completeness of the Ward-Szabo theorem Ishizuka, Takashi Computational Complexity Discrete Mathematics Ward and Szabó [WS94] have shown that a complete graph with $N^2$ 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 $N^2$ 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. |
| title | The PPP-completeness of the Ward-Szabo theorem |
| topic | Computational Complexity Discrete Mathematics |
| url | https://arxiv.org/abs/2507.23345 |