Revisiting path contraction and cycle contraction

DOI10.1016/J.JCSS.2025.103724MaRDI QIDQ6885359zbMATH OpenFDO

Authors R. Krithika, V. K. Kutty Malu, Prafullkumar Tale

Publication date 11 December 2025

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JCSS.2025.103724

zbMATH Keywords

chordal graphscycle contractionparameterized complexitypath contractionplanar graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• An improved linear kernel for the cycle contraction problem
• Connecting Terminals and 2-Disjoint Connected Subgraphs
• Consequences of Faster Alignment of Sequences
• Contractibility and NP-completeness
• Contracting chordal graphs and bipartite graphs to paths and trees
• Contracting graphs to paths and trees
• Contracting to a longest path in H-free graphs
• Contractions of Planar Graphs in Polynomial Time
• Cyclicity of graphs
• Edge-contraction problems
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• Finding orthogonal vectors in discrete structures
• Graph minors. XIII: The disjoint paths problem
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• scientific article; zbMATH DE number 2188410 (Why is no real title available?)
• Improved kernel results for some FPT problems based on simple observations
• On the parameterized complexity of grid contraction
• Parameterized algorithms
• Parameterized complexity of three edge contraction problems with degree constraints
• Partitioning graphs into connected parts
• Path contraction faster than 2ⁿ
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Tight hardness results for LCS and other sequence similarity measures
• Treewidth computation and extremal combinatorics

This page was built for publication: Revisiting path contraction and cycle contraction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6885359)