On the public citation graph

Directed Multicut is W[1]-hard, Even for Four Terminal Pairs

0 signed · 56 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.1006/jcss.2001.1774openalex-snapshot
Which Problems Have Strongly Exponential Complexity?
inferredcites →https://doi.org/10.1007/978-1-4471-3886-0openalex-snapshot
Digraphs Theory Algorithms And Applications
inferredcites →https://doi.org/10.1007/978-3-319-21275-3_14openalex-snapshot
Lower Bounds Based on the Exponential-Time Hypothesis
inferredcites →https://doi.org/10.1007/978-3-642-25870-1_2openalex-snapshot
Important Separators and Parameterized Algorithms
inferredcites →https://doi.org/10.1007/978-3-642-30891-8openalex-snapshot
The Multivariate Algorithmic Revolution and Beyond: essays dedicated to Michael R. Fellows on the occasion of His 60th birthday
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.1007/s00453-014-9910-8openalex-snapshot
A Completeness Theory for Polynomial (Turing) Kernelization
inferredcites →https://doi.org/10.1007/s00453-016-0139-6openalex-snapshot
List H-Coloring a Graph by Removing Few Vertices
inferredcites →https://doi.org/10.1016/j.dam.2013.10.038openalex-snapshot
Digraph width measures in parameterized algorithmics
inferredcites →https://doi.org/10.1016/j.jcss.2009.04.002openalex-snapshot
Almost 2-SAT is fixed-parameter tractable
inferredcites →https://doi.org/10.1016/j.jctb.2015.09.001openalex-snapshot
Are there any good digraph width measures?
inferredcites →https://doi.org/10.1016/j.tcs.2005.10.007openalex-snapshot
Parameterized graph separation problems
inferredcites →https://doi.org/10.1093/acprof:oso/9780198566076.003.0013openalex-snapshot
PARAMETERIZED COMPLEXITY THEORY
inferredcites →https://doi.org/10.1108/ir.1999.04926fae.001openalex-snapshot
Lecture Notes in Computer Science 1205
inferredcites →https://doi.org/10.1112/jlms/s1-35.1.85openalex-snapshot
Intersection Theorems for Systems of Sets
inferredcites →https://doi.org/10.1137/1.9781611973402.128openalex-snapshot
Half-integrality, LP-branching and FPT Algorithms
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/120883931openalex-snapshot
Steiner Forest Orientation Problems
inferredcites →https://doi.org/10.1137/120904202openalex-snapshot
Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs
inferredcites →https://doi.org/10.1137/15m1032077openalex-snapshot
Designing FPT Algorithms for Cut Problems Using Randomized Contractions
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/1993636.1993698openalex-snapshot
Multicut is FPT
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
inferredcites →https://doi.org/10.1145/2566616openalex-snapshot
Faster Parameterized Algorithms Using Linear Programming
inferredcites →https://doi.org/10.1145/2591796.2591852openalex-snapshot
Minimum bisection is fixed parameter tractable
inferredcites →https://doi.org/10.1145/2594439openalex-snapshot
Clique Cover and Graph Separation
inferredcites →https://doi.org/10.1201/b17645-11openalex-snapshot
Width-Measures for Directed Graphs and Algorithmic Applications
inferredcites →https://doi.org/10.4086/toc.2010.v006a005openalex-snapshot
inferredcites →https://doi.org/10.4230/lipics.stacs.2015.34openalex-snapshot
Graph Searching Games and Width Measures for Directed Graphs

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-00256-5_6openalex-snapshot
On Directed Feedback Vertex Set Parameterized by Treewidth
inferred← citeshttps://doi.org/10.1007/s00224-020-09977-6openalex-snapshot
On the Fixed-Parameter Tractability of the Maximum Connectivity Improvement Problem
inferred← citeshttps://doi.org/10.1007/s00453-019-00580-xopenalex-snapshot
A Tight Lower Bound for Planar Steiner Orientation
inferred← citeshttps://doi.org/10.1007/s00454-025-00782-xopenalex-snapshot
Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
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.100833openalex-snapshot
Techniques in parameterized approximation
inferred← citeshttps://doi.org/10.1016/j.cosrev.2025.100869openalex-snapshot
Applications of flow-augmentation
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.2025.103730openalex-snapshot
Search-space reduction via essential vertices revisited: Vertex multicut and cograph deletion
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.9781611973402.129openalex-snapshot
Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
inferred← citeshttps://doi.org/10.1137/1.9781611975031.177openalex-snapshot
Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms
inferred← citeshttps://doi.org/10.1137/1.9781611976465.11openalex-snapshot
Solving hard cut problems via flow-augmentation
inferred← citeshttps://doi.org/10.1137/1.9781611976465.15openalex-snapshot
Strong Connectivity Augmentation is FPT
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/18m122371xopenalex-snapshot
Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
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/3447584openalex-snapshot
Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
inferred← citeshttps://doi.org/10.1145/3519935.3520018openalex-snapshot
Directed flow-augmentation
inferred← citeshttps://doi.org/10.1145/3706103openalex-snapshot
Flow-augmentation I: Directed graphs
inferred← citeshttps://doi.org/10.3390/a13060146openalex-snapshot
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
inferred← citeshttps://doi.org/10.34768/amcs-2022-0004openalex-snapshot
Exact and approximation algorithms for sensor placement against DDoS attacks
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2020.104openalex-snapshot
Parameterized Inapproximability for Steiner Orientation by Gap Amplification
inferred← citeshttps://doi.org/10.4230/lipics.ipec.2019.8openalex-snapshot
FPT Inapproximability of Directed Cut and Connectivity Problems
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.