research
∙
06/29/2021
Yin-Yang Puzzles are NP-complete
We prove NP-completeness of Yin-Yang / Shiromaru-Kuromaru pencil-and-pap...
share
research
∙
03/11/2021
Hardness of Token Swapping on Trees
Given a graph where every vertex has exactly one labeled token, how can ...
research
∙
07/31/2020
New Results in Sona Drawing: Hardness and TSP Separation
Given a set of point sites, a sona drawing is a single closed curve, dis...
research
∙
03/17/2019
Circumscribing Polygons and Polygonizations for Disjoint Line Segments
Given a planar straight-line graph G=(V,E) in R^2, a circumscribing poly...
research
∙
08/22/2018
Cookie Clicker
Cookie Clicker is a popular online incremental game where the goal of th...
research
∙
06/09/2018
Computational Complexity of Motion Planning of a Robot through Simple Gadgets
We initiate a general theory for analyzing the complexity of motion plan...
research
∙
04/26/2018
Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
We analyze the computational complexity of the many types of pencil-and-...
research
∙
03/09/2018
Computational Complexity of Generalized Push Fight
We analyze the computational complexity of optimally playing the two-pla...
research
∙
07/11/2017
A simple proof that the (n^2-1)-puzzle is hard
The 15 puzzle is a classic reconfiguration puzzle with fifteen uniquely ...
research
∙
06/30/2017
Hamiltonicity is Hard in Thin or Polygonal Grid Graphs, but Easy in Thin Polygonal Grid Graphs
In 2007, Arkin et al. initiated a systematic study of the complexity of ...
research
∙
06/24/2017
Tree-Residue Vertex-Breaking: a new tool for proving hardness
In this paper, we introduce a new problem called Tree-Residue Vertex-Bre...
research
∙
06/21/2017
