Polynomial-Time Algorithms for Energy Games with Special Weight Structures

Energy games belong to a class of turn-based two-player infinite-duration games played on a weighted directed graph. It is one of the rare and intriguing combinatorial problems that lie in NP∩co-NP, but are not known to be in P. The existence of polynomial-time algorithms has been a major open problem for decades and apart from pseudopolynomial algorithms there is no algorithm that solves any non-trivial subclass in polynomial time. In this paper, we give several results based on the weight structures of the graph. First, we identify a notion of penalty and present a polynomial-time algorithm when the penalty is large. Our algorithm is the first polynomial-time algorithm on a large class of weighted graphs. It includes several worst-case instances on which previous algorithms, such as value iteration and random facet algorithms, require at least sub-exponential time. Our main technique is developing the first non-trivial approximation algorithm and showing how to convert it to an exact algorithm. Moreover, we show that in a practical case in verification where weights are clustered around a constant number of values, the energy game problem can be solved in polynomial time. We also show that the problem is still as hard as in general when the clique-width is bounded or the graph is strongly ergodic, suggesting that restricting the graph structure does not necessarily help.     

Best-order streaming model

We study a new model of computation, called best-order stream, for graph problems. Roughly, it is a proof system where a space-limited verifier has to verify a proof sequentially (i.e., it reads the proof as a stream). Moreover, the proof itself is just a specific ordering of the input data. This model is closely related to many models of computation in other areas such as data streams, communication complexity, and proof checking, and could be used in applications such as cloud computing.In this paper we focus on graph problems where the input is a sequence of edges. We show that even under this model, checking some basic graph properties deterministically requires linear space in the number of nodes. We also show that, in contrast with this, randomized verifiers are powerful enough to check many graph properties in polylogarithmic space.     

Simple FPTAS for the subset-sums ratio problem

In the subset-sums ratio problem, we want to find two sets of numbers such that the ratio between the larger and smaller sets (in terms of the summed values) is as small as possible. We show a new Fully Polynomial-Time Approximation Scheme (FPTAS) for this problem which simplifies the algorithm proposed by [C. Bazgan, M. Santha, Z. Tuza, Efficient approximation algorithms for the SUBSET-SUMS EQUALITY problem, J. Comput. System Sci. 64 (2) (2002) 160–170, announced in ICALP 1998]. The key insight of the new algorithm is to solve the problem with an additional constraint that the output sets must contain some certain numbers. While the new problem is harder (in the sense that the original problem can be reduced to this problem), it still admits an FPTAS, which is surprisingly simpler than the FPTAS of the original problem.