A Parameterized-Complexity Framework for Finding Local Optima

Local search is one of the most commonly employed paradigms in the design of algorithms for optimization problems. The idea underlying local search algorithms is both natural and simple: start from an initial solution $S$ to the problem and apply a series of local improvement steps until reaching a local optimum, that is, a solution which cannot be improved by any local change. The definition of local improvement steps typically involves straightforward operations such as swapping or moving a constant number of elements in the solution. There are almost always many ways these steps could be applied, and one typically speaks of the local neighborhood of a solution $S$ to subsume all possible solutions that can be obtained from $S$ by performing one round of permissible operations. A solution $S$ is called a local optimum if there is no better solution in its local neighborhood, and local search algorithms are typically tasked with finding such a local optimum via a sequence of local improvement steps.

While the local search paradigm often performs very well in practice, currently established complexity-theoretic tools exclude tractability of finding local optima for many problems of interest [1, 24]. The central complexity class in the theory of local search is $\mathrm{𝖯𝖫𝖲}$ [16] (for “polynomial local search”). Inclusion in $\mathrm{𝖯𝖫𝖲}$ essentially means that one can search the local neighborhood of any given solution in polynomial time¹¹1Formal definitions are provided in Section 2.. While inclusion in $\mathrm{𝖯𝖫𝖲}$ is a natural prerequisite for efficient local search, it does not guarantee that one can find a local optimum in polynomial time – to the contrary, it is now widely believed that $\mathrm{𝖯𝖫𝖲}$-complete problems do not admit any polynomial-time local search algorithm [24]. In this sense, establishing $\mathrm{𝖯𝖫𝖲}$-hardness for a local search problem can be seen as a counterpart to establishing NP-hardness for decision problems.

Given the above discrepancy between the performance of local search algorithms and inclusion in $\mathrm{𝖯𝖫𝖲}$, researchers have proposed a second classical formalization of local search: the standard algorithm problem [16]. There, one fixes not only the notion of local neighborhood but also the specific pivoting rule, that is, the specific procedure used to compute the next solution in the local improvement step. The underlying task is then to identify the local optimum that will be obtained by exhaustively applying the selected pivoting rule from a provided initial solution $S$. The standard algorithm problem provides a useful way of making complexity-theoretic statements about local search – several standard algorithm problems are known to be PSPACE-complete [29, 27, 30, 3, 21] – but suffers from the drawback that each such statement applies to a combination of pivoting rule and local search problem. This drawback has already been acknowledged in the seminal work of Schäffer and Yannakakis [29, Page 62, 1st paragraph]: while formal lower bounds made for the standard algorithm problem only hold for specific pivoting rules (such as, e.g., moving to the first discovered improvement in the local neighborhood), it is more desirable to exclude efficient local search for any pivoting rule and this is also what can be inferred from most existing lower bound constructions [16, 27, 30, 3, 21].

Crucially, regardless of whether one chooses the $\mathrm{𝖯𝖫𝖲}$ or standard algorithm formulation, most local search problems remain computationally intractable. In this article, we introduce a novel perspective which allows us to establish not only stronger lower bounds, but also tractability for local search problems. We do so by developing a theory of parameterized local search which is inspired by and connected to the well-established parameterized complexity paradigm [5, 4]. What distinguishes our work from prior studies that examined parameterized complexity of local search [22, 31, 20, 14, 12, 17, 13] is that our results apply to the local search task as a whole and not only to a single improving step (see the discussion of related work at the end of this section). In fact, our framework targets a wide variety of common settings where computing a single improving step is polynomial-time solvable. Moreover, as a byproduct of our approach we also obtain a formulation of local search problems that lies between $\mathrm{𝖯𝖫𝖲}$ and the standard algorithm: one where negative results exclude tractability with respect to every pivoting rule (unlike the latter) while positive ones guarantee efficient local search (unlike the former).

For two integers , we denote by $[a,b]$ the set of integers between (and including) $a$ and $b$. We write $[a]$ for $[1,a]$. Given a set $S$, a subset $S^{\prime }$ of $S$, and a function $f:S\to \mathbb{Q}$, we define $f(S^{\prime }):={\sum }_{s\in S^{\prime }}f(s)$. For two sets $A$ and $B$, we denote by $A\oplus B$ their symmetric difference (i.e., $A\oplus B:=(A\setminus B)\cup (B\setminus A))$. Given a graph $G$, the open neighborhood $N_G(v)$ of a vertex $v$ is the set of all adjacent vertices of $v$ in $G$. Its closed neighborhood $N_G[v]$ is defined as $N_G(v)\cup \{v\}$. We drop the subscript when the graph $G$ is clear. For a vertex subset $S\subseteq V(G)$, we denote by $G[S]$ the subgraph of $G$ induced by $S$.

A local search problem $P$ is an optimization problem that consists of a set of instances $D_P$, a finite set of (feasible) solutions $F_P(I)$ for each instance $I\in D_P$, an objective function $f_P$ that assigns an integer value to each instance $I\in D_P$ and solution $s\in F_P(I)$, and a neighborhood $N_P(s,I)\subseteq F_P(I)$ for each solution $s\in F_P(I)$. The size of every solution $s\in F_P(I)$ is bounded by a polynomial in the size of $I$. The goal is to find a locally optimal solution for a given instance $I$; that is, a solution $s\in F_P(I)$ such that no solution $s^{\prime }\in N_P(s,I)$ yields a better objective value than $f_P(s,I)$. Formally, this means that for all $s^{\prime }\in N_P(s,I)$, we have $f_P(s,I)\le f_P(s^{\prime },I)$ if $P$ is a minimization problem, and $f_P(s,I)\ge f_P(s^{\prime },I)$ if $P$ is a maximization problem.

A common naming convention for a local search problem is of the form $Q/N$, where $Q$ is the corresponding optimization problem and $N$ is the notion of neighborhood. For example, Max Cut/Flip indicates the local search problem with instances, solutions, and objective function as defined by the optimization problem Max Cut with the addition of the neighborhood as defined by the flip operation.

A standard local search algorithm for an instance $I$ proceeds as follows. It starts with some initial solution $s\in F_P(I)$. Then it iteratively visits a neighbor with better objective value, until it reaches a local optimum. If a solution has more than one better neighbor, the algorithm has to choose one by some prespecified rule, often referred to as a pivoting rule. The standard algorithm problem is then defined as follows [16]: Given an instance $I$ and an initial solution $s$, output the local optimum that would be produced by the standard local search algorithm (with a specific pivoting rule) starting from $s$.

Next, we formalize a series of classical notions related to the complexity class $\mathrm{𝖯𝖫𝖲}$.

The “basic” reductions used for $\mathrm{𝖯𝖫𝖲}$ are defined below.

A more restrictive (and often useful) kind of reduction was defined later, by Schäffer and Yannakakis. Before defining it, we will need the following notion:

Note that tight $\mathrm{𝖯𝖫𝖲}$-reductions preserve the PSPACE-completeness of the standard algorithm problem and also the all-exp property (formalized below) [29].

We start with the concept of pivoting formulation. Given an instance $I$ of a local search problem, we define an improving sequence for $I$ to be a sequence of solutions $s_0,\mathrm{\dots },s_r$ such that for $i\in [r]$, $s_i$ is a neighbor of $s_{i-1}$ with a better objective value. An improving sequence is maximal if the last solution is locally optimal.

Observe that for a local search problem, the task is to find a local optimum, without the restriction on the techniques used to achieve it. For the pivoting problem, we restrict ourselves to using only a local search algorithm (i.e., following a path in the transition graph). We can view it as finding the right pivoting rule to arrive at a local optimum, and hence the name “pivoting”.

For example, consider the following local search problem Subset Weight Optimization Problem/$c$-Swap: We are given a graph $G=(V,E)$, a weight function $\omega :V\cup E\to \mathbb{Q}$, a certifying function $\sigma :2^{V\cup E}\to \{0,1\}$ that certifies whether a subset of vertices and edges form a solution, and an objective function $f:2^{V\cup E}\to \mathbb{Q}$ with $f(S):={\sum }_{u\in S}\omega (u)$. Two solutions are neighbors if they differ by a $c$-swap (i.e., their symmetric difference is at most $c$). The task is to find a locally maximal solution (i.e., a solution $S\subseteq V\cup E$ such that for all neighboring solution $S^{\prime }$ of $S$, we have $f(S)\ge f(S^{\prime })$). The corresponding pivoting problem is then defined as follows.

We assume that $\omega$ and $\sigma$ can be computed in time polynomial in $|V|$. Note that the graph $G$ may be directed and/or a multi-graph. Further, although it is phrased here as a maximization problem, by reversing the signs of the images of $\omega$, we can also model a minimization problem. We also assume $c$ to be a constant so that the local search variant is in $\mathrm{𝖯𝖫𝖲}$ (i.e., a polynomial time algorithm to compute a better neighbor exists).

Subset Weight Optimization Problem/$c$-Swap can be considered as a general problem that takes as special cases many well-known local search problems, such as the following.

• $\mathrm{■}$

  Weighted Independent Set/$c$-Swap (resp., Weighted Clique/$c$-Swap, Weighted Vertex Cover/$c$-Swap): In this case, the graph is vertex-weighted (i.e., the edge weights are zero); and a solution is an independent set (resp., a clique, a vertex cover).

• $\mathrm{■}$

  Traveling Salesman/$k$-opt: We have an edge-weighted graph, edge sets of spanning cycles are the solutions; and $c=2k$ (i.e., a $k$-opt step is a $(2k)$-swap).

• $\mathrm{■}$

  Max Cut/Flip with bounded maximum degree $\mathrm{\Delta }$: Here, the graph is edge-weighted (i.e., the vertex weights are zero); a solution is a set of vertices $U$ together with all edges between $U$ and $V\setminus U$; and the swap size is $c=2\cdot \mathrm{\Delta }+1$.

The next local search problem we consider is Weighted Circuit/Flip, a generalization of the classical Circuit/Flip. In this problem, we are given a Boolean circuit $D$ with $n$ input nodes $x_1,\mathrm{\dots },x_n$ and $m$ output nodes $y_1,\mathrm{\dots },y_m$ and a weight function $\omega :[m]\to \mathbb{Q}$. The goal is to find a locally maximal input for the optimization function $f(x_1,\mathrm{\dots },x_n)={\sum }_{i=1}^m\omega (i)y_i$ and 1-swap neighborhood (which we also refer to as a flip). The corresponding pivoting problem is as follows.

Note that when $\omega (i)=2^{i-1}$ (i.e., we interpret $f(x_1,\mathrm{\dots },x_n)$ as the number $y_m\mathrm{\dots }{y}_1$ written in binary), then we recover the classical Max-Circuit/Flip. Similarly, if we set $\omega (i)=-2^{i-1}$, then we have the Min-Circuit/Flip. Further, this problem also captures Weighted Max-SAT/Flip.

In our parameterized analysis of the above problems, we assume that the input is additionally equipped with an integer parameter $\kappa$ (see Section 2).

Recall that the parameter $\mathrm{\ell }$ is the distance of the given starting solution to the nearest local optimum in the transition graph. Observe that the time complexity of a pivoting problem is lower-bounded by the encoding length of the shortest maximal improving sequence from the initial solution (i.e., $\mathrm{\ell }$ times the encoding size of a solution). Hence, it is natural to consider the parameterized complexity of such a problem with respect to $\mathrm{\ell }$.

This section is dedicated to prove the following theorem.

Note that since Weighted Independent Set/3-Swap$[\text{Pivot}]$ is a special case of Subset Weight Optimization Problem/$c$-Swap$[\text{Pivot}]$, the hardness result above also extends to the latter problem.

The proof of Theorem 4.1 makes use of the following result.

Weighted Independent Set/3-Swap has been shown to be $\mathrm{𝖯𝖫𝖲}$-complete [18] via a $\mathrm{𝖯𝖫𝖲}$-reduction from Max Cut/Flip. However, this reduction was not argued to be tight, and is in fact unlikely to be. Here, we adapt it into a tight $\mathrm{𝖯𝖫𝖲}$-reduction; the proof is presented in Section 4.2.

The constructions in the proofs of Theorems 4.1 and 4.3 use the concept of (up/down)-elevators, defined as follows. Here, when we assume a certain (fixed) ordering on a set $X$, we denote by $X[i]$ the $i$th element in this ordering.

Let $G=(V,E)$ be a vertex-weighted graph and let $X\subseteq V$ be a set of size at least $2$. An $X$-elevator is a clique $L:=\{{\mathrm{\ell }}_1,\mathrm{\dots },{\mathrm{\ell }}_s\}$ of size $s:=|X|-1$, such that the vertices of $L$ have the same neighborhood outside of $L\cup X$ and for each $i\in [1,s-1]$, ${\mathrm{\ell }}_i$ has exactly the first $i+1$ vertices of $X$ as neighbors inside of $X$ for an arbitrary but fixed ordering on the vertices of $X$. We call the vertices of an elevator levels. The vertex ${\mathrm{\ell }}_{|L|}$ is the top-level, while ${\mathrm{\ell }}_1$ is the bottom-level.

We say that $L$ is an up-elevator if $\omega ({\mathrm{\ell }}_1)=\omega (X[1])+\omega (X[2])+1$ and for each $i\in [2,s-1]$, $\omega ({\mathrm{\ell }}_i)=\omega ({\mathrm{\ell }}_{i-1})+\omega (X[i+1])+1$. Similarly, we say that $L$ is a down-elevator if $\omega ({\mathrm{\ell }}_1)=\omega (x_1)+\omega (x_2)-1$ and for each $i\in [2,s-1]$, $\omega ({\mathrm{\ell }}_i)=\omega ({\mathrm{\ell }}_{i-1})+\omega (X[i+1])-1$. Note that the weights of the vertices in such an up- or down-elevator are uniquely defined by the weights and the order of the vertices of $X$. See Figure 2 for examples of an up-elevator and a down-elevator.

In this section, we define a new notion of $\mathrm{𝖯𝖫𝖲}$-reduction that transfers the result in Theorem 4.1 to other problems. We also demonstrate it by describing such a reduction from Weighted Independent Set/3-Swap$[\text{Pivot}]$ to Max-Circuit/Flip$[\text{Pivot}]$, which is a special case of Weighted Circuit/Flip$[\text{Pivot}]$.

In this section, we establish the algorithmic upper bounds that form the foundation of Main Finding 1. We recall that all results obtained in this section can also be directly translated to the $\mathrm{𝖯𝖫𝖲}$ and standard algorithm problem formulations.

There are numerous avenues for future research. First, one could identify further local search problems for which the pivoting formulation parameterized by the distance $\mathrm{\ell }$ of the starting solution to the closest local optimum is not $\mathrm{𝖥𝖯𝖳}$. Conversely, it is open whether there is any natural $\mathrm{𝖯𝖫𝖲}$-complete problem whose pivoting formulation admits a fixed-parameter algorithm when parameterized by $\mathrm{\ell }$. Observe that such a fixed-parameter algorithm exists for $\mathrm{𝖯𝖫𝖲}$-complete local search problems where the largest neighborhood has constant size or – slightly more generally – the maximum outdegree in the transition graph is constant. Such problems do exist, for example one may define an ordering of solutions and redefine the neighborhood to only contain the smallest solution with respect to this ordering. We are, however, not aware of any natural $\mathrm{𝖯𝖫𝖲}$-complete problem with only constant-size neighborhoods. In light of this discussion it seems more meaningful to ask whether there is any $\mathrm{𝖯𝖫𝖲}$-complete problem with an unbounded number of large neighborhoods whose pivoting formulation is $\mathrm{𝖥𝖯𝖳}$ with respect to $\mathrm{\ell }$.

In addition to $\mathrm{\ell }$, other parameters related to the transition graph could be considered. For example, since parameterization by the diameter of the transition graph or the distance to the furthest local optimum trivially yield fixed-parameter algorithms, one could consider parameters that are sandwiched between $\mathrm{\ell }$ and the diameter. By the discussion above, it is also motivated to consider parameter combinations $(q,\mathrm{\ell })$ where $q$ is some parameter that is always upper-bounded by the maximum out-degree of the transition graph.

Finally, it is open to obtain any parameterized hardness results for classic (non-pivoting) formulations of $\mathrm{𝖯𝖫𝖲}$ problems. A major obstacle towards such a result is that the existence of any polynomial-time Turing reduction of some $\mathrm{𝖭𝖯}$-hard problem $X$ to a problem $L$ in $\mathrm{𝖯𝖫𝖲}$ implies $\mathrm{𝖭𝖯}$=$\mathrm{𝖼𝗈𝖭𝖯}$ [16]. This excludes the standard approach of providing a polynomial parameter transformation from Multicolored Independent Set or similar classic problems. In other words, any parameterized reduction from Multicolored Independent Set or similar problems would need an exponential running time dependence on the parameter $k$. An alternative, perhaps more promising, approach would be to develop analogs of $\mathrm{𝖷𝖯}$ or $𝖶$[1] for the $\mathrm{𝖯𝖫𝖲}$ class and to identify complete problems for such classes. This, however, would not relate the hardness of such problems to existing complexity classes.