Simple proof of hardness of feedback vertex set

DOI10.4086/TOC.2016.V012A006MaRDI QIDQ2816412zbMATH OpenOpenAlexFDO

Authors Euiwoong Lee, Venkatesan Guruswami

Publication date 22 August 2016

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2016.v012a006

zbMATH Keywords

feedback vertex setinapproximabilityUG-hardness

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• Two Hardness Results on Feedback Vertex Sets
• scientific article; zbMATH DE number 970357
• Hardness of vertex deletion and project scheduling
• scientific article; zbMATH DE number 3876618
• scientific article; zbMATH DE number 3848625

Cites work

• Gaussian bounds for noise correlation of functions
• On the power of unique 2-prover 1-round games

Cited in

(11)

• Target set selection for conservative populations
• Two Hardness Results on Feedback Vertex Sets
• Euler digraphs
• Hardness of vertex deletion and project scheduling
• Hardness of vertex deletion and project scheduling
• Parameterized algorithms for generalizations of directed feedback vertex set
• A constant factor approximation for directed feedback vertex set in graphs of bounded genus
• Data reduction for directed feedback vertex set on graphs without long induced cycles. Three rules to rule them all
• The PACE 2022 parameterized algorithms and computational experiments challenge: directed feedback vertex set
• Finding small feedback arc sets on large graphs
• Parameterized complexity of MinCSP over the point algebra

This page was built for publication: Simple proof of hardness of feedback vertex set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2816412)