Complexity of counting feedback vertex sets

DOI10.4086/CJTCS.2022.001MaRDI QIDQ5095623zbMATH OpenOpenAlexFDO

Authors Kévin Perrot

Publication date 10 August 2022

Published in Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1909.03339

zbMATH Keywords

counting complexity\#Pfeedback arc setscounting minimum solutions

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• On enumerating all minimal solutions of feedback problems
• On the complexity of feedback set problems in signed digraphs
• Feedback arc set in bipartite tournaments is NP-complete
• Exact localisations of feedback sets
• On the minimum feedback vertex set problem: Exact and enumeration algorithms

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A complexity theory for feasible closure properties
• Complexity of counting the optimal solutions
• Hard Enumeration Problems in Geometry and Combinatorics
• On closure properties of \(\#\text{P}\) in the context of \(\text{PF} \circ \#\text{P}\)
• On enumerating all minimal solutions of feedback problems
• PP is closed under truth-table reductions
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• Reducibility among combinatorial problems
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The Complexity of Enumeration and Reliability Problems
• The Complexity of Planar Counting Problems
• The complexity of computing the permanent

Cited in

(2)

• Two Hardness Results on Feedback Vertex Sets
• scientific article; zbMATH DE number 4041287 (Why is no real title available?)

This page was built for publication: Complexity of counting feedback vertex sets

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