Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-120 | 21st June 2018 20:39

The Complexity of Multi-source Variants of the End-of-Line Problem, and the Concise Mutilated Chessboard


Authors: Alexandros Hollender, Paul Goldberg
Publication: 24th June 2018 17:17
Downloads: 1099


The complexity class PPAD is usually defined in terms of the END-OF-LINE problem, in which we are given a concise representation of a large directed graph having indegree and outdegree at most 1, and a known source, and we seek some other degree-1 vertex. We show that variants where we are given multiple sources and seek one solution or multiple solutions are PPAD-complete. Our proof also shows that a multiple source SINK problem where we look for multiple sinks instead of one is equivalent to SINK (i.e. PPADS-complete). Using our result, we provide a full proof of PPAD-completeness of IMBALANCE. Finally, we use these results together with earlier work on the 2D-Brouwer problem to investigate the complexity of a new total search problem inspired by the mutilated chessboard tiling puzzle.

ISSN 1433-8092 | Imprint