11

Here is a rather different application from what you may have had in mind. Linear programming has many practical applications. There are many algorithms for linear programming and those based on George Dantzig's simplex method are among the most commonly implemented. An important parameter of simplex is called the pivoting rule. Victor Klee and George Minty ...


10

Undirected (Vertex) Geography is in P. In particular, the game on graph $G$ with starting vertex $v$ is a win for player 1 if and only if every maximum matching of $G$ uses the vertex $v$. This can be checked in polynomial time. The above is Theorem 1.1 from the paper "Undirected Edge Geography", by Fraenkel, Scheinerman and Ullman, Theoretical Computer ...


7

The answer is yes, for the first game you list! This result was only established in 2019. Here is a link to the paper: Costa et al. 2019 Even more recently, some variants of the first game were proved to be PSPACE-complete. This result can be found here: Marcilon et al. 2019.


2

It sounds like this paper has some of what you're looking for: http://arxiv.org/abs/1202.5762 The general form of the first question is a really simple reduction: using colors {0, ..., n-1}, start with a Node Kayles instance and create a vertex for each of the colors from 1 to n-1 and connect them to each uncolored vertex. Now those colors can't be played ...


Only top voted, non community-wiki answers of a minimum length are eligible