Complexity of counting feedback vertex sets

DOI10.4086/CJTCS.2022.001OpenAlexW4226367151MaRDI QIDQ5095623FDOQ5095623

Authors: Kévin Perrot 

Publication date: 10 August 2022

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

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

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

zbMATH Keywords

counting complexity\#Pfeedback arc setscounting minimum solutions

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

Cited In (2)

• Title not available (Why is that?)
• Two Hardness Results on Feedback Vertex Sets

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)