Cover Image

Polynomial-time algorithms for PATH COVER and PATH PARTITION on trees and graphs of bounded treewidth

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Foucaud, Florent, Majumder, Atrayee, Mömke, Tobias, Roshany-Tabrizi, Aida
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

Approximating Maximum Edge 2-Coloring by Normalizing Graphs
by: Mömke, Tobias, et al.
Published: (2024)

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

Isometric path complexity of graphs
by: Chakraborty, Dibyayan, et al.
Published: (2022)

On graphs coverable by k shortest paths
by: Dumas, Maël, et al.
Published: (2022)

Algorithms and complexity for path covers of temporal DAGs: when is Dilworth dynamic?
by: Chakraborty, Dibyayan, et al.
Published: (2024)

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

Feedback Vertex Set for pseudo-disk graphs in subexponential FPT time
by: Berthe, Gaétan, et al.
Published: (2024)

Algorithms and complexity for monitoring edge-geodetic sets in graphs
by: Foucaud, Florent, et al.
Published: (2024)

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

Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions
by: Alecu, Bogdan, et al.
Published: (2024)

Generation of weighted trees, block trees and block graphs
by: Ekim, Tınaz, et al.
Published: (2024)

Generating pivot Gray codes for spanning trees of complete graphs in constant amortized time
by: Liu, Bowie, et al.
Published: (2025)

Packing $K_r$s in bounded degree graphs
by: McKay, Michael, et al.
Published: (2022)

Fast approximation algorithms for the 1-median problem on real-world large graphs
by: Ueta, Keisuke, et al.
Published: (2025)

A column generation algorithm for finding co-3-plexes in chordal graphs
by: Dupont-Bouillard, Alexandre
Published: (2026)

Circle graphs can be recognized in linear time
by: Paul, Christophe, 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)

Near-linear time subhypergraph counting in bounded degeneracy hypergraphs
by: Paul-Pena, Daniel, et al.
Published: (2025)

Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs
by: Bencs, Ferenc, et al.
Published: (2025)

Clique-free t-matchings in degree-bounded graphs
by: Paluch, Katarzyna, et al.
Published: (2024)

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

Hypergraph Connectivity Augmentation in Strongly Polynomial Time
by: Bérczi, Kristóf, et al.
Published: (2024)

Asymptotically faster algorithms for recognizing $(k,\ell)$-sparse graphs
by: Deák, Bence, et al.
Published: (2026)

Quasi-linear distance query reconstruction for graphs of bounded treelength
by: Bastide, Paul, et al.
Published: (2024)

On the complexity of finding a spanning even tree in a graph
by: Hanaka, Tesshu, et al.
Published: (2024)

Prime Factorization of the Kirchhoff Polynomial: Compact Enumeration of Arborescences
by: Mihalák, Matúš, et al.
Published: (2015)

Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets
by: Bonamy, Marthe, et al.
Published: (2020)

Output-Sensitive Enumeration of Potential Maximal Cliques in Polynomial Space
by: Brosse, Caroline, et al.
Published: (2024)

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

Continuous Petri Nets for Fast Yield Computation: Polynomial-Time and MILP Approaches
by: Jordon, Addie, et al.
Published: (2025)

Bounded indegree $k$-forests problem and a faster algorithm for directed graph augmentation
by: Arkhipov, Pavel, et al.
Published: (2024)

A survey of Chernoff and Hoeffding bounds
by: Gerbessiotis, Alexandros V.
Published: (2025)

Terminal Steiner tree problem : Complexity and Algorithms
by: S, Jyothish, et al.
Published: (2026)

Approximation algorithms for non-sequential star packing problems
by: Hu, Mengyuan, et al.
Published: (2024)

An approximation algorithm for Maximum DiCut vs. Cut
by: Nakajima, Tamio-Vesa, et al.
Published: (2024)

Rumors on evolving graphs through stationary times
by: Bonasorte, Vicenzo
Published: (2025)

Fanciful Figurines flip Free Flood-It -- Polynomial-Time Miniature Painting on Co-gem-free Graphs
by: Rosenke, Christian, et al.
Published: (2026)

An efficient algorithm for $\mathcal{F}$-subgraph-free Edge Deletion on graphs having a product structure
by: An, Shinwoo, et al.
Published: (2025)

Circular-arc graphs and the Helly property
by: Derbisz, Jan, et al.
Published: (2024)