Cover Image

Path Contraction Faster than $2^n$

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Agrawal, Akanksha, Fomin, Fedor V., Lokshtanov, Daniel, Saurabh, Saket, Tale, Prafullkumar
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Robust Contraction Decomposition for Minor-Free Graphs and its Applications
by: Bandyapadhyay, Sayan, et al.
Published: (2024)

Parameterized Saga of First-Fit and Last-Fit Coloring
by: Agrawal, Akanksha, et al.
Published: (2024)

A Finer View of the Parameterized Landscape of Labeled Graph Contractions
by: Mathur, Yashaswini, et al.
Published: (2025)

The Parameterized Complexity Landscape of Two-Sets Cut-Uncut
by: Bentert, Matthias, et al.
Published: (2024)

Stability in Graphs with Matroid Constraints
by: Fomin, Fedor V., et al.
Published: (2024)

Algorithms for Euclidean Distance Matrix Completion: Exploiting Proximity to Triviality
by: Fomin, Fedor V., et al.
Published: (2026)

A Quadratic Vertex Kernel and a Subexponential Algorithm for Subset-FAST
by: Jana, Satyabrata, et al.
Published: (2025)

Cuts in Graphs with Matroid Constraints
by: Banik, Aritra, et al.
Published: (2024)

When Distances Lie: Euclidean Embeddings in the Presence of Outliers and Distance Violations
by: Bentert, Matthias, et al.
Published: (2025)

Parameterized complexity of isometric path partition: treewidth and diameter
by: Chakraborty, Dibyayan, et al.
Published: (2025)

Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover
by: Chakraborty, Dipayan, et al.
Published: (2024)

Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
by: Fomin, Fedor V., et al.
Published: (2024)

Algorithms and Hardness for Geodetic Set on Tree-like Digraphs
by: Foucaud, Florent, et al.
Published: (2026)

Polynomial Kernels for Spanning Tree with Diversity Requirements
by: Golovach, Petr A., et al.
Published: (2026)

When does FTP become FPT?
by: Bentert, Matthias, et al.
Published: (2025)

Edge Clique Partition and Cover Beyond Independence
by: Fomin, Fedor V., et al.
Published: (2025)

Fault-Tolerant Matroid Bases
by: Bentert, Matthias, et al.
Published: (2025)

H-Planarity and Parametric Extensions: when Modulators Act Globally
by: Fomin, Fedor V., et al.
Published: (2025)

Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
by: Foucaud, Florent, et al.
Published: (2023)

Metric Dimension and Geodetic Set Parameterized by Vertex Cover
by: Foucaud, Florent, et al.
Published: (2024)

Induced Minors and Coarse Tree Decompositions
by: Chudnovsky, Maria, et al.
Published: (2026)

A Faster Deterministic Algorithm for Mader's $\mathcal{S}$-Path Packing
by: Iwata, Satoru, et al.
Published: (2024)

Tree Independence Number IV. Even-hole-free Graphs
by: Chudnovsky, Maria, et al.
Published: (2024)

Node-Weighted Triangles: Faster and Simpler
by: Akmal, Shyan, et al.
Published: (2026)

Efficient Online Sensitivity Analysis For The Injective Bottleneck Path Problem
by: Kaymakov, Kirill V., et al.
Published: (2024)

The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 2
by: Byrka, Jarosław, et al.
Published: (2024)

Parameterized Complexity of Path Set Packing
by: Aravind, N. R., et al.
Published: (2022)

Faster Mixing of the Jerrum-Sinclair Chain
by: Chen, Xiaoyu, et al.
Published: (2025)

Tight Paths and Tight Pairs in Weighted Directed Graphs
by: Balcázar, José Luis
Published: (2025)

Detecting Disjoint Shortest Paths in Linear Time and More
by: Akmal, Shyan, et al.
Published: (2024)

Minsum Problem for Discrete and Weighted Set Flow on Dynamic Path Network
by: Manna, Bubai, et al.
Published: (2024)

On the Polynomial Kernelizations of Finding a Shortest Path with Positive Disjunctive Constraints
by: Bandopadhyay, Susobhan, et al.
Published: (2023)

An $Ω(n \log n)$ Randomized Lower Bound for Cutting a Cake into Proportionally Fair Pieces
by: Arndt, Stephen, et al.
Published: (2026)

Fixed-Parameter Tractability of Hedge Cut
by: Fomin, Fedor V., et al.
Published: (2024)

Deterministic approximate counting of colorings with fewer than $2Δ$ colors via absence of zeros
by: Bencs, Ferenc, et al.
Published: (2024)

Separating Feasibility and Movement in Solution Discovery: The Case of Path Discovery
by: von Bergen, Hanno, et al.
Published: (2026)

Space-Efficient Hierholzer: Eulerian Cycles in $\mathrm{O}(m)$ Time and $\mathrm{O}(n)$ Space
by: Alaoui, Ziad Ismaili, et al.
Published: (2025)

An Algebraic Approach to the Longest Path Problem
by: Khazali, Omar Al -
Published: (2023)

Revisiting Path Contraction and Cycle Contraction
by: Krithika, R., et al.
Published: (2024)

On the Enumeration of all Unique Paths of Recombining Trinomial Trees
by: Torres, Ethan, et al.
Published: (2025)