On the public citation graph

Multicut Is FPT

0 signed · 39 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1002/net.20081openalex-snapshot
Fixed‐parameter tractability and data reduction for multicut in trees
inferredcites →https://doi.org/10.1007/bf02523685openalex-snapshot
Primal-dual approximation algorithms for integral flow and multicut in trees
inferredcites →https://doi.org/10.1007/s00037-006-0210-9openalex-snapshot
ON THE HARDNESS OF APPROXIMATING MULTICUT AND SPARSEST-CUT
inferredcites →https://doi.org/10.1007/s00453-007-9130-6openalex-snapshot
An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem
inferredcites →https://doi.org/10.1016/j.ejor.2003.10.037openalex-snapshot
Minimal multicut and maximal integer multiflow: A survey
inferredcites →https://doi.org/10.1016/j.ipl.2007.03.005openalex-snapshot
A logical approach to multicut problems
inferredcites →https://doi.org/10.1016/j.jcss.2012.03.001openalex-snapshot
Multicut in trees viewed through the eyes of vertex cover
inferredcites →https://doi.org/10.1016/j.tcs.2005.10.007openalex-snapshot
Parameterized graph separation problems
inferredcites →https://doi.org/10.1016/s0166-218x(99)00187-0openalex-snapshot
A polyhedral approach to an integer multicommodity flow problem
inferredcites →https://doi.org/10.1112/jlms/s1-35.1.85openalex-snapshot
Intersection Theorems for Systems of Sets
inferredcites →https://doi.org/10.1137/110855247openalex-snapshot
Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
inferredcites →https://doi.org/10.1137/12086217xopenalex-snapshot
Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset
inferredcites →https://doi.org/10.1137/120904202openalex-snapshot
Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs
inferredcites →https://doi.org/10.1137/s0097539792225297openalex-snapshot
The Complexity of Multiterminal Cuts
inferredcites →https://doi.org/10.1137/s0097539793243016openalex-snapshot
Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
inferredcites →https://doi.org/10.1145/1411509.1411511openalex-snapshot
A fixed-parameter algorithm for the directed feedback vertex set problem
inferredcites →https://doi.org/10.1145/2462896.2462899openalex-snapshot
On multiway cut parameterized above lower bounds
inferredcites →https://doi.org/10.1145/2500119openalex-snapshot
Finding small separators in linear time via treewidth reduction

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/978-3-030-60440-0_16openalex-snapshot
Feedback Edge Sets in Temporal Graphs
inferred← citeshttps://doi.org/10.1007/978-3-031-15914-5_19openalex-snapshot
Parameterized Complexity of Weighted Multicut in Trees
inferred← citeshttps://doi.org/10.1007/s00453-023-01196-yopenalex-snapshot
Domination and Cut Problems on Chordal Graphs with Bounded Leafage
inferred← citeshttps://doi.org/10.1016/j.cosrev.2023.100556openalex-snapshot
A survey of parameterized algorithms and the complexity of edge modification
inferred← citeshttps://doi.org/10.1016/j.cosrev.2025.100869openalex-snapshot
Applications of flow-augmentation
inferred← citeshttps://doi.org/10.1016/j.dam.2025.01.012openalex-snapshot
The complexity of cluster vertex splitting and company
inferred← citeshttps://doi.org/10.1016/j.entcs.2019.08.021openalex-snapshot
Adapting The Directed Grid Theorem into an FPT Algorithm
inferred← citeshttps://doi.org/10.1016/j.jcss.2024.103597openalex-snapshot
Single-exponential FPT algorithms for enumerating secluded F -free subgraphs and deleting to scattered graph classes
inferred← citeshttps://doi.org/10.1016/j.jcss.2025.103730openalex-snapshot
Search-space reduction via essential vertices revisited: Vertex multicut and cograph deletion
inferred← citeshttps://doi.org/10.1016/j.jcss.2026.103820openalex-snapshot
On the parameterized complexity of s-club cluster edge deletion
inferred← citeshttps://doi.org/10.1016/j.jctb.2025.11.002openalex-snapshot
When recursion is better than iteration: A linear-time algorithm for directed acyclicity with few error vertices
inferred← citeshttps://doi.org/10.1016/j.tcs.2021.09.040openalex-snapshot
Colourful components in k-caterpillars and planar graphs
inferred← citeshttps://doi.org/10.1016/j.tcs.2023.114174openalex-snapshot
Parameterized complexity of multicut in weighted trees
inferred← citeshttps://doi.org/10.1137/1.9781611977073.82openalex-snapshot
Subexponential Parameterized Algorithms for Cut and Cycle Hitting Problems on H -Minor-Free Graphs
inferred← citeshttps://doi.org/10.1137/1.9781611977554.ch123openalex-snapshot
Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
inferred← citeshttps://doi.org/10.1137/21m1452664openalex-snapshot
Adapting the Directed Grid Theorem into an FPT Algorithm
inferred← citeshttps://doi.org/10.1137/22m153118xopenalex-snapshot
On Weighted Graph Separation Problems and Flow Augmentation
inferred← citeshttps://doi.org/10.1145/3626526openalex-snapshot
Cluster Editing Parameterized above Modification-disjoint P 3 -packings
inferred← citeshttps://doi.org/10.1145/3641105openalex-snapshot
Flow-augmentation II: Undirected Graphs
inferred← citeshttps://doi.org/10.1145/3696451openalex-snapshot
Compound Logics for Modification Problems
inferred← citeshttps://doi.org/10.1145/3733107openalex-snapshot
Almost Consistent Systems of Linear Equations
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.