Computational Complexity of Cycle Discrepancy

Abstract

<p align="justify" The irregularities or the deviations from the state of absolute uniformity are the core focus of the area of discrepancy theory. Cycle discrepancy is about the quantification of the least possible deviation of bi-labeling of graph vertices from an ideal bi-labeling which divides each cycle of a graph in two equal parts. This paper shows that it is NP-hard to compute the cycle discrepancy of a given graph. A polynomial time reduction of Hamiltonian problem to the problem of computing cycle discrepancy is used to establish this result