Parameterized complexity of finding small degree-constrained subgraphs

DOI10.1016/j.jda.2011.05.001zbMath1242.68119OpenAlexW2069471278MaRDI QIDQ414424

Omid Amini, Ignasi Sau, Saket Saurabh

Publication date: 11 May 2012

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2011.05.001

zbMATH Keywords

dynamic programmingtreewidthexcluded minorsparameterized complexity\(W[1\)-hardness]degree-constrained subgraphfixed-parameter tractable algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Increasing the Minimum Degree of a Graph by Contractions ⋮ Complexity and Kernels for Bipartition into Degree-bounded Induced Graphs ⋮ Increasing the minimum degree of a graph by contractions ⋮ Tight complexity bounds for FPT subgraph problems parameterized by the clique-width ⋮ Minimum k‐cores and the k‐core polytope ⋮ On the approximability of some degree-constrained subgraph problems ⋮ On approximating the \(d\)-girth of a graph ⋮ Complexity and kernels for bipartition into degree-bounded induced graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Subgraphs of minimal degree \(k\)
• Hardness and approximation of traffic grooming
• The complexity of regular subgraph recognition
• The complexity of uniform Nash equilibria and related regular subgraph problems
• Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
• On the parameterized complexity of multiple-interval graph problems
• Parameterized complexity of finding regular induced subgraphs
• A note on the complexity of finding regular subgraphs
• Long cycles in graphs with no subgraphs of minimal degree 3
• Graph minors. XVI: Excluding a non-planar graph
• Diameter and treewidth in minor-closed graph families
• Finding regular subgraphs in both arbitrary and planar graphs
• Maximum \(k\)-regular induced subgraphs
• Parametrized complexity theory.
• Local tree-width, excluded minors, and approximation algorithms
• Deciding first-order properties of locally tree-decomposable structures
• Induced Subgraphs of the Power of a Cycle
• Finding Dense Subgraphs with Size Bounds
• Degree-Constrained Subgraph Problems: Hardness and Approximation Results
• Connected Coloring Completion for General Graphs: Algorithms and Complexity
• The ring grooming problem
• Approximation algorithms for finding low-degree subgraphs
• Three‐regular subgraphs of four‐regular graphs
• The dense \(k\)-subgraph problem