Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs

DOI10.1145/3450704MaRDI QIDQ5056419zbMATH OpenOpenAlexWikidataFDO

Authors Vincent Cohen-Addad, Éric Colin de Verdière, Dániel Marx, Arnaud de Mesmay

Publication date 8 December 2022

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3450704

zbMATH Keywords

cut graphexponential time hypothesismulticutmultiway cutsurfaceW[1-hardness]

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Minimum Cuts in Surface Graphs
• Global minimum cuts in surface embedded graphs
• Minimum cuts and shortest homologous cycles

Cited in

(6)

• Almost tight lower bounds for hard cutting problems in embedded graphs
• Multicut problems in embedded graphs: the dependency of complexity on the demand pattern
• Can you link up with treewidth?
• Multicut problems in embedded graphs: the dependency of complexity on the demand pattern
• Multicut problems in almost-planar graphs: the dependency of complexity on the demand pattern
• Can you link up with treewidth?

This page was built for publication: Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs

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