2012/02/17 by Fraser Stewart, Stewart, Fraser
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1202.4658
arxiv created 2012/04/03 · arxiv updated 2012/04/04
Hackenbush is a two player game, played on a graph with coloured edges where players take it in turns to remove edges of their own colour. It has been shown that under normal play rules Red-Blue Hackenbush (all edges are coloured either red or blue) is NP-hard. We will show that Red-Blue Hackenbush is in P, but that Red-Blue-Green Hackenbush is NP-Hard, when played under misère rules.