Can local optimality be used for efficient data reduction?

DOI10.1007/978-3-030-75242-2_25OpenAlexW3158282794MaRDI QIDQ2692734

Christian Komusiewicz, Nils Morawietz

Publication date: 22 March 2023

Full work available at URL: https://doi.org/10.1007/978-3-030-75242-2_25

zbMATH Keywords

local searchindependent setNP-hardnesslongest pathmax-cut

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Uses Software

• NuMVC

Cites Work

• The parameterized complexity of local search for TSP, more refined
• The disjoint paths problem in quadratic time
• Local search: is brute-force avoidable?
• A simplified NP-complete satisfiability problem
• Searching the \(k\)-change neighborhood for TSP is W[1-hard]
• How easy is local search?
• Independent-set reconfiguration thresholds of hereditary graph classes
• Distributed reconfiguration of maximal independent sets
• Extension of Vertex Cover and Independent Set in some classes of graphs
• Extension and its price for the Connected Vertex Cover problem
• The Planar Hamiltonian Circuit Problem is NP-Complete
• The Complexity of Independent Set Reconfiguration on Bipartite Graphs
• NuMVC: An Efficient Local Search Algorithm for Minimum Vertex Cover
• Independent set reconfiguration parameterized by modular-width