On the Parameterized Complexity of Counting Small-Sized Minimum (S,T)-Cuts

DOI10.1137/21M1398203MaRDI QIDQ6157971zbMATH OpenOpenAlexFDO

Authors Pierre Bergé, Arpad Rimmel, Joanna Tomasik

Publication date 22 June 2023

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/21m1398203

zbMATH Keywords

parameterized complexitycounting problemsminimum \((S,T)\)-cuts

Mathematics Subject Classification ID

Flows in graphs (05C21) Enumeration in graph theory (05C30) Connectivity (05C40)

Recommendations

• The minimum \(k\)-way cut of bounded size is fixed-parameter tractable
• Counting and sampling minimum (s,t)-cuts in weighted planar graphs in polynomial time
• Counting Minimum (s,t)-Cuts in Weighted Planar Graphs in Polynomial Time
• Simple and improved parameterized algorithms for multiterminal cuts
• Computing All Small Cuts in an Undirected Network

Cites work

• scientific article; zbMATH DE number 5485529 (Why is no real title available?)
• scientific article; zbMATH DE number 1979521 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 795224 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• An improved parameterized algorithm for the minimum node multiway cut problem
• Calculating bounds on reachability and connectedness in stochastic networks
• Computing Network Reliability in Time Polynomial in the Number of Cuts
• Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time
• Counting and sampling minimum cuts in genus g graphs
• Counting matchings of size \(k\) is \#W[1]-hard
• Counting problems in parameterized complexity
• Counting the number of minimum cuts in undirected multigraphs
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• Finding and counting vertex-colored subtrees
• Finding small separators in linear time via treewidth reduction
• Finding, minimizing, and counting weighted subgraphs
• Fine-grained dichotomies for the Tutte plane and Boolean \#CSP
• Fixed-parameter tractability of counting small minimum \((S,T)\)-cuts
• Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
• Fixed-parameter tractability of multicut parameterized by the size of the cutset
• Integrating and sampling cuts in bounded treewidth graphs
• Maximal Flow Through a Network
• Minimum bisection is fixed parameter tractable
• Parameterized graph separation problems
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The Parameterized Complexity of Counting Problems
• The complexity of computing the permanent

Cited in

(2)

• Small \(k\)-pyramids and the complexity of determining \(k\)
• Counting Minimum (s,t)-Cuts in Weighted Planar Graphs in Polynomial Time

This page was built for publication: On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts

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