The parameterized complexity of \(k\)-edge induced subgraphs

DOI10.1016/J.IC.2016.10.004zbMath1355.68127OpenAlexW2563974133MaRDI QIDQ729817

Yijia Chen, Bingkai Lin

Publication date: 22 December 2016

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2016.10.004

zbMATH Keywords

fixed-parameter tractable\(\# \operatorname{W}[1\)-hard]\(k\)-edge induced subgraph

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Chordless paths through three vertices
• Parameterized complexity of finding regular induced subgraphs
• The parameterized complexity of the induced matching problem
• \(E\Upsilon PHKA\)! \(\mathrm{num}=\Delta +\Delta +\Delta\)
• Fixed-parameter tractability of graph modification problems for hereditary properties
• On limited nondeterminism and the complexity of the V-C dimension
• Graphs with a small number of distinct induced subgraphs
• Parameterized complexity of finding subgraphs with hereditary properties.
• The complexity of first-order and monadic second-order logic revisited
• An existential locality theorem
• Computing crossing numbers in quadratic time
• Parametrized complexity theory.
• Parameterized counting problems
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• Deciding first-order properties of locally tree-decomposable structures
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• Understanding the Complexity of Induced Subgraph Isomorphisms
• Induced subgraphs with distinct sizes
• The Complexity of Enumeration and Reliability Problems
• Deciding First-Order Properties of Nowhere Dense Graphs
• The Parameterized Complexity of Counting Problems
• Detecting even holes
• Model Theory Makes Formulas Large
• A Simple Algorithm for the Graph Minor Decomposition − Logic meets Structural Graph Theory–

This page was built for publication: The parameterized complexity of \(k\)-edge induced subgraphs