Can local optimality be used for efficient data reduction?

DOI10.1007/S00224-024-10205-8MaRDI QIDQ7021362zbMATH OpenFDO

Authors Christian Komusiewicz, Nils Morawietz

Publication date 28 February 2025

Published in Theory of Computing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00224-024-10205-8

zbMATH Keywords

independent setlocal searchlongest pathmax-cutNP-hardness

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites work

• A simplified NP-complete satisfiability problem
• Distributed reconfiguration of maximal independent sets
• Extension and its price for the connected vertex cover problem
• Extension of Vertex Cover and Independent Set in some classes of graphs
• Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP
• How easy is local search?
• Independent set reconfiguration parameterized by modular-width
• Independent-set reconfiguration thresholds of hereditary graph classes
• Local search for the minimum label spanning tree problem with bounded color classes.
• Local search: is brute-force avoidable?
• NuMVC: an efficient local search algorithm for minimum vertex cover
• Placing quantified variants of 3-SAT and \textsc{not-all-equal} 3-SAT in the polynomial hierarchy
• Searching the \(k\)-change neighborhood for TSP is W[1]-hard
• Stochastic local search. Foundations and applications.
• The complexity of independent set reconfiguration on bipartite graphs
• The disjoint paths problem in quadratic time
• The h-Index of a Graph and its Application to Dynamic Subgraph Statistics
• The parameterized complexity of local search for TSP, more refined
• The Planar Hamiltonian Circuit Problem is NP-Complete

This page was built for publication: Can local optimality be used for efficient data reduction?

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