2014/02/11 by Muhammad Ali Khan, Khan, Muhammad Ali
Computer Science · Engineering · Business, Management and Accounting · #Complexity and Algorithms in Graphs #Optimization and Packing Problems #Consumer Market Behavior and Pricing
paper · pdf · doi:10.48550/arxiv.1402.2456
Reid conjectured that any finite set of non-negative integers is the score set of some tournament and Yao gave a non-constructive proof of Reid's conjecture using arithmetic arguments. No constructive proof has been found since. In this paper, we investigate a related problem, namely, which sets of integers are imbalance sets of tournaments. We completely solve the tournament imbalance set problem (TIS) and also estimate the minimal order of a tournament realizing an imbalance set. Our proofs are constructive and provide a pseudo-polynomial time algorithm to realize any imbalance set. Along the way, we generalize the well-known equal sum subsets problem (ESS) to define the equal sum sequences problem (ESSeq) and show it to be NP-complete. We then prove that ESSeq reduces to TIS and so, due to the pseudo-polynomial time complexity, TIS is weakly NP-complete.