Cover Image

Parameterized complexity of isometric path partition: treewidth and diameter

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chakraborty, Dibyayan, Defrain, Oscar, Foucaud, Florent, Mari, Mathieu, Tale, Prafullkumar
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Discrete Mathematics Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

Strong isometric path complexity of graphs: Asymptotic minors, restricted holes, and graph operations
by: Chakraborty, Dibyayan, et al.
Published: (2025)

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

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

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

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

Translating between the representations of an acyclic convex geometry of bounded degree
by: Defrain, Oscar, et al.
Published: (2025)

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

Hypergraph dualization with FPT-delay parameterized by the degeneracy and dimension
by: Bartier, Valentin, et al.
Published: (2023)

Enumerating minimal solution sets for metric graph problems
by: Bergougnoux, Benjamin, et al.
Published: (2023)

Polynomial-time algorithms for PATH COVER and PATH PARTITION on trees and graphs of bounded treewidth
by: Foucaud, Florent, et al.
Published: (2025)

Enumerating minimal dominating sets and variants in chordal bipartite graphs
by: Castelo, Emanuel, et al.
Published: (2025)

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

On the enumeration of signatures of XOR-CNF's
by: Creignou, Nadia, et al.
Published: (2024)

Generating minimal redundant and maximal irredundant sets in incidence graphs
by: Castelo, Emanuel, et al.
Published: (2026)

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

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

Polynomial-delay generation of functional digraphs up to isomorphism
by: Defrain, Oscar, et al.
Published: (2023)

Structural Parameterization of Locating-Dominating Set and Test Cover
by: Chakraborty, Dipayan, et al.
Published: (2024)

Path Contraction Faster than $2^n$
by: Agrawal, Akanksha, et al.
Published: (2025)

Distance-based (and path-based) covering problems for graphs of given cyclomatic number
by: Chakraborty, Dibyayan, et al.
Published: (2025)

Isomorphism Testing Parameterized by Genus and Beyond
by: Neuen, Daniel
Published: (2021)

Parameterized Complexity of Temporal Connected Components: Treewidth and k-Path Graphs
by: Deligkas, Argyrios, et al.
Published: (2025)

Graph parameters that are coarsely equivalent to path-length
by: Dragan, Feodor F., et al.
Published: (2025)

Probabilistic estimates of the diameters of the Rubik's Cube groups
by: Hirata, So
Published: (2024)

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

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

On the time complexity of finding a well-spread perfect matching in bridgeless cubic graphs
by: Ghanbari, Babak, et al.
Published: (2025)

Complexity of polytope diameters via perfect matchings
by: Nöbel, Christian, et al.
Published: (2024)

(Independent) Roman Domination Parameterized by Distance to Cluster
by: Ashok, Pradeesha, et al.
Published: (2024)

Vertex-ordering and arc-partitioning problems
by: Borsik, Nóra A., et al.
Published: (2025)

On the Parameterized Complexity of Grundy Domination and Zero Forcing Problems
by: Scheffler, Robert
Published: (2025)

Parameterized Complexity of (d,r)-Domination via Modular Decomposition
by: Cordasco, Gennaro, et al.
Published: (2024)

The Parameterized Complexity of Computing the VC-Dimension
by: Foucaud, Florent, et al.
Published: (2025)

The Strong Birthday Problem Revisited
by: Tripathy, Chijul B.
Published: (2025)

Reconfiguration of List Colourings
by: Cambie, Stijn, et al.
Published: (2025)

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

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