Cover Image

Finding One Local Optimum Is Easy -- but What About Two?

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kobayashi, Yasuaki, Kurita, Kazuhiro, Yamaguchi, Yutaro
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The Complexity of Maximal Common Subsequence Enumeration
by: Buzzega, Giovanni, et al.
Published: (2025)

On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs
by: Kurita, Kazuhiro, et al.
Published: (2025)

Finding a Minimum Spanning Tree with a Small Non-Terminal Set
by: Hanaka, Tesshu, et al.
Published: (2023)

Polynomial-Delay Enumeration of Large Maximal Common Independent Sets in Two Matroids and Beyond
by: Kobayashi, Yasuaki, et al.
Published: (2023)

Recognizing 2-Layer and Outer $k$-Planar Graphs
by: Kobayashi, Yasuaki, et al.
Published: (2024)

Efficient Constant-Factor Approximate Enumeration of Minimal Subsets for Monotone Properties with Weight Constraints
by: Kobayashi, Yasuaki, et al.
Published: (2020)

Finding Diverse Strings and Longest Common Subsequences in a Graph
by: Shida, Yuto, et al.
Published: (2024)

Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial
by: Curticapean, Radu, et al.
Published: (2025)

Broadcasting under Structural Restrictions
by: Egami, Yudai, et al.
Published: (2025)

Computational Complexity of Swish
by: Horiyama, Takashi, et al.
Published: (2026)

Fantastic Flips and Where to Find Them: A General Framework for Parameterized Local Search on Partitioning Problems
by: Grüttemeier, Niels, et al.
Published: (2025)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

The Complexity of Finding and Counting Subtournaments
by: Döring, Simon, et al.
Published: (2025)

Optimal Parallel Basis Finding in Graphic and Related Matroids
by: Khanna, Sanjeev, et al.
Published: (2025)

On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets
by: Bilò, Davide, et al.
Published: (2024)

Finding Maximum Common Contractions Between Phylogenetic Networks
by: Marchand, Bertrand, et al.
Published: (2024)

The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
by: Bentert, Matthias, et al.
Published: (2024)

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
by: Shih, Yu-Sheng, et al.
Published: (2026)

Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure
by: de Berg, Mark, et al.
Published: (2025)

Parameterized Complexity of Finding a Maximum Common Vertex Subgraph Without Isolated Vertices
by: Dey, Palash, et al.
Published: (2026)

Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints
by: Kobayashi, Yasuaki, et al.
Published: (2023)

Clustering with Locally Bounded Ignorance
by: Garvardt, Jaroslav, et al.
Published: (2026)

Local Enumeration: The Not-All-Equal Case
by: Gurumukhani, Mohit, et al.
Published: (2025)

Sumplete is Hard, Even with Two Different Numbers
by: Ruangwises, Suthee
Published: (2023)

Non-Boolean OMv: One More Reason to Believe Lower Bounds for Dynamic Problems
by: Hu, Bingbing, et al.
Published: (2024)

Complexity of Local Search for Euclidean Clustering Problems
by: Manthey, Bodo, et al.
Published: (2023)

The Query Complexity of Local Search and Brouwer in Rounds
by: Brânzei, Simina, et al.
Published: (2020)

Structural Parameterizations for Two Bounded Degree Problems Revisited
by: Lampis, Michael, et al.
Published: (2023)

List Locally Surjective Homomorphisms in Hereditary Graph Classes
by: Dvořák, Pavel, et al.
Published: (2022)

The Query Complexity of Local Search in Rounds on General Graphs
by: Brânzei, Simina, et al.
Published: (2026)

A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow
by: Gholizadeh, Hossein, et al.
Published: (2025)

Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut
by: Michel, Lukas, et al.
Published: (2023)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
by: Esmer, Barış Can, et al.
Published: (2022)

Scalable Neighborhood Local Search for Single-Machine Scheduling with Family Setup Times
by: Balzereit, Kaja, et al.
Published: (2024)

A Linear-Time Algorithm for Finding an Odd Cycle Through Two Specified Vertices
by: Kano, Takumi, et al.
Published: (2026)

Computing diverse pair of solutions for tractable SAT
by: Gima, Tatsuya, et al.
Published: (2024)

Complexity of Finding and Enumerating Interconnection Trees
by: Demange, Noé, et al.
Published: (2026)

Finding Minimum Distance Preservers: A Parameterized Study
by: Simonov, Kirill, et al.
Published: (2026)

Quantum Algorithms on Edge Lists: Hiding, Shuffling, and Cycle Finding
by: Gilani, Amin Shiraz, et al.
Published: (2024)

Quantum Algorithm for Finding the Optimal Variable Ordering for Binary Decision Diagrams
by: Tani, Seiichiro
Published: (2019)