Revising Johnson's table for the 21st century
From MaRDI portal
Publication:2091799
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.
Recommendations
- Steiner trees for hereditary graph classes: a treewidth perspective
- Parameterized complexity of arc-weighted directed Steiner problems
- scientific article; zbMATH DE number 219235
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Parameterized complexity of arc-weighted directed Steiner problems
Cites work
- \(k\)-NLC graphs and polynomial algorithms
- A Linear Time Algorithm for Deciding Interval Graph Isomorphism
- A partial k-arboretum of graphs with bounded treewidth
- A recognition algorithm for the intersection graphs of paths in trees
- A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
- An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
- Approximating clique-width and branch-width
- Approximating rank-width and clique-width quickly
- Approximating the minimum clique cover and other hard problems in subtree filament graphs
- Approximation algorithms for NP-complete problems on planar graphs
- Bandwidth contrained NP-complete problems
- Bounded clique cover of some sparse graphs
- Clique cover on sparse networks
- Complexity of Finding Embeddings in a k-Tree
- Dominating set is fixed parameter tractable in claw-free graphs
- Dominating Sets in Chordal Graphs
- Edge dominating set and colorings on graphs with fixed clique-width
- Efficient graph representations
- Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
- Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- Finding Branch-Decompositions and Rank-Decompositions
- Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
- Fixed Linear Crossing Minimization by Reduction to the Maximum Cut Problem
- Fourier meets M\"{o}bius: fast subset convolution
- Fundamentals of parameterized complexity
- Generalized planar matching
- Genus characterizes the complexity of certain graph problems: Some tight results
- Genus g Graphs Have Pagenumber O(√g)
- Graph classes with structured neighborhoods and algorithmic applications
- Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
- Graph isomorphism for \(K_{3,3}\)-free and \(K_5\)-free graphs is in Log-space
- Hamilton Paths in Grid Graphs
- HAMILTONian circuits in chordal bipartite graphs
- Hamiltonian circuits in interval graph generalizations
- Hardness of r-dominating set on graphs of diameter (r + 1)
- scientific article; zbMATH DE number 1696630 (Why is no real title available?)
- scientific article; zbMATH DE number 3878376 (Why is no real title available?)
- scientific article; zbMATH DE number 3815666 (Why is no real title available?)
- scientific article; zbMATH DE number 3906530 (Why is no real title available?)
- scientific article; zbMATH DE number 3974318 (Why is no real title available?)
- scientific article; zbMATH DE number 4051024 (Why is no real title available?)
- scientific article; zbMATH DE number 3694608 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1095171 (Why is no real title available?)
- scientific article; zbMATH DE number 1979505 (Why is no real title available?)
- scientific article; zbMATH DE number 2044943 (Why is no real title available?)
- scientific article; zbMATH DE number 3445275 (Why is no real title available?)
- scientific article; zbMATH DE number 806748 (Why is no real title available?)
- scientific article; zbMATH DE number 1414279 (Why is no real title available?)
- scientific article; zbMATH DE number 6737879 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
- Improved Parameterized Upper Bounds for Vertex Cover
- Intersection graphs of paths in a tree
- Kernelization. Theory of parameterized preprocessing
- Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Linear time solvable optimization problems on graphs of bounded clique-width
- Maximum cut on line and total graphs
- Mim-width. III. Graph powers and generalized distance domination problems
- MSOL partitioning problems on graphs of bounded treewidth and clique-width
- Network sparsification for Steiner problems on planar and bounded-genus graphs
- Node-and edge-deletion NP-complete problems
- NP-completeness of edge-colouring some restricted graphs
- On the Algorithmic Complexity of Total Domination
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- Parameterized algorithms
- Parameterized complexity of directed Steiner tree on sparse graphs
- Parameterized complexity of independent set in \(H\)-free graphs
- Parameterized domination in circle graphs
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Partition into cliques for cubic graphs: Planar case, complexity and approximation
- Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
- Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
- Recent developments on graphs of bounded clique-width
- Reducibility among combinatorial problems
- Rooted directed path graphs are leaf powers
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
- Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
- Some simplified NP-complete graph problems
- Steiner problem in Halin networks
- Steiner trees, connected domination and strongly chordal graphs
- Steiner trees, partial 2–trees, and minimum IFI networks
- The behavior of clique-width under graph operations and graph transformations
- The Complexity of Coloring Circular Arcs and Chords
- The complexity of domination problems in circle graphs
- The complexity of SIMPLE MAX-CUT on comparability graphs
- The dominating set problem is fixed parameter tractable for graphs of bounded genus
- The Hamiltonian circuit problem for circle graphs is NP-complete
- The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
- The NP-completeness column: an ongoing guide
- The NP-Completeness of Edge-Coloring
- The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
- The steiner problem in graphs
- Unit disk graphs
- Upper bounds to the clique width of graphs
Cited in
(6)- Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage
- MaxCut on permutation graphs is NP‐complete
- Maximum cut on interval graphs of interval count four is NP-complete
- Further split graphs known to be class 1 and a characterization of subgraph-overfull split graphs
- Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs
- Chromatic index under parameterized settings
This page was built for publication: Revising Johnson's table for the 21st century
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2091799)
