Stephen Fenner, Rohit Gurjar, Arpita Korwar, and Thomas Thierauf
Abstract:
We consider the complexity of determining the winner of a finite, two-level poset game.
This is a natural question, as it has been shown recently that determining the winner of a finite, three-level poset game is PSPACE-complete.
We give a simple formula allowing one to compute the status of a type of two-level poset game that we call parity-uniform.
This class includes significantly more easily solvable two-level games than was known previously.
We also establish general equivalences between various two-level games.
These equivalences imply that for any n, only finitely many two-level posets with n minimal elements need be considered, and a similar result holds for two-level posets with n maximal elements.
To compare the complexity of the perfect matching problem for general graphs with that for planar graphs, one might try to come up with a reduction from the perfect matching problem to the planar perfect matching problem.
The obvious way to construct such a reduction is via a planarizing gadget, a planar graph which replaces all edge crossings of a given graph.
We show that no such gadget exists. This provides a further indication that the complexity of the two problems is different.