Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond
type: Item
instance of: scholarly article
title: Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond
arXiv ID: 2204.10465
DOI: 10.1145/3519935.3520066
author: Amir Abboud
author: Karl Bringmann
author: Seri Khoury
author: Or Zamir
published in: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
publication date: 2023-12-08T00:00:00Z
full work available at URL: https://arxiv.org/abs/2204.10465
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7774432
zbMATH Keywords: 4-cycle finding
zbMATH Keywords: fine-grained complexity
zbMATH Keywords: hardness of approximation
zbMATH Keywords: shortest paths
zbMATH Keywords: triangle finding
MaRDI profile type: MaRDI publication profile
Recommended article: On the cycle augmentation problem: hardness and approximation algorithms
Recommended article: On the Cycle Augmentation Problem: hardness and approximation algorithms
Recommended article: Disjoint Cycles: Integrality Gap, Hardness, and Approximation
Recommended article: Q4638059
Recommended article: Parameterized Approximability of the Disjoint Cycle Problem
Recommended article: Approximation algorithms and hardness results for cycle packing problems
Recommended article: Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions
Recommended article: Q5091249
Recommended article: Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
Recommended article: Hardness of approximating the shortest vector problem in lattices
description: scientific article; zbMATH DE number 7774432