Novice Difficulties with Graph Problem Reduction in Algorithm DesignCER
Problem reduction is a core practice in computer science and a central learning goal in CS education. In algorithm design, it involves transforming complex problems into standard forms so they can be solved using canonical algorithms. Graph layering provides an interesting context for studying how students learn/use problem reduction in algorithm design: while graph layering provides a specific schema of problem reduction for certain problem types, it is also complex, requiring the coordination of several abstract and difficult concepts. In this study, we conducted think-aloud interviews with 15 students to investigate how novices approach graph layering in algorithm design tasks. Using thematic analysis, we identified three common difficulties: incorrect application of dynamic programming, inappropriate use of standard graph algorithms, and errors in graph layering construction. These difficulties resonate with broader challenges in CS education, including surface-level problem categorization, weaknesses in reduction-based reasoning, and struggles with abstraction and state-based modeling. Together, our findings highlight how students struggle with graph layering and suggest directions for instructional support for this and other advanced theory topics in computer science.