Parameterized complexity of finding subgraphs with hereditary properties.

DOI10.1016/S0304-3975(01)00414-5zbMath1061.68061OpenAlexW1488421129MaRDI QIDQ1853579

Venkatesh Raman, Subhash A. Khot

Publication date: 21 January 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(01)00414-5

zbMATH Keywords

Ramsey numbersParameterized complexityHereditary properties

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (56)

Parameterized algorithms for feedback set problems and their duals in tournaments ⋮ Assessing the Computational Complexity of Multi-layer Subgraph Detection ⋮ Additive approximation of generalized Turán questions ⋮ Computing the similarity of two sequences with nested arc annotations ⋮ Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity ⋮ Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes ⋮ Parameterized complexity of the induced subgraph problem in directed graphs ⋮ The Birth and Early Years of Parameterized Complexity ⋮ Vertex Cover, Dominating Set and My Encounters with Parameterized Complexity and Mike Fellows ⋮ A Basic Parameterized Complexity Primer ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ A parameterized perspective on packing paths of length two ⋮ Counting Small Induced Subgraphs Satisfying Monotone Properties ⋮ Editing to a Planar Graph of Given Degrees ⋮ List-coloring -- parameterizing from triviality ⋮ Editing to a connected graph of given degrees ⋮ Parameterized aspects of strong subgraph closure ⋮ Parameterized complexity of vertex deletion into perfect graph classes ⋮ On the parameterized complexity of the acyclic matching problem ⋮ Wheel-Free Deletion Is W[2-Hard] ⋮ Reducing the vertex cover number via edge contractions ⋮ Essentially tight kernels for (weakly) closed graphs ⋮ Computing dense and sparse subgraphs of weakly closed graphs ⋮ The challenges of unbounded treewidth in parameterised subgraph counting problems ⋮ Parameterized complexity of finding connected induced subgraphs ⋮ Counting Small Induced Subgraphs with Hereditary Properties ⋮ Parameterized Counting and Cayley Graph Expanders ⋮ Parameterized complexity of even/odd subgraph problems ⋮ Dual parameterization and parameterized approximability of subset graph problems ⋮ Hardness of subgraph and supergraph problems in \(c\)-tournaments ⋮ Local search: is brute-force avoidable? ⋮ Unnamed Item ⋮ Parameterized complexity of Eulerian deletion problems ⋮ Multivariate algorithmics for finding cohesive subnetworks ⋮ The Parameterized Complexity of Finding Point Sets with Hereditary Properties ⋮ The parameterized complexity of maximality and minimality problems ⋮ Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles ⋮ Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs ⋮ On the parameterized complexity of reconfiguration problems ⋮ The parameterised complexity of counting connected subgraphs and graph motifs ⋮ Kernels for packing and covering problems ⋮ Dynamic parameterized problems ⋮ Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity ⋮ The parameterized complexity of \(k\)-edge induced subgraphs ⋮ Editing to a planar graph of given degrees ⋮ Parameterizing above or below guaranteed values ⋮ A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems ⋮ Unnamed Item ⋮ Faster graph bipartization ⋮ Parameterized complexity of finding regular induced subgraphs ⋮ Kernel Lower Bounds using Co-Nondeterminism: Finding Induced Hereditary Subgraphs ⋮ Almost 2-SAT is fixed-parameter tractable ⋮ Parameterized Complexity of Eulerian Deletion Problems ⋮ Tractability of König edge deletion problems ⋮ Unnamed Item ⋮ Editing to a graph of given degrees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• The node-deletion problem for hereditary properties is NP-complete
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Perfect Code is \(W[1\)-complete]
• On the parametric complexity of schedules to minimize tardy tasks.
• The complexity of irredundant sets parameterized by size
• Edge-Deletion Problems
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Fixed-Parameter Tractability and Completeness I: Basic Results

This page was built for publication: Parameterized complexity of finding subgraphs with hereditary properties.