Oh well, noone else writes, so I will also explain my not-best solutions:
Enjoying a Multiplayer Game
The "can shoot" relation turned out to be symmetric.
The shortest scenario is always of length 1 - you can just find a maximal (not neccessarily the maximum) matching in the graph and have those pairs of people shoot each other. The rest can shoot whoever they want. The remaining graph after this round will have no edges.
The long scenario: In each step I try to find a small set of people that should die this round. This set must "cover" everybody - so I am looking for a small set cover, where each set covers the neighbors of a vertex.
Start by choosing neighbors of degree-1 vertices - they must be chosen. Then I take guys that are not covered yet, from the smallest degree (resolve ties randomly). For each of them, pick one neighbor to shoot. I ended up picking the neighbor with the smallest number of already chosen neighbors (ties randomly).
Repeat the long scenario algorithm 7 times and choose the longest