Back to Search
Start Over
The complexity of the parity argument with potential.
- Source :
-
Journal of Computer & System Sciences . Sep2021, Vol. 120, p14-41. 28p. - Publication Year :
- 2021
-
Abstract
- The parity argument principle states that every finite graph has an even number of odd degree vertices. We consider the problem whose totality is guaranteed by the parity argument on a graph with potential. In this paper, we show that the problem of finding an unknown odd-degree vertex or a local optimum vertex on a graph with potential is polynomially equivalent to EndOfPotentialLine if the maximum degree is at most three. However, even if the maximum degree is 4, such a problem is PPA ∩ PLS -complete. To show the complexity of this problem, we provide new results on multiple-source variants of EndOfPotentialLine , which is the canonical problem for EOPL. This result extends the work by Goldberg and Hollender; they studied similar variants of EndOfLine. [ABSTRACT FROM AUTHOR]
- Subjects :
- *ODD numbers
*ARGUMENT
Subjects
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 120
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 150188338
- Full Text :
- https://doi.org/10.1016/j.jcss.2021.03.004