Cover Image

Computing distances is FPT on graph associahedra and W[2]-hard on hypergraphic polytopes

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cunha, Luís Felipe I., Sau, Ignasi, Souza, Uéverton S., Valencia-Pabon, Mario
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Computational Geometry Discrete Mathematics Combinatorics 05C85, 05C10, 0C05, 90C08, 90C27 G.2.2; G.2.3; G.2.1
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Cluster deletion and clique partitioning in graphs with bounded clique number
by: Galesi, Nicola, et al.
Published: (2025)

On the parameterized complexity of computing good edge-labelings
by: de Andrade, Davi, et al.
Published: (2024)

A new density limit for unanimity in majority dynamics on random graphs
by: Kim, Jeong Han, et al.
Published: (2025)

Games on deBruijn Graphs and Cycle Means
by: Drenska, Nadejda
Published: (2026)

(Even hole, triangle)-free graphs revisited
by: Martins, Beatriz, et al.
Published: (2026)

Unavoidable induced subgraphs in graphs with complete bipartite induced minors
by: Chudnovsky, Maria, et al.
Published: (2024)

On the characterization of graphs with tree 3-spanners
by: Lin, Lan, et al.
Published: (2025)

Computing the forcing spectrum of outerplanar graphs in polynomial time
by: Gorsky, Maximilian, et al.
Published: (2024)

How Local Separators Shape Community Structure in Large Networks
by: Frenkel, Sarah, et al.
Published: (2025)

Excluding a Forest Induced Minor
by: Bonnet, Édouard, et al.
Published: (2025)

Solving the Graph Burning Problem for Large Graphs
by: Pereira, Felipe de Carvalho, et al.
Published: (2024)

Graph modification of bounded size to minor-closed classes as fast as vertex deletion
by: Morelle, Laure, et al.
Published: (2025)

Closeness of Some Graph Operations
by: Dangalchev, Chavdar
Published: (2023)

TreePIR: Efficient Private Retrieval of Merkle Proofs via Tree Colorings with Fast Indexing and Zero Storage Overhead
by: Dau, Son Hoang, et al.
Published: (2022)

Census Dual Graphs: Properties and Random Graph Models
by: Anderson, Sara, et al.
Published: (2026)

Dynamic programming on bipartite tree decompositions
by: Jaffke, Lars, et al.
Published: (2023)

An Overview of Universal Obstructions for Graph Parameters
by: Paul, Christophe, et al.
Published: (2023)

Optimal List Recoloring of Subcubic Graphs and Complete Multipartite Graphs
by: De Meyer, Lucas
Published: (2025)

On the Boxicity of Line Graphs and of Their Complements
by: Caoduro, Marco, et al.
Published: (2025)

A counterexample to the conjecture on Biclique Partition number of Split Graphs and related problems
by: Babu, Anand, et al.
Published: (2026)

Simultaneous recovery of a sparse topology and the admittance of an electrical network
by: Samperio, Álvaro
Published: (2023)

Forbidden paths and cycles in the undirected underlying graph of a 2-quasi best match graph
by: Korchmaros, Annachiara
Published: (2024)

Dynamic Traffic Assignment for Public Transport with Vehicle Capacities
by: Patzner, Julian, et al.
Published: (2024)

Parameterizing the quantification of CMSO: model checking on minor-closed graph classes
by: Sau, Ignasi, et al.
Published: (2024)

Expanded-clique graphs and the domination problem
by: Dourado, Mitre C., et al.
Published: (2022)

The Leaf Function of Penrose P2 Graphs
by: Porrier, Carole, et al.
Published: (2023)

Optimal Path Partitions in Subcubic and Almost-subcubic Graphs
by: Masařík, Tomáš, et al.
Published: (2026)

Vertex identification to a forest
by: Morelle, Laure, et al.
Published: (2024)

New results on graph matching from degree preserving growth
by: Erdős, Péter L., et al.
Published: (2022)

Simple Approximations for General Spanner Problems
by: Bökler, Fritz, et al.
Published: (2025)

Exact Minimum Weight Spanners via Column Generation
by: Bökler, Fritz, et al.
Published: (2024)

Measuring Ransomware Lateral Movement Susceptibility via Privilege-Weighted Adjacency Matrix Exponentiation
by: Tyagi, Satyam, et al.
Published: (2025)

Local Equivalence Classes of Distance-Hereditary Graphs using Split Decompositions
by: Connolly, Nicholas, et al.
Published: (2026)

Efficient Preparation of Graph States using the Quotient-Augmented Strong Split Tree
by: Connolly, Nicholas, et al.
Published: (2026)

Quickly excluding an annotated planar graph
by: Gorsky, Maximilian, et al.
Published: (2026)

Faster parameterized algorithms for modification problems to minor-closed classes
by: Morelle, Laure, et al.
Published: (2022)

Log-concavity of the independence polynomials of $\mathbf{W}_{p}$ graphs
by: Hoang, Do Trong, et al.
Published: (2024)

Tree-independence number VI. Thetas and pyramids
by: Chudnovsky, Maria, et al.
Published: (2025)

Merge Trees of Periodic Filtrations
by: Edelsbrunner, Herbert, et al.
Published: (2024)

A note on graphs with purely imaginary per-spectrum
by: Singh, Ranveer, et al.
Published: (2022)