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

DOI10.1137/21M1398203zbMATH Open1517.05077OpenAlexW4380487890MaRDI QIDQ6157971FDOQ6157971

Arpad Rimmel, Pierre Bergé, Joanna Tomasik, Author name not available (Why is that?)

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

• Maximal Flow Through a Network
• The complexity of computing the permanent
• Finding and counting vertex-colored subtrees
• Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• Fixed-parameter tractability of multicut parameterized by the size of the cutset
• Title not available (Why is that?)
• Parameterized graph separation problems
• An improved parameterized algorithm for the minimum node multiway cut problem
• Finding small separators in linear time via treewidth reduction
• Calculating bounds on reachability and connectedness in stochastic networks
• Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Parameterized Complexity of Counting Problems
• Title not available (Why is that?)
• Counting the number of minimum cuts in undirected multigraphs
• Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time
• Minimum bisection is fixed parameter tractable
• Computing Network Reliability in Time Polynomial in the Number of Cuts
• Directed multicut is W[1]-hard, even for four terminal pairs
• Block interpolation: a framework for tight exponential-time counting complexity
• Title not available (Why is that?)
• Finding, minimizing, and counting weighted subgraphs
• Counting Matchings of Size k Is $\sharp$ W[1]-Hard
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• Fine-grained dichotomies for the Tutte plane and Boolean \#CSP
• Fixed-parameter tractability of counting small minimum \((S,T)\)-cuts
• Integrating and Sampling Cuts in Bounded Treewidth Graphs
• Counting and sampling minimum cuts in genus g graphs

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)