Distance from triviality 2.0: hybrid parameterizations

DOI10.1007/978-3-031-06678-8_1zbMath1497.68360OpenAlexW4285246460MaRDI QIDQ2169932

M. S. Ramanujan, Akanksha Agrawal

Publication date: 30 August 2022

Full work available at URL: https://doi.org/10.1007/978-3-031-06678-8_1

zbMATH Keywords

parameterized complexityvertex deletionelimination distanceH-treewidth

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• Unnamed Item
• Chordal editing is fixed-parameter tractable
• Graph isomorphism parameterized by elimination distance to bounded degree
• Fundamentals of parameterized complexity
• Finding odd cycle transversals.
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• Chordal deletion is fixed-parameter tractable
• The node-deletion problem for hereditary properties is NP-complete
• Fixed-parameter tractability of graph modification problems for hereditary properties
• A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
• Backdoor treewidth for SAT
• Graph minors. XIII: The disjoint paths problem
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Rank-width: algorithmic and structural results
• Parametrized complexity theory.
• Tree-depth, subgraph coloring and homomorphism bounds
• Approximating clique-width and branch-width
• Rank-width and vertex-minors
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• FPT algorithms to compute the elimination distance to bipartite graphs and more
• Measuring Indifference: Unit Interval Vertex Deletion
• Easy problems for tree-decomposable graphs
• Rank-Width and Well-Quasi-Ordering
• Combining Treewidth and Backdoors for CSP.
• Faster Parameterized Algorithms Using Linear Programming
• Interval Deletion Is Fixed-Parameter Tractable
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
• Approximating rank-width and clique-width quickly
• Reducing CMSO model checking to highly connected graphs
• A Fixed-Parameter Tractable Algorithm for Elimination Distance to Bounded Degree Graphs
• Parameterized Complexity of Elimination Distance to First-Order Logic Properties
• Elimination Distance to Bounded Degree on Planar Graphs
• Hitting topological minors is FPT
• Parameterized and Exact Computation
• A Near-Optimal Planarization Algorithm
• Parameterized Algorithms
• Vertex deletion parameterized by elimination distance and even less
• On the Parameterized Complexity of Clique Elimination Distance

This page was built for publication: Distance from triviality 2.0: hybrid parameterizations