Asymptotically Optimal Inapproximability of Maxmin $k$-Cut Reconfiguration

One of the most well-studied reconfiguration problems, which we study in this paper, is $k$-Coloring Reconfiguration [10, 14, 15, 16, 17], whose source problem is $k$-Coloring. Recall that $k$-Coloring asks to decide if a graph $G$ is $k$-colorable; namely, there is a proper $k$-coloring $f:V(G)\to [k]$ of $G$, which renders every edge bichromatic.¹¹1 An edge is bichromatic if its endpoints receive different colors. A sequence over $k$-colorings of a graph $G$, denoted by $ℱ=(f^{(1)},\mathrm{\dots },f^{(T)})$, is called a reconfiguration sequence if every adjacent pair of $k$-colorings $f^{(t)},f^{(t+1)}$ differ in a single vertex. In the $k$-Coloring Reconfiguration problem, for a $k$-colorable graph $G$ and a pair of its proper $k$-colorings $f_{\mathrm{𝗌𝗍𝖺𝗋𝗍}},f_{\mathrm{𝖾𝗇𝖽}}:V(G)\to [k]$, we seek a reconfiguration sequence from $f_{\mathrm{𝗌𝗍𝖺𝗋𝗍}}$ to $f_{\mathrm{𝖾𝗇𝖽}}$ consisting only of proper $k$-colorings of $G$. See Figures 1 and 2 for Yes and No instances of $k$-Coloring Reconfiguration, respectively. If the number $k$ of available colors is sufficiently large (e.g., the maximum degree of $G$ plus $2$ or more [19, 39]), then the answer to this problem is always Yes. For a constant value of $k$, the following complexity results are known: $k$-Coloring Reconfiguration belongs to $𝖯$ if $k⩽3$ [17]²²2 Moreover, a reconfiguration sequence for Yes instances can be found in polynomial time. and is $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-complete for every $k⩾4$ [10]. Quite interestingly, $3$-Coloring “becomes” easy in the reconfiguration regime even though $3$-Coloring itself is $\mathrm{𝖭𝖯}$-complete [23, 45, 62]. Several existing work further investigate the parameterized complexity [11, 40] and the complexity for restricted graph classes [6, 8, 9, 16, 28, 64]. Note that the configuration graph of $k$-Coloring Reconfiguration is closely related to the Glauber dynamics [19, 39, 46]. See also Section 4 for related work.

In this paper, we study approximability of $k$-Coloring Reconfiguration. Since 2023, approximability of reconfiguration problems has been studied actively from both hardness and algorithmic sides [31, 32, 42, 51, 52, 53, 54, 55]. For a reconfiguration problem, its approximate version [38] allows to relax the feasibility of intermediate solutions, but requires to optimize the “worst” feasibility during reconfiguration. For example, an approximate version of Set Cover Reconfiguration ³³3 In this problem, we are asked to transform a given cover of a set system into another by repeatedly adding or removing a single set so as to minimize the maximum size of any cover during transformation. admits a $2$-factor approximation algorithm [38] while it is $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hard to approximate within a factor of $2-o(1)$ [31]. There are two natural approximate versions of $k$-Coloring Reconfiguration since $k$-Coloring has the following two approximate versions:

1. Maximizing the number of bichromatic edges:

For a (not necessarily $k$-colorable) graph $G$, the first approximate version asks to find a $k$-coloring of $G$ that makes as many edges as possible bichromatic. This problem is known by the names of Max $k$-Cut and Max $k$-Colorable Subgraph [27, 57].⁴⁴4 This problem is also called Max $k$-Coloring [4, 21] and Max $k$-Colorability [58]. We do not use these names to avoid confusion with other graph coloring problems.

2. Minimizing the number of used colors:

For a (not necessarily $k$-colorable) graph $G$, the second approximate version asks to find a proper coloring of $G$ that uses as few colors as possible. This problem is known as Chromatic Number and Graph Coloring.

In this paper, we study a reconfiguration analogue of the first version $k$-Cut, which we call Maxmin $k$-Cut Reconfiguration. In this problem, given a (not necessarily $k$-colorable) graph $G=(V,E)$ and a pair of its $k$-colorings $f_{\mathrm{𝗌𝗍𝖺𝗋𝗍}},f_{\mathrm{𝖾𝗇𝖽}}:V\to [k]$, we shall construct a reconfiguration sequence $ℱ$ from $f_{\mathrm{𝗌𝗍𝖺𝗋𝗍}}$ to $f_{\mathrm{𝖾𝗇𝖽}}$ consisting of any (not necessarily proper) $k$-colorings of $G$ that maximizes the minimum fraction of bichromatic edges of $G$, where the minimum is taken over all $k$-colorings of $ℱ$.

See Figure 2 for an example of Maxmin $k$-Cut Reconfiguration. Solving this problem, we may be able to find a “reasonable” reconfiguration sequence, which consists of almost-proper $k$-colorings, so that we can manage No instances of $k$-Coloring Reconfiguration.

Here, we briefly review known results on Maxmin $k$-Cut Reconfiguration. The $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hardness of exactly solving Maxmin $k$-Cut Reconfiguration for every $k⩾4$ follows from that of $k$-Coloring Reconfiguration [10]. For the $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hardness of approximation, the Probabilistically Checkable Reconfiguration Proof (PCRP) theorem due to Hirahara and Ohsaka [32] and Karthik C. S. and Manurangsi [42], along with a series of gap-preserving reductions due to Bonsma and Cereceda [10] and Ohsaka [51], implies that Maxmin 4-Cut Reconfiguration is $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hard to approximate within some constant factor.⁵⁵5See Section 4 for other applications of the PCRP theorem in $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hardness of approximating reconfiguration problems. However, the asymptotic behavior of approximability for Maxmin $k$-Cut Reconfiguration with respect to the number $k$ of available colors is not well understood.

In this paper, we find out that the asymptotically optimal approximation factor of Maxmin $k$-Cut Reconfiguration is $1-\mathrm{\Theta }\left(\frac{1}{k}\right)$. On the hardness side, we demonstrate the $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hardness of approximation within a factor of $1-\mathrm{\Omega }\left(\frac{1}{k}\right)$ for every $k⩾2$.

On the algorithmic side, we develop a deterministic $\left(1-\frac{2}{k}\right)$-factor approximation algorithm for every $k⩾2$.⁶⁶6 Although $1-\frac{2}{k}=0$ if $k=2$, the actual approximation factor can be arbitrarily close to $\frac{1}{4}$. See the full version of this paper [33].

To the best of our knowledge, this is the first non-trivial approximation algorithm for Maxmin $k$-Cut Reconfiguration.

Theorems 1.1 and 1.2 provide asymptotically tight lower and upper bounds for approximability of Maxmin $k$-Cut Reconfiguration.

The rest of this paper is organized as follows. In Sections 2 and 3, we present an overview of the proof of Theorems 1.1 and 1.2, respectively; the complete proofs can be found in the full version of this paper [33]. In Section 4, we review related work on variants of $k$-Coloring Reconfiguration, and approximability of Max $k$-Cut and reconfiguration problems. Proofs marked with $\ast$ are omitted and can be found in the full version of this paper [33].

For a nonnegative integer $n\in \mathbb{N}$, let $[n]≔\{1,2,\mathrm{\dots },n\}$. We use the Iverson bracket $⟦\cdot ⟧$; i.e., $⟦P⟧$ for a statement $P$ is defined as $1$ if $P$ is true and $0$ otherwise. A sequence $𝒮$ of a finite number of objects, $s^{(1)},\mathrm{\dots },s^{(T)}$, is denoted by $(s^{(1)},\mathrm{\dots },s^{(T)})$, and we write $s\in 𝒮$ to indicate that $s$ appears in $𝒮$. The symbol $\circ$ stands for a concatenation of two sequences or functions, and ${𝔖}_n$ for the set of all permutations over $[n]$. For a set $𝒮$, we write $X\sim 𝒮$ to mean that $X$ is a random variable uniformly drawn from $𝒮$. For two functions $f,g:𝒟\to ℛ$ over a finite domain $𝒟$, the relative Hamming distance between $f$ and $g$, denoted by $\mathrm{dist}(f,g)$, is defined as the fraction of positions on which $f$ and $g$ differ; namely,

We say that $f$ is $\epsilon$-close to $g$ if $\mathrm{dist}(f,g)⩽\epsilon$ and $\epsilon$-far from $g$ if $\mathrm{dist}(f,g)>\epsilon$. Similar notations are used for a set of functions $G$ from $𝒟$ to $ℛ$; e.g., $\mathrm{dist}(f,G)≔{\min }_{g\in G}\mathrm{dist}(f,g)$ and $f$ is $\epsilon$-close to $G$ if $\mathrm{dist}(f,G)⩽\epsilon$.

To prove Lemma 2.2, one might think of applying the existing proof techniques for the $\mathrm{𝖭𝖯}$-hardness of approximating Max $k$-Cut, which has the (asymptotically) same approximation threshold of $1-\mathrm{\Theta }\left(\frac{1}{k}\right)$ as Maxmin $k$-Cut Reconfiguration [4, 22, 27, 41] (see Section 4 for details). However, this approach does not work for proving Lemma 2.2: when a gap-preserving reduction from Max 2-Cut to Max $k$-Cut due to [27, 41] is used to reduce Maxmin 2-Cut Reconfiguration to Maxmin $k$-Cut Reconfiguration, the ratio between completeness and soundness becomes $1-𝒪\left(\frac{1}{k^2}\right)$.

To explain the detail, we briefly review the gap-preserving reduction due to Kann, Khanna, Lagergren, and Panconesi [41].⁷⁷7 The reduction due to Guruswami and Sinop [27] differs from that of [41] in that it starts from Max $3$-Cut to preserve the perfect completeness. For a graph $G=(V,E)$ and a positive even integer $k$, a new weighted graph $H$ is constructed as follows.

• $\mathrm{■}$

  Create fresh $\frac{k}{2}$ copies of each vertex $v$ of $G$, denoted by $v_1,\mathrm{\dots },v_{\frac{k}{2}}$.

• $\mathrm{■}$

  For each edge $(v,w)$ of $G$ and each pair $i,j\in \left[\frac{k}{2}\right]$, create an edge $(v_i,w_j)$ of weight $1$.

• $\mathrm{■}$

  For each vertex $v$ of $G$ and each pair $i\ne j\in \left[\frac{k}{2}\right]$, create an edge $(v_i,v_j)$ of weight equal to the degree of $v$.

See Figures 3 and 3 for illustration of $G$ and $H$, respectively. The total edge weight of $H$ is equal to $\left(\genfrac{}{}{0pt}{}{k}{2}\right)\cdot |E|$. By [41], this construction is a gap-preserving reduction from Max 2-Cut to Max $k$-Cut, implying the $\mathrm{𝖭𝖯}$-hardness of $\left(1-\mathrm{\Omega }\left(\frac{1}{k}\right)\right)$-factor approximation for Max $k$-Cut.

Let us apply the above reduction to reduce Maxmin 2-Cut Reconfiguration to Maxmin $k$-Cut Reconfiguration. Given a graph $G=(V,E)$ and a pair of its proper $2$-colorings $f_{\mathrm{𝗌𝗍𝖺𝗋𝗍}},f_{\mathrm{𝖾𝗇𝖽}}:V\to [2]$ as an instance of Maxmin 2-Cut Reconfiguration, we construct an instance of Maxmin $k$-Cut Reconfiguration as follows. First, create a weighted graph $H$ from $G$ according to [41]. Then, create a pair of $k$-colorings $f_{\mathrm{𝗌𝗍𝖺𝗋𝗍}}^{\prime },f_{\mathrm{𝖾𝗇𝖽}}^{\prime }:V(H)\to [k]$ of $H$ in a natural manner such that $f_{\mathrm{𝗌𝗍𝖺𝗋𝗍}}^{\prime }(v_i)≔f_{\mathrm{𝗌𝗍𝖺𝗋𝗍}}(v)+2(i-1)$ and $f_{\mathrm{𝖾𝗇𝖽}}^{\prime }(v_i)≔f_{\mathrm{𝖾𝗇𝖽}}(v)+2(i-1)$ for each vertex $v_i$ of $H$. See Figures 3, 3, 3, and 3 for illustration of $f_{\mathrm{𝗌𝗍𝖺𝗋𝗍}}$, $f_{\mathrm{𝖾𝗇𝖽}}$, $f_{\mathrm{𝗌𝗍𝖺𝗋𝗍}}^{\prime }$, and $f_{\mathrm{𝖾𝗇𝖽}}^{\prime }$, respectively. For each $i\in \left[\frac{k}{2}\right]$, we define $V_i≔\{v_i\mid v\in V\}$. Observe that $f_{\mathrm{𝗌𝗍𝖺𝗋𝗍}}^{\prime }$ and $f_{\mathrm{𝖾𝗇𝖽}}^{\prime }$ are proper if so are $f_{\mathrm{𝗌𝗍𝖺𝗋𝗍}}$ and $f_{\mathrm{𝖾𝗇𝖽}}$, and each vertex of $V_i$ is colored in $2i-1$ or $2i$. Here, we claim that ${\mathrm{𝗈𝗉𝗍}}_H(f_{\mathrm{𝗌𝗍𝖺𝗋𝗍}}^{\prime }\leftrightsquigarrow f_{\mathrm{𝖾𝗇𝖽}}^{\prime })⩾1-\frac{2}{k(k-1)}$ independent of the value of ${\mathrm{𝗈𝗉𝗍}}_G(f_{\mathrm{𝗌𝗍𝖺𝗋𝗍}}\leftrightsquigarrow f_{\mathrm{𝖾𝗇𝖽}})$. Consider a reconfiguration sequence ${ℱ}^{\prime }$ from $f_{\mathrm{𝗌𝗍𝖺𝗋𝗍}}^{\prime }$ to $f_{\mathrm{𝖾𝗇𝖽}}^{\prime }$ obtained by recoloring vertices of $V_1,V_2,\mathrm{\dots },V_{\frac{k}{2}}$ in this order. Suppose that we are on the way of recoloring the vertices of $V_i$. The subgraph $H[V_i]$ may contain (at most) $|E|$ monochromatic edges, but all other $(\frac{k}{2}-1)$ subgraphs $H[V_j]$ for $j\ne i$ do not contain any monochromatic edges, deriving that

This is undesirable because the ratio between completeness and soundness is at least $1-𝒪\left(\frac{1}{k^2}\right)$.

Our gap-preserving reduction from Maxmin 2-Cut Reconfiguration to Maxmin $k$-Cut Reconfiguration is completely different from those of [27, 41]. Briefly speaking, we shall encode a $2$-coloring of each vertex of a graph $G$ by a $k$-coloring of a $k\times k$ grid ${[k]}^2$. Our proposed encoding is motivated by the following scenario: Suppose that for a graph $G=(V,E)$ and a pair of its proper $k$-colorings $f,g:V\to [k]$, we would like to find an optimal reconfiguration sequence from $f$ to $g$ (see Figures 4 and 4). For each pair of colors $\alpha ,\beta \in [k]$, let $V_{\alpha ,\beta }$ denote the set of vertices in $V$ colored in $\alpha$ by $f$ and in $\beta$ by $g$ (see Figure 4); namely,

When $V_{\alpha ,\beta }$’s are placed on a $k\times k$ grid, $f$ looks “horizontally striped” while $g$ looks “vertically striped” (see Figures 4 and 4). Since both $f$ and $g$ are proper, there may exist edges between vertices in $V_{{\alpha }_1,{\beta }_1}$ and $V_{{\alpha }_2,{\beta }_2}$ only if ${\alpha }_1\ne {\alpha }_2$ and ${\beta }_1\ne {\beta }_2$ (see Figure 4). On the other hand, every reconfiguration sequence from $f$ to $g$ seems to make a nonnegligible fraction of edges into monochromatic. The above structural observation motivates the following two ideas (see also Figure 5 for illustration):

Idea 1:

Consider the “striped” pattern represented by a $k$-coloring of ${[k]}^2$ as if it were encoding $[2]$; i.e., the “horizontally striped” pattern represents $1$, whereas the “vertically striped” pattern represents $2$. This encoding can be thought of as a very redundant error-correcting code from $[2]$ to ${[k]}^{{[k]}^2}$.

Idea 2:

Given a graph $G=(V,E)$ and a collection of $|V|$ $k$-colorings of ${[k]}^2$, one for each vertex of $G$, we test if these $k$-colorings encode a proper $2$-coloring of $G$. Specifically, we will design a probabilistic verifier that checks if (1) a $k$-coloring of ${[k]}^2$ associated with each vertex of $G$ is close to a striped pattern, and (2) a pair of $k$-colorings of ${[k]}^2$ corresponding to each edge of $G$ encode different colors. In the subsequent sections, we will introduce the following three auxiliary verifiers to achieve this requirement: Stripe, consistency, and edge verifiers.

We will say that a $k$-coloring $f:{[k]}^2\to [k]$ is horizontally striped if $f(x,y)=\sigma (y)$ for every $(x,y)\in {[k]}^2$ for some permutation $\sigma \in {𝔖}_k$, vertically striped if $f(x,y)=\sigma (x)$ for every $(x,y)\in {[k]}^2$ for some permutation $\sigma \in {𝔖}_k$, and striped if it is horizontally or vertically striped.

There are several types of reconfiguration problems [48, 50, 63]. One is connectivity problems, which ask if the configuration graph is entirely connected. In the connectivity variant of $k$-Coloring Reconfiguration, we are asked to decide if every pair of proper $k$-colorings of a graph $G$ is a Yes instance of $k$-Coloring Reconfiguration. Such a graph $G$ is said to be $k$-mixing. It is $\mathrm{𝖼𝗈𝖭𝖯}$-hard to decide if a graph is $k$-mixing for every $k⩾3$ [12, 16]. The name of $k$-mixing comes from the relation to the (rapid) mixing of the Glauber dynamics [19, 39, 46]. The Glauber dynamics is a Markov Chain such that starting from a graph $G$ and a proper $k$-coloring of $G$, we repeatedly recolor a random vertex with a random color (as long as it yields a proper $k$-coloring). The Glauber dynamics is ergodic only if $G$ is $k$-mixing.

Other algorithmic and structural problems related to $k$-Coloring Reconfiguration include finding the shortest reconfiguration sequence [7, 17, 40] and bounding the diameter of the configuration graph [8, 9, 10, 17], respectively. See also Mynhardt and Nasserasr [49], Nishimura [50, §6], and van den Heuvel [63, §3].

The Max $k$-Cut problem (a.k.a. Max $k$-Colorable Subgraph [27, 57]) seeks a $k$-coloring of a graph that makes the maximum number of edges bichromatic. Observe easily that a random $k$-coloring makes a $\left(1-\frac{1}{k}\right)$-fraction of edges bichromatic in expectation. Frieze and Jerrum [22] developed a $\left(1-\frac{1}{k}+\frac{2\ln k}{k^2}\right)$-factor approximation algorithm. On the hardness side, $\left(1-\frac{1}{17k+𝒪(1)}\right)$-factor approximation is $\mathrm{𝖭𝖯}$-hard for every $k⩾3$ [4, 27, 41]. For the special case of $k=2$, i.e., Max Cut, the current best approximation factor is $\approx 0.878$ [25]. This is proven to be optimal [44, 47] under the Unique Games Conjecture [43].

Ito, Demaine, Harvey, Papadimitriou, Sideri, Uehara, and Uno [38] proved that several reconfiguration problems (e.g., Maxmin SAT Reconfiguration) are $\mathrm{𝖭𝖯}$-hard to approximate relying on the $\mathrm{𝖭𝖯}$-hardness of approximating the source problems (e.g., Max SAT). Since most reconfiguration problems are $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-complete, $\mathrm{𝖭𝖯}$-hardness results are not optimal. In fact, [38] posed $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hardness of approximation as an open problem.

Motivated by the $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hardness of approximation for reconfiguration problems, Ohsaka [51] postulated a reconfiguration analogue of the PCP theorem [2, 3], called the Reconfiguration Inapproximability Hypothesis (RIH). Under RIH, (approximate versions of) several reconfiguration problems are $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hard to approximate, including those of 3-SAT, Independent Set, Vertex Cover, and Clique. Recently, Hirahara and Ohsaka [32] and Karthik C. S. and Manurangsi [42] gave a proof of RIH by establishing the Probabilistically Checkable Reconfiguration Proof (PCRP) theorem, which provides a new PCP-type characterization of $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$. The PCRP theorem, along with a series of gap-preserving reductions [31, 32, 51, 53], implies unconditional $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hardness of approximation results for several reconfiguration problems, thereby resolving the open problem of [38] affirmatively.

One recent trend regarding approximability of reconfiguration problems is to prove an explicit factor of $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hardness of approximation. In the $\mathrm{𝖭𝖯}$ regime, the parallel repetition theorem [61] can be used to derive many strong inapproximability results, e.g., [5, 20, 35, 36, 65]. However, for a reconfiguration analogue of two-prover games, a naive parallel repetition does not reduce its soundness error [55]. Ohsaka [53] adapted Dinur’s gap amplification [18, 59, 60] to show that Maxmin 2-CSP Reconfiguration and Minmax Set Cover Reconfiguration are $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hard to approximate within a factor of $0.9942$ and $1.0029$, respectively. Subsequently, Karthik C. S. and Manurangsi [42] showed that Minmax Set Cover Reconfiguration is $\mathrm{𝖭𝖯}$-hard to approximate within a factor of $2-\epsilon$ for every $\epsilon >0$. Hirahara and Ohsaka [31] demonstrated that Minmax Set Cover Reconfiguration is $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hard to approximate within a factor of $2-o(1)$, improving upon [42, 53]. Since Minmax Set Cover Reconfiguration admits a $2$-factor approximation algorithm [38], this is the first optimal $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hardness result for approximability of any reconfiguration problem.

Approximation algorithms have been developed for several reconfiguration problems; e.g., Maxmin 2-CSP Reconfiguration admits a $\left(\frac{1}{2}-\epsilon \right)$-factor approximation [42], Subset Sum Reconfiguration admits a PTAS [37], and Submodular Reconfiguration admits a constant-factor approximation [56].