1. Revising Johnson’s table for the 21st century
- Author
-
D. Sasaki, Ana Silva, Celina M. H. de Figueiredo, and Alexsander Andrade de Melo
- Subjects
Discrete mathematics ,Polynomial ,Applied Mathematics ,0211 other engineering and technologies ,Parameterized complexity ,021107 urban & regional planning ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Column (database) ,Steiner tree problem ,symbols.namesake ,010201 computation theory & mathematics ,Path (graph theory) ,symbols ,Discrete Mathematics and Combinatorics ,Table (database) ,Point (geometry) ,Row ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
What does it mean today to study a problem from a computational point of view? We focus on parameterized complexity and on Column 16 “Graph Restrictions and Their Effect” of D.S. Johnson’s Ongoing guide, where several puzzles were proposed in a summary table with 30 graph classes as rows and 11 problems as columns. Several of the 330 entries remain unclassified into Polynomial or NP -complete after 35 years. We provide a full dichotomy for the Steiner Tree column by proving that the problem is NP -complete when restricted to Undirected Path graphs. We revise Johnson’s summary table according to the granularity provided by the parameterized complexity for NP -complete problems.
- Published
- 2022