2016/09/06 by Comin, Carlo, Rizzi, Romeo
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1609.01517
This study strengthens the links between Mean Payoff Games (\MPGs) and Energy Games (EGs). Firstly, we offer a faster O(|V|2|E|W) pseudo-polynomial time and Θ(|V|+|E|) space deterministic algorithm for solving the Value Problem and Optimal Strategy Synthesis in \MPGs. This improves the best previously known estimates on the pseudo-polynomial time complexity to: O(|E|log |V|) + Θ(∑v∈ VdegΓ(v)⋅ℓΓ(v)) = O(|V|2|E|W), where ℓΓ(v) counts the number of times that a certain energy-lifting operator δ(⋅, v) is applied to any v∈ V, along a certain sequence of Value-Iterations on reweighted \EGs; and degΓ(v) is the degree of v. This improves significantly over a previously known pseudo-polynomial time estimate, i.e. Θ(|V|2|E|W + ∑v∈ VdegΓ(v)⋅ℓΓ(v)) \citepCR15, CR16, as the pseudo-polynomiality is now confined to depend solely on ℓΓ. Secondly, we further explore on the relationship between Optimal Positional Strategies (OPSs) in \MPGs and Small Energy-Progress Measures (SEPMs) in reweighted \EGs. It is observed that the space of all OPSs, optΓΣM0, admits a unique complete decomposition in terms of extremal-SEPMs in reweighted EGs. This points out what we called the "Energy-Lattice X^*Γ associated to optΓΣM0". Finally, it is offered a pseudo-polynomial total-time recursive procedure for enumerating (w/o repetitions) all the elements of X^*Γ, and for computing the corresponding partitioning of optΓΣM0.