Copertina

Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Hatzel, Meike, Jaffke, Lars, Lima, Paloma T., Masařík, Tomáš, Pilipczuk, Marcin, Sharma, Roohani, Sorge, Manuel
Natura:	Preprint
Pubblicazione:	2022
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

On weighted graph separation problems and flow-augmentation
di: Kim, Eun Jung, et al.
Pubblicazione: (2022)

A tight quasi-polynomial bound for Global Label Min-Cut
di: Jaffke, Lars, et al.
Pubblicazione: (2022)

Optimal Discretization is Fixed-parameter Tractable
di: Kratsch, Stefan, et al.
Pubblicazione: (2020)

Constant congestion brambles in directed graphs
di: Masařík, Tomáš, et al.
Pubblicazione: (2021)

On graphs coverable by chubby shortest paths
di: Hatzel, Meike, et al.
Pubblicazione: (2025)

Erdős-Pósa property of tripods in directed graphs
di: Briański, Marcin, et al.
Pubblicazione: (2024)

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
di: Kim, Eun Jung, et al.
Pubblicazione: (2022)

Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
di: Gartland, Peter, et al.
Pubblicazione: (2023)

Tight bound on treedepth in terms of pathwidth and longest path
di: Hatzel, Meike, et al.
Pubblicazione: (2023)

Dualities in graphs and digraphs
di: Hatzel, Meike
Pubblicazione: (2024)

QPTAS for MWIS and finding large sparse induced subgraphs in graphs with few independent long holes
di: Bonnet, Édouard, et al.
Pubblicazione: (2026)

Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of $P_4$
di: Cook, Linda, et al.
Pubblicazione: (2022)

Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory
di: Baste, Julien, et al.
Pubblicazione: (2019)

Connectivity augmentation is fixed-parameter tractable
di: Korhonen, Tuukka, et al.
Pubblicazione: (2026)

Half-integral Erdős-Pósa property for non-null $S$-$T$ paths
di: Chekan, Vera, et al.
Pubblicazione: (2024)

Computing $\vec{\mathcal{S}}$-DAGs and Parity Games
di: Hatzel, Meike, et al.
Pubblicazione: (2024)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
di: S., Karthik C., et al.
Pubblicazione: (2023)

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
di: Bergougnoux, Benjamin, et al.
Pubblicazione: (2025)

A Parameterized Complexity Analysis of Bounded Height Depth-first Search Trees
di: Jaffke, Lars, et al.
Pubblicazione: (2025)

Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument
di: Majewski, Konrad, et al.
Pubblicazione: (2022)

Fixed-parameter tractability and hardness for Steiner rooted and locally connected orientations
di: Bérczi, Kristóf, et al.
Pubblicazione: (2025)

Fixed-parameter tractability of canonical polyadic decomposition over finite fields
di: Yang, Jason
Pubblicazione: (2024)

Pattern-Sparse Tree Decompositions in $H$-Minor-Free Graphs
di: Marx, Dániel, et al.
Pubblicazione: (2026)

Counterexample to Babai's lonely colour conjecture
di: Davies, James, et al.
Pubblicazione: (2024)

Directed treewidth is closed under taking butterfly minors
di: Kim, Gunwoo, et al.
Pubblicazione: (2025)

Quasi-isometries between graphs with variable edge lengths
di: Davies, James, et al.
Pubblicazione: (2025)

Fixed-parameter tractable inference for discrete probabilistic programs, via string diagram algebraisation
di: Peterseim, Benedikt, et al.
Pubblicazione: (2026)

Critical site percolation and cutsets
di: Li, Zhongyang
Pubblicazione: (2024)

On graphs with a simple structure of maximal cliques
di: Gollin, J. Pascal, et al.
Pubblicazione: (2025)

Braces of Perfect Matching Width 2
di: Giannopoulou, Archontia C., et al.
Pubblicazione: (2019)

A polynomial bound on the number of minimal separators and potential maximal cliques in $P_6$-free graphs of bounded clique number
di: Pilipczuk, Marcin, et al.
Pubblicazione: (2023)

A note on finding long directed cycles above the minimum degree bound in 2-connected digraphs
di: Czyżewska, Jadwiga, et al.
Pubblicazione: (2025)

Bounding $\varepsilon$-scatter dimension via metric sparsity
di: Bourneuf, Romain, et al.
Pubblicazione: (2024)

Computing diverse pair of solutions for tractable SAT
di: Gima, Tatsuya, et al.
Pubblicazione: (2024)

Faster diameter computation in graphs of bounded Euler genus
di: Kluk, Kacper, et al.
Pubblicazione: (2025)

Coarse Balanced Separators in Fat-Minor-Free Graphs
di: Bonnet, Édouard, et al.
Pubblicazione: (2026)

Antichain cutsets in real-ranked lattices
di: Foldes, Stephan, et al.
Pubblicazione: (2025)

Minimizing an Uncrossed Collection of Drawings
di: Hliněný, Petr, et al.
Pubblicazione: (2023)

General Strong Bound on the Uncrossed Number via a Tight Bound for the Maximum Uncrossed Subgraph Number
di: Charvy, Gaspard, et al.
Pubblicazione: (2025)

Single-conflict colorings of degenerate graphs
di: Bradshaw, Peter, et al.
Pubblicazione: (2021)