On Approximate Reconfigurability of Label Cover

Naoto Ohsaka CyberAgent, Inc., Tokyo, Japan. [email protected]; [email protected]

Abstract

Given a two-prover game $G$ and its two satisfying labelings $\psi_{\mathsf{s}}$ and $\psi_{\mathsf{t}}$ , the Label Cover Reconfiguration problem asks whether $\psi_{\mathsf{s}}$ can be transformed into $\psi_{\mathsf{t}}$ by repeatedly changing the value of a vertex while preserving any intermediate labeling satisfying $G$ . We consider an optimization variant of Label Cover Reconfiguration by relaxing the feasibility of labelings, referred to as Maxmin Label Cover Reconfiguration: we are allowed to transform by passing through any non-satisfying labelings, but required to maximize the minimum fraction of satisfied edges during transformation from $\psi_{\mathsf{s}}$ to $\psi_{\mathsf{t}}$ . Since the parallel repetition theorem of Raz (SIAM J. Comput., 1998) [Raz98], which implies NP-hardness of Label Cover within any constant factor, produces strong inapproximability results for many NP-hard problems, one may think of using Maxmin Label Cover Reconfiguration to derive inapproximability results for reconfiguration problems. We prove the following results on Maxmin Label Cover Reconfiguration, which display different trends from those of Label Cover and the parallel repetition theorem:

•

Maxmin Label Cover Reconfiguration can be approximated within a factor of nearly $\frac{1}{4}$ for restricted graph classes, including slightly dense graphs and balanced bipartite graphs.
•

A naive parallel repetition of Maxmin Label Cover Reconfiguration does not decrease the optimal objective value.
•

Label Cover Reconfiguration on projection games can be decided in polynomial time.

The above results suggest that a reconfiguration analogue of the parallel repetition theorem is unlikely.

1 Introduction

Background.

In reconfiguration problems [IDH⁺11], given a pair of feasible solutions for a combinatorial problem, we wish to find a step-by-step transformation from one to the other while the feasibility of every intermediate solution is maintained. Under the framework of reconfiguration [IDH⁺11], numerous reconfiguration problems have been derived from classical search problems; refer to the surveys by Nishimura [Nis18] and van den Heuvel [vdH13] for an overview of reconfiguration.

In this article, we consider reconfigurability of Label Cover [ABSS97] and its approximation. Given a two-prover game $G$ and its two satisfying labelings $\psi_{\mathsf{s}}$ and $\psi_{\mathsf{t}}$ , the Label Cover Reconfiguration problem asks whether $\psi_{\mathsf{s}}$ can be transformed into $\psi_{\mathsf{t}}$ by repeatedly changing the value of a vertex preserving any intermediate labeling satisfying $G$ . We can consider an optimization variant of this problem by relaxing the feasibility of labelings, referred to as Maxmin Label Cover Reconfiguration: we are allowed to transform by passing through any non-satisfying labelings, but required to maximize the minimum fraction of satisfied edges during transformation from $\psi_{\mathsf{s}}$ to $\psi_{\mathsf{t}}$ . Solving Maxmin Label Cover Reconfiguration approximately, we may find approximate reconfiguration for Label Cover Reconfiguration consisting of almost-satisfying labelings.

The recent work of the author [Ohs23] demonstrated that assuming PSPACE-hardness of approximation for Maxmin CSP Reconfiguration (which implies that for Maxmin Label Cover Reconfiguration), a bunch of reconfiguration problems are also PSPACE-hard to approximate, say, within a factor of $(1-\varepsilon)$ for some $\varepsilon\in(0,1)$ . One limitation of this approach is that the value of such $\varepsilon$ might be too small to rule out a $0.999\cdots 9$ -approximation algorithm. In NP optimization problems, the parallel repetition theorem due to Raz [Raz98] serves as the “mother” of many strong inapproximability results [Fei98, Hås99, Hås01]. The crux of this theorem is to imply along with the PCP theorem [AS98, ALM⁺98] that for every $\varepsilon\in(0,1)$ , there is a finite alphabet $\Sigma$ such that Label Cover on $\Sigma$ is NP-hard to approximate within a factor of $\varepsilon$ . One might thus think of a reconfiguration analogue of the parallel repetition theorem for Maxmin Label Cover Reconfiguration, which would help in improving PSPACE-hardness of approximation for reconfiguration problems. Our contribution is to give evidence that such hopes are probably dashed.

Our Results.

We present a few results on Maxmin Label Cover Reconfiguration, which display different trends from those for Label Cover and the parallel repetition theorem.

•

In Section 2, we prove that Maxmin Label Cover Reconfiguration can be approximated within a factor of nearly $\frac{1}{4}$ for restricted graph classes, including slightly dense graphs and balanced bipartite graphs,
•

In Section 3, we further show that a naive parallel repetition of Maxmin Label Cover Reconfiguration does not decrease the optimal objective value, defined as the worst fraction of satisfied edges during transformation.
•

In Section 4, we develop a polynomial-time algorithm for deciding Label Cover Reconfiguration on projection games, which is based on a simple characterization of the reconfigurability between a pair of satisfying labelings.

Our results suggest that a reconfiguration analogue of the parallel repetition theorem is unlikely; thus, we should resort to a different approach to derive an improved factor of inapproximability for reconfiguration problems.

Preliminaries.

For two integers $m,n\in\mathbb{N}$ with $m\leqslant n$ , let $[n]\triangleq\{1,2,\ldots,n\}$ and $[m\mathrel{..}\nobreak n]\triangleq\{m,m+1,\ldots,n-1,n\}$ . For a statement $P$ , $\llbracket P\rrbracket$ is $1$ if $P$ is true, and $0$ otherwise. We formally define Label Cover Reconfiguration and its optimization variant.A constraint graph is defined as a tuple $G=(V,E,\Sigma,\Pi)$ , where

•

$(V,E)$ is an undirected graph called the underlying graph of $G$ ,
•

$\Sigma$ is a finite set called the alphabet, and
•

$\Pi=(\pi_{e})_{e\in E}$ is a collection of binary constraints, where each $\pi_{e}\subseteq\Sigma^{e}$ consists of pairs of admissible values that endpoints of $e$ can take.

If the underlying graph of $G$ is a bipartite graph, $G$ is called a two-prover game or simply game. We write $G=(X,Y,E,\Sigma,\Pi)$ to stress that the underlying graph of $G$ is a bipartite graph with bipartition $(X,Y)$ . Unless otherwise specified, we use $G$ to represent a game. Moreover, $G$ is said to be a projection game if every constraint $\pi_{(x,y)}$ for $(x,y)\in E$ has a projection property; i.e., each value $\beta\in\Sigma$ for $y$ has a unique value $\alpha\in\Sigma$ for $x$ such that $(\alpha,\beta)\in\pi_{(x,y)}$ . Such $\alpha$ is denoted $\pi_{(x,y)}(\beta)$ .

A labeling for a constraint graph $G$ is a mapping $\psi\colon V\to\Sigma$ that assigns value of $\Sigma$ to vertex of $V$ . We say that $\psi$ satisfies edge $e=(v,w)\in E$ (or constraint $\pi_{e}$ ) if $(\psi(v),\psi(w))\in\pi_{e}$ , and $\psi$ satisfies $G$ if it satisfies all edges of $G$ . For two satisfying labelings $\psi_{\mathsf{s}}$ and $\psi_{\mathsf{t}}$ for $G$ , a reconfiguration sequence from $\psi_{\mathsf{s}}$ to $\psi_{\mathsf{t}}$ is any sequence of labelings starting from $\psi_{\mathsf{s}}$ and ending with $\psi_{\mathsf{t}}$ such that each labeling is obtained from the previous one by changing the value of a single vertex; i.e., they differ in exactly one vertex. The Label Cover Reconfiguration problem is defined as follows:

{itembox}

[l]Label Cover Reconfiguration Input: a satisfiable game $G$ and its two satisfying labelings $\psi_{\mathsf{s}}$ and $\psi_{\mathsf{t}}$ . Question: is there a reconfiguration sequence of satisfying labelings from $\psi_{\mathsf{s}}$ to $\psi_{\mathsf{t}}$ ?

Label Cover Reconfiguration is known to be PSPACE-complete, e.g., [GKMP09]. We then proceed to an optimization variant [IDH⁺11] of Label Cover Reconfiguration, in which we are allowed to touch non-satisfying labelings. For a game $G=(V,E,\Sigma,\Pi)$ and a labeling $\psi\colon V\to\Sigma$ , let $\operatorname{\mathsf{val}}_{G}(\psi)$ denote the fraction of edges satisfied by $\psi$ ; namely,

\displaystyle\operatorname{\mathsf{val}}_{G}(\psi)\triangleq\frac{1}{|E|}\cdot\left|\left\{e\in E\Bigm{|}\psi\text{ satisfies }e\right\}\right|.

(1.1)

For any reconfiguration sequence $\mathbf{\bm{\uppsi}}=\langle\psi^{(0)},\ldots,\psi^{(\ell)}\rangle$ , let $\operatorname{\mathsf{val}}_{G}(\mathbf{\bm{\uppsi}})$ denote the minimum fraction of satisfied edges over all $\psi^{(i)}$ ’s in $\mathbf{\bm{\uppsi}}$ ; namely,

\displaystyle\operatorname{\mathsf{val}}_{G}(\mathbf{\bm{\uppsi}})\triangleq\min_{\psi^{(i)}\in\mathbf{\bm{\uppsi}}}\operatorname{\mathsf{val}}_{G}(\psi^{(i)}).

(1.2)

Then, Maxmin Label Cover Reconfiguration is defined as the following optimization problem:

{itembox}

[l]Maxmin Label Cover Reconfiguration Input: a satisfiable game $G$ and its two satisfying labelings $\psi_{\mathsf{s}}$ and $\psi_{\mathsf{t}}$ . Question: maximize $\operatorname{\mathsf{val}}_{G}(\mathbf{\bm{\uppsi}})$ subject to that $\mathbf{\bm{\uppsi}}$ is a reconfiguration sequence from $\psi_{\mathsf{s}}$ to $\psi_{\mathsf{t}}$ .

2 Nearly $\frac{1}{4}$ -factor Approximation

We show that Maxmin Label Cover Reconfiguration is approximately reconfigurable within a factor of nearly $\frac{1}{4}$ for some graph classes. For a game $G=(V,E,\Sigma,\Pi)$ and its two labelings $\psi_{\mathsf{s}},\psi_{\mathsf{t}}\colon V\to\Sigma$ , let $\operatorname{\mathsf{val}}_{G}(\psi_{\mathsf{s}}\leftrightsquigarrow\psi_{\mathsf{t}})$ denote the maximum value of $\operatorname{\mathsf{val}}_{G}(\mathbf{\bm{\uppsi}})$ over all possible reconfiguration sequences $\mathbf{\bm{\uppsi}}$ from $\psi_{\mathsf{s}}$ to $\psi_{\mathsf{t}}$ ; namely,

\displaystyle\operatorname{\mathsf{val}}_{G}(\psi_{\mathsf{s}}\leftrightsquigarrow\psi_{\mathsf{t}})\triangleq\max_{\mathbf{\bm{\uppsi}}=\langle\psi_{\mathsf{s}},\ldots,\psi_{\mathsf{t}}\rangle}\operatorname{\mathsf{val}}_{G}(\mathbf{\bm{\uppsi}}).

(2.1)

Theorem 2.1.

For a game $G$ having $m$ edges and two of its satisfying labelings $\psi_{\mathsf{s}},\psi_{\mathsf{t}}\colon V\to\Sigma$ , the following holds:

•

If the average degree of $G$ is at least $\frac{6}{\varepsilon}$ for $\varepsilon\in(0,\frac{1}{4})$ , then $\operatorname{\mathsf{val}}_{G}(\psi_{\mathsf{s}}\leftrightsquigarrow\psi_{\mathsf{t}})\geqslant\frac{1}{4}-\varepsilon$ . Moreover, the same result holds even if $G$ is a general (i.e., non-bipartite) constraint graph.
•

If $G$ is balanced (i.e., the two parts have the same size), then $\operatorname{\mathsf{val}}_{G}(\psi_{\mathsf{s}}\leftrightsquigarrow\psi_{\mathsf{t}})\geqslant\frac{1}{4}\left(1-\frac{1}{\sqrt{m}}\right)$ .

The proof of Theorem 2.1 relies on the following claim.

Claim 2.2.

For a constraint graph $G=(V,E,\Sigma,\Pi)$ and its two satisfying labelings $\psi_{\mathsf{s}}$ and $\psi_{\mathsf{t}}$ , it holds that

\displaystyle\operatorname{\mathsf{val}}_{G}(\psi_{\mathsf{s}}\leftrightsquigarrow\psi_{\mathsf{t}})\geqslant\max_{S\subset V}\min\left\{\frac{|E[S]|}{|E|},\frac{|E[V\setminus S]|}{|E|}\right\},

(2.2)

where $E[S]$ is the edge set of a subgraph of $G$ induced by vertex set $S$ .

Proof.

For a vertex set $S\subset V$ , we define a labeling $\psi_{\text{via}}\colon V\to\Sigma$ as follows:

\displaystyle\psi_{\text{via}}(v)\triangleq\begin{cases}\psi_{\mathsf{s}}(v)&\text{if }v\in S,\\ \psi_{\mathsf{t}}(v)&\text{if }v\notin S.\end{cases}

(2.3)

Consider transforming $\psi_{\mathsf{s}}$ into $\psi_{\text{via}}$ by changing the value of $v\notin S$ from $\psi_{\mathsf{s}}(v)$ to $\psi_{\mathsf{t}}(v)$ one by one. Since the value of vertices in $S$ has never been changed, any edge of $G[S]$ are always satisfied during this transformation; i.e., $\operatorname{\mathsf{val}}_{G}(\psi_{\mathsf{s}}\leftrightsquigarrow\psi_{\text{via}})\geqslant\frac{|E[S]|}{|E|}$ . Similarly, it follows that $\operatorname{\mathsf{val}}_{G}(\psi_{\text{via}}\leftrightsquigarrow\psi_{\mathsf{t}})\geqslant\frac{|E[V\setminus S]|}{|E|}$ . Consequently, we derive

\displaystyle\operatorname{\mathsf{val}}_{G}(\psi_{\mathsf{s}}\leftrightsquigarrow\psi_{\mathsf{t}})\geqslant\min\Bigl{\{}\operatorname{\mathsf{val}}_{G}(\psi_{\mathsf{s}}\leftrightsquigarrow\psi_{\text{via}}),\operatorname{\mathsf{val}}_{G}(\psi_{\text{via}}\leftrightsquigarrow\psi_{\mathsf{t}})\Bigr{\}}\geqslant\min\left\{\frac{|E[S]|}{|E|},\frac{|E[V\setminus S]|}{|E|}\right\},

(2.4)

as desired. ∎

We focus on the case that $G=(X,Y,E,\Sigma,\Pi)$ is balanced; i.e., $|X|=|Y|$ . We wish to partition each $X$ and $Y$ in a particular well-balanced manner. To this end, we use the following auxiliary lemma.

Lemma 2.3.

For any $n$ positive integers $x_{1},\ldots,x_{n}$ in the range of $[n]$ , there exists a partition $(S,T)$ of $[n]$ such that

\displaystyle\min\left\{\sum_{i\in S}x_{i},\sum_{i\in T}x_{i}\right\}\geqslant\frac{m-\sqrt{m}}{2},\text{ where }m\triangleq\sum_{i\in[n]}x_{i}.

(2.5)

Moreover, such $S$ and $T$ can be found in polynomial time.

Proof.

The case of $n=1$ is trivial because $m=1$ and so $\frac{m-\sqrt{m}}{2}=0$ ; we thus assume that $n\geqslant 2$ . Denote $\mathbf{\bm{x}}(S)\triangleq\sum_{i\in S}x_{i}$ for any $S\subseteq[n]$ . Consider the following naive greedy algorithm for Bin Packing:

{itembox}

[l]Greedy algorithm

1:sort

x_{i}

’s in descending order.

2:define

S^{(0)}\triangleq\emptyset

and

T^{(0)}\triangleq\emptyset

3:for

i=1\;\textbf{to}\;n

4: if

\mathbf{\bm{x}}(S^{(i-1)})<\mathbf{\bm{x}}(T^{(i-1)})

then

5: define

S^{(i)}\triangleq S^{(i-1)}\cup\{i\}

and

T^{(i)}\triangleq T^{(i-1)}

6: else

7: define

S^{(i)}\triangleq S^{(i-1)}

and

T^{(i)}\triangleq T^{(i-1)}\cup\{i\}

8:return

S^{(n)}

and

T^{(n)}

We show

\displaystyle\left|\mathbf{\bm{x}}(S^{(n)})-\mathbf{\bm{x}}(T^{(n)})\right|\leqslant\sqrt{m}.

(2.6)

Define

\displaystyle d\triangleq\frac{m}{n}\text{ and }\varepsilon\triangleq\sqrt{\frac{d}{n}}=\sqrt{\frac{m}{n^{2}}}.

(2.7)

Since for every $k\in[n]$ , $x_{1},\ldots,x_{k}$ are at least $x_{k}$ and $x_{k+1},\ldots,x_{n}$ are at least $1$ , we have

\displaystyle\begin{aligned} &\underbrace{x_{k}\cdot k}_{\text{contribution of }x_{1},\ldots,x_{k}}+\underbrace{1\cdot(n-k)}_{\text{contribution of }x_{k+1},\ldots,x_{n}}\leqslant m=nd\\ &\implies k(x_{k}-1)\leqslant(d-1)n\\ &\implies x_{k}\leqslant\frac{d-1}{k}n+1.\end{aligned}

(2.8)

Observing easily that

\displaystyle\left|\mathbf{\bm{x}}(S^{(\lceil\varepsilon n\rceil-1)})-\mathbf{\bm{x}}(T^{(\lceil\varepsilon n\rceil-1)})\right|\leqslant n

(2.9)

due to the nature of the greedy algorithm, we consider the following two cases:

(Case 1)

If the absolute difference between $\mathbf{\bm{x}}(S^{(\lceil\varepsilon n\rceil-1)})$ and $\mathbf{\bm{x}}(T^{(\lceil\varepsilon n\rceil-1)})$ is larger than $\mathbf{\bm{x}}([\lceil\varepsilon n\rceil\mathrel{..}\nobreak n])$ , then we would have added all of $[\lceil\varepsilon n\rceil\mathrel{..}\nobreak n]$ into either $S^{(n)}$ or $T^{(n)}$ . Thus, the absolute difference between $\mathbf{\bm{x}}(S^{(n)})$ and $\mathbf{\bm{x}}(T^{(n)})$ will be simply

\displaystyle\left|\mathbf{\bm{x}}(S^{(n)})-\mathbf{\bm{x}}(T^{(n)})\right|\leqslant\underbrace{\left|\mathbf{\bm{x}}(S^{(\lceil\varepsilon n\rceil-1)})-\mathbf{\bm{x}}(T^{(\lceil\varepsilon n\rceil-1)})\right|}_{\leqslant n}-\underbrace{\mathbf{\bm{x}}([\lceil\varepsilon n\rceil\mathrel{..}\nobreak n])}_{\geqslant n-\lceil\varepsilon n\rceil+1}\leqslant\lceil\varepsilon n\rceil-1\leqslant\varepsilon n.

(2.10)

(Case 2)

Otherwise, the absolute difference between $\mathbf{\bm{x}}(S^{(n)})$ and $\mathbf{\bm{x}}(T^{(n)})$ must be at most $x_{\lceil\varepsilon n\rceil}$ . Using Eq. 2.8, we can derive

\displaystyle\left|\mathbf{\bm{x}}(S^{(n)})-\mathbf{\bm{x}}(T^{(n)})\right|\leqslant x_{\lceil\varepsilon n\rceil}\leqslant\frac{d-1}{\lceil\varepsilon n\rceil}n+1\leqslant\frac{d-1}{\varepsilon}+1\leqslant\frac{d}{\varepsilon},

(2.11)

where the last inequality is due to the fact that $\varepsilon\in(0,1]$ .

In either case, we obtain

\displaystyle\left|\mathbf{\bm{x}}(S^{(n)})-\mathbf{\bm{x}}(T^{(n)})\right|\leqslant\max\left\{\varepsilon n,\frac{d}{n}\right\}=\sqrt{dn}=\sqrt{m}.

(2.12)

Consequently, we derive

\displaystyle\begin{aligned} &2\cdot\min\Bigl{\{}\mathbf{\bm{x}}(S^{(n)}),\mathbf{\bm{x}}(T^{(n)})\Bigr{\}}+\sqrt{m}\geqslant\min\Bigl{\{}\mathbf{\bm{x}}(S^{(n)}),\mathbf{\bm{x}}(T^{(n)})\Bigr{\}}+\max\Bigl{\{}\mathbf{\bm{x}}(S^{(n)}),\mathbf{\bm{x}}(T^{(n)})\Bigr{\}}=m\\ \implies&\min\Bigl{\{}\mathbf{\bm{x}}(S^{(n)}),\mathbf{\bm{x}}(T^{(n)})\Bigr{\}}\geqslant\frac{m-\sqrt{m}}{2}.\end{aligned}

(2.13)

completing the proof. ∎

We are now ready to prove Theorem 2.1.

Proof of Theorem 2.1.

By Claim 2.2, it suffices to show the existence of a desired partition of $V$ for each case. The statement for the case of large average degree directly follows from Kühn and Osthus [KO03, Corollary 18], stating that for every graph $G$ of $m$ edges and average degree $\frac{6}{\varepsilon}$ , its vertex set can be partitioned into $S$ and $T$ such that both $G[S]$ and $G[T]$ contain at least $m\left(\frac{1}{4}-\varepsilon\right)$ edges.

Suppose then that $G=(X,Y,E,\Sigma,\Pi)$ is a balanced game over $m$ edges such that $|X|=|Y|$ . Using Lemma 2.3, we construct a pair of partitions $(S,\overline{S})$ and $(T,\overline{T})$ of $X$ and $Y$ , respectively, such that

\displaystyle\min\left\{\sum_{x\in S}d_{G}(x),\sum_{x\in\overline{S}}d_{G}(x)\right\}\geqslant\frac{m-\sqrt{m}}{2}\text{ and }\min\left\{\sum_{x\in T}d_{G}(x),\sum_{x\in\overline{T}}d_{G}(x)\right\}\geqslant\frac{m-\sqrt{m}}{2},

(2.14)

where $d_{G}(v)$ denotes the degree of $v$ in $G$ . Define $\theta\triangleq\frac{m-\sqrt{m}}{4}$ . By case analysis, we show that either of $(S\cup T,\overline{S}\cup\overline{T})$ or $(S\cup\overline{T},\overline{S}\cup T)$ gives us a desired partition.

(Case 1)

$e_{G}(S,T)\leqslant\theta$ : $e_{G}(S,\overline{T})$ and $e_{G}(\overline{S},T)$ can be bounded from below as follows:

	$\displaystyle e_{G}(S,\overline{T})$	$\displaystyle=e_{G}(S,T\cup\overline{T})-e_{G}(S,T)\geqslant\sum_{x\in S}d_{G}(x)-\theta\geqslant\frac{m-\sqrt{m}}{4},$		(2.15)
	$\displaystyle e_{G}(\overline{S},T)$	$\displaystyle=e_{G}(S\cup\overline{S},T)-e_{G}(\overline{S},\overline{T})\geqslant\sum_{y\in T}d_{G}(y)-\theta\geqslant\frac{m-\sqrt{m}}{4}.$		(2.16)

(Case 2)

$e_{G}(\overline{S},\overline{T})\leqslant\theta$ : Similarly to (Case 1), we can bound

\displaystyle e_{G}(S,\overline{T})\geqslant\frac{m-\sqrt{m}}{4}\text{ and }e_{G}(\overline{S},T)\geqslant\frac{m-\sqrt{m}}{4}.

(2.17)

(Case 3)

$e_{G}(S,T)>\theta$ and $e_{G}(\overline{S},\overline{T})>\theta$ : We are done since $S\cup T$ and $\overline{S}\cup\overline{T}$ have a desired property.

Consequently, in either case, we obtain

\displaystyle\min\Bigl{\{}e_{G}(S,T),e_{G}(\overline{S},\overline{T})\Bigr{\}}\geqslant\frac{m-\sqrt{m}}{4}\text{ or }\min\Bigl{\{}e_{G}(S,\overline{T}),e_{G}(\overline{S},T)\Bigr{\}}\geqslant\frac{m-\sqrt{m}}{4},

(2.18)

which completes the proof. ∎

3 Parallel Repetition Does Not Amplify Gap

Here, we show that a naive parallel repetition of Label Cover Reconfiguration does not amplify the gap unlike the parallel repetition theorem [Raz98]. We first define the product of two games.

Definition 3.1.

Let $G_{1}=(X_{1},Y_{1},E_{1},\Sigma_{1},\Pi_{1}=(\pi_{1,e})_{e\in E_{1}})$ and $G_{2}=(X_{2},Y_{2},E_{2},\Sigma_{2},\Pi_{2}=(\pi_{2,e})_{e\in E_{2}})$ be two games. Then, the product of $G_{1}$ and $G_{2}$ , denoted $G_{1}\otimes G_{2}$ , is defined as a new game $(X_{1}\times X_{2},Y_{1}\times Y_{2},E,\Sigma_{1}\times\Sigma_{2},\Pi=(\pi_{e})_{e\in E})$ , where

\displaystyle E\triangleq\left\{((x_{1},x_{2}),(y_{1},y_{2}))\Bigm{|}(x_{1},y_{1})\in E_{1},(x_{2},y_{2})\in E_{2}\right\},

(3.1)

and the constraint $\pi_{e}\subseteq(\Sigma_{1}\times\Sigma_{2})^{e}$ for each edge $e=((x_{1},x_{2}),(y_{1},y_{2}))\in E$ is defined as

\displaystyle\pi_{e}\triangleq\left\{((\alpha_{1},\alpha_{2}),(\beta_{1},\beta_{2}))\Bigm{|}(\alpha_{1},\beta_{1})\in\pi_{1,(x_{1},y_{1})}\text{ and }(\alpha_{2},\beta_{2})\in\pi_{2,(x_{2},y_{2})}\right\}.

(3.2)

The $\rho$ -fold parallel repetition of $G$ , denoted $G^{\otimes\rho}$ , for any positive integer $\rho\in\mathbb{N}$ is defined as

\displaystyle G^{\otimes\rho}\triangleq\underbrace{G\otimes\cdots\otimes G}_{\rho\text{ times}}.

(3.3)

The parallel repetition theorem due to Raz [Raz98] states that for every game $G$ with $\operatorname{\mathsf{val}}(G)\leqslant 1-\varepsilon<1$ , it holds that $\operatorname{\mathsf{val}}(G^{\otimes\rho})\leqslant(1-\overline{\varepsilon})^{\frac{\rho}{\log|\Sigma|}}$ , where $\overline{\varepsilon}>0$ depends only on the value of $\varepsilon$ .

We can think of a reconfiguration analogue for parallel repetition. More precisely, for two labelings $\psi_{1}\colon(X_{1}\cup Y_{1})\to\Sigma_{1}$ for $G_{1}=(X_{1},Y_{1},E_{1},\Sigma_{1},\Pi_{1})$ and $\psi_{2}\colon(X_{2}\cup Y_{2})\to\Sigma_{2}$ for $G_{2}=(X_{2},Y_{2},E_{2},\Sigma_{2},\Pi_{2})$ , the product labeling of $\psi_{1}$ and $\psi_{2}$ , denoted $\psi_{1}\otimes\psi_{2}$ , is defined as a labeling $\psi\colon(X_{1}\times X_{2})\cup(Y_{1}\times Y_{2})\to\Sigma_{1}\times\Sigma_{2}$ such that

\displaystyle\psi(v_{1},v_{2})\triangleq(\psi_{1}(v_{1}),\psi_{2}(v_{2}))\text{ for all }(v_{1},v_{2})\in(X_{1}\times X_{2})\cup(Y_{1}\times Y_{2}).

(3.4)

We write $\psi^{\otimes\rho}$ for denoting $\underbrace{\psi\otimes\cdots\otimes\psi}_{\rho\text{ times}}.$ It is easy to see that $\operatorname{\mathsf{val}}_{G}(\psi_{\mathsf{s}}\leftrightsquigarrow\psi_{\mathsf{t}})=1$ implies $\operatorname{\mathsf{val}}_{G^{\otimes\rho}}(\psi_{\mathsf{s}}^{\otimes\rho}\leftrightsquigarrow\psi_{\mathsf{t}}^{\otimes\rho})=1$ . So, given that $\operatorname{\mathsf{val}}_{G}(\psi_{\mathsf{s}}\leftrightsquigarrow\psi_{\mathsf{t}})<1$ , does the value of the $\rho$ -fold parallel repetition of a game decreases as the increase of $\rho$ ? Unfortunately, the answer is negative:

Observation 3.2.

Let $G$ be a satisfiable game, and $\psi_{\mathsf{s}}$ and $\psi_{\mathsf{t}}$ be its two satisfying labelings. Then, for every positive integer $\rho\in\mathbb{N}$ , it holds that

\displaystyle\operatorname{\mathsf{val}}_{G^{\otimes\rho}}(\psi_{\mathsf{s}}^{\otimes\rho}\leftrightsquigarrow\psi_{\mathsf{t}}^{\otimes\rho})\geqslant\operatorname{\mathsf{val}}_{G}(\psi_{\mathsf{s}}\leftrightsquigarrow\psi_{\mathsf{t}}).

(3.5)

Proof.

Let $G=(X,Y,E,\Sigma,\Pi)$ be a satisfiable game. Suppose that we are given a reconfiguration sequence $\mathbf{\bm{\uppsi}}=\langle\psi^{(0)}\ldots,\psi^{(\ell)}\rangle$ from $\psi_{\mathsf{s}}$ to $\psi_{\mathsf{t}}$ such that $\operatorname{\mathsf{val}}_{G}(\mathbf{\bm{\uppsi}})=\operatorname{\mathsf{val}}_{G}(\psi_{\mathsf{s}}\leftrightsquigarrow\psi_{\mathsf{t}})$ . We will show

\displaystyle\operatorname{\mathsf{val}}_{G^{\otimes\rho}}(\psi_{\mathsf{s}}^{\otimes k}\otimes\psi_{\mathsf{t}}^{\otimes\rho-k}\leftrightsquigarrow\psi_{\mathsf{s}}^{\otimes k-1}\otimes\psi_{\mathsf{t}}^{\otimes\rho-k+1})\geqslant\operatorname{\mathsf{val}}_{G}(\psi_{\mathsf{s}}\leftrightsquigarrow\psi_{\mathsf{t}})\text{ for all }k\in[\rho].

(3.6)

To this end, for each $i\in[\ell]$ , we bound

\displaystyle\operatorname{\mathsf{val}}_{G^{\otimes\rho}}(\psi_{\mathsf{s}}^{\otimes k-1}\otimes\psi^{(i-1)}\otimes\psi_{\mathsf{t}}^{\otimes\rho-k}\leftrightsquigarrow\psi_{\mathsf{s}}^{\otimes k-1}\otimes\psi^{(i)}\otimes\psi_{\mathsf{t}}^{\otimes\rho-k}).

(3.7)

Fix $k\in[\rho]$ and $i\in[\ell]$ . We assume that $\psi^{(i-1)}$ and $\psi^{(i)}$ differ in some $x^{\star}\in X$ ; the case that they differ in some $y^{\star}\in Y$ can be shown similarly. Construct then a reconfiguration sequence $\mathbf{\bm{\uppsi}}^{(k,i)}$ from $\psi_{\mathsf{s}}^{\otimes k-1}\otimes\psi^{(i-1)}\otimes\psi_{\mathsf{t}}^{\otimes\rho-k}$ to $\psi_{\mathsf{s}}^{\otimes k-1}\otimes\psi^{(i)}\otimes\psi_{\mathsf{t}}^{\otimes\rho-k}$ by changing the value of a vertex of $G^{\otimes\ell}$ if its value is different between the two assignments. Obviously, it holds that

\displaystyle\operatorname{\mathsf{val}}_{G^{\otimes\rho}}(\psi_{\mathsf{s}}^{\otimes k-1}\otimes\psi^{(i-1)}\otimes\psi_{\mathsf{t}}^{\otimes\rho-k}\leftrightsquigarrow\psi_{\mathsf{s}}^{\otimes k-1}\otimes\psi^{(i)}\otimes\psi_{\mathsf{t}}^{\otimes\rho-k})\geqslant\operatorname{\mathsf{val}}_{G^{\otimes\ell}}(\mathbf{\bm{\uppsi}}^{(k,i)}).

(3.8)

Observe now that $\psi_{\mathsf{s}}^{\otimes k-1}\otimes\psi^{(i-1)}\otimes\psi_{\mathsf{t}}^{\otimes\rho-k}$ and $\psi_{\mathsf{s}}^{\otimes k-1}\otimes\psi^{(i)}\otimes\psi_{\mathsf{t}}^{\otimes\rho-k}$ differ on vertex $(x_{1},\ldots,x_{\rho})\in X^{\rho}$ if and only if $x_{k}=x^{\star}$ and agree with each other on any vertex $(y_{1},\ldots,y_{\rho})\in Y^{\rho}$ . Thus, for any assignment $\psi\in\mathbf{\bm{\uppsi}}^{(k,i)}$ ,

	$\displaystyle\psi(x_{1},\ldots,x_{\rho})$	$\displaystyle=(\psi_{\mathsf{s}}(x_{1}),\ldots,\psi_{\mathsf{s}}(x_{k-1}),\left\{\begin{array}[]{c}\psi^{(i-1)}(x_{k})\\ \text{or}\\ \psi^{(i)}(x_{k})\end{array}\right\},\psi_{\mathsf{t}}(x_{k+1}),\ldots,\psi_{\mathsf{t}}(x_{\rho}))$
	$\displaystyle\psi(y_{1},\ldots,y_{\rho})$	$\displaystyle=(\psi_{\mathsf{s}}(y_{1}),\ldots,\psi_{\mathsf{s}}(y_{k-1}),\psi^{(i-1)}(y_{k}),\psi_{\mathsf{t}}(y_{k+1}),\ldots,\psi_{\mathsf{t}}(y_{\rho}))$
		$\displaystyle=(\psi_{\mathsf{s}}(y_{1}),\ldots,\psi_{\mathsf{s}}(y_{k-1}),\psi^{(i)}(y_{k}),\psi_{\mathsf{t}}(y_{k+1}),\ldots,\psi_{\mathsf{t}}(y_{\rho})).$

for all $(x_{1},\ldots,x_{\rho})\in X^{\rho}$ and $(y_{1},\ldots,y_{\rho})\in Y^{\rho}$ . By abuse of notation, denoting $\psi(x,y)=(\psi(x),\psi(y))$ for assignment $\psi$ and edge $(x,y)$ ; we bound the value of $\mathbf{\bm{\uppsi}}^{(k,i)}$ as follows:

		$\displaystyle\operatorname{\mathsf{val}}_{G^{\otimes\ell}}(\mathbf{\bm{\uppsi}}^{(k,i)})$
	$\displaystyle\geqslant{}$	$\displaystyle\frac{1}{\|E(G^{\otimes\rho})\|}\sum_{x_{1},\ldots,x_{\rho}\in X}$
		$\displaystyle\min\left\{\sum_{\begin{subarray}{c}y_{1},\ldots,y_{\rho}\in Y:\\ (x_{j},y_{j})\in E\forall j\end{subarray}}\Bigl{\llbracket}\bigwedge_{1\leqslant j\leqslant k-1}\psi_{\mathsf{s}}(x_{j},y_{j})\in\pi_{(x_{j},y_{j})}\Bigr{\rrbracket}\cdot\Bigl{\llbracket}\psi^{(i-1)}(x_{k},y_{k})\in\pi_{(x_{k},y_{k})}\Bigr{\rrbracket}\cdot\Bigl{\llbracket}\bigwedge_{k+1\leqslant j\leqslant\ell}\psi_{\mathsf{t}}(x_{j},y_{j})\in\pi_{(x_{j},y_{j})}\Bigr{\rrbracket},\right.$
		$\displaystyle\left.\sum_{\begin{subarray}{c}y_{1},\ldots,y_{\rho}\in Y:\\ (x_{j},y_{j})\in E\forall j\end{subarray}}\Bigl{\llbracket}\bigwedge_{1\leqslant j\leqslant k-1}\psi_{\mathsf{s}}(x_{j},y_{j})\in\pi_{(x_{j},y_{j})}\Bigr{\rrbracket}\cdot\Bigl{\llbracket}\psi^{(i)}(x_{k},y_{k})\in\pi_{(x_{k},y_{k})}\Bigr{\rrbracket}\cdot\Bigl{\llbracket}\bigwedge_{k+1\leqslant j\leqslant\ell}\psi_{\mathsf{t}}(x_{j},y_{j})\in\pi_{(x_{j},y_{j})}\Bigr{\rrbracket}\right\}$

Since $\psi_{\mathsf{s}}(x_{j},y_{j})$ satisfies $(x_{j},y_{j})$ if $1\leqslant j\leqslant k-1$ and $\psi_{\mathsf{t}}(x_{j},y_{j})$ satisfies $(x_{j},y_{j})$ if $k+1\leqslant j\leqslant\ell$ , we further have

		$\displaystyle\operatorname{\mathsf{val}}_{G^{\otimes\ell}}(\mathbf{\bm{\uppsi}}^{(k,i)})$
	$\displaystyle\geqslant{}$	$\displaystyle\frac{1}{\|E(G^{\otimes\rho})\|}\sum_{x_{1},\ldots,x_{\rho}}\min\left\{\sum_{y_{1},\ldots,y_{\rho}}\left\llbracket\psi^{(i-1)}(x_{k},y_{k})\in\pi_{(x_{k},y_{k})}\right\rrbracket,\sum_{y_{1},\ldots,y_{\rho}}\left\llbracket\psi^{(i)}(x_{k},y_{k})\in\pi_{(x_{k},y_{k})}\right\rrbracket\right\}$
	$\displaystyle={}$	$\displaystyle\frac{1}{\|E(G^{\otimes\rho})\|}\sum_{e_{1},\ldots,e_{k-1},e_{k+1},\ldots,e_{\rho}\in E}$
		$\displaystyle\sum_{x_{k}}\min\left\{\sum_{y_{k}:(x_{k},y_{k})\in E}\left\llbracket\psi^{(i-1)}(x_{k},y_{k})\in\pi_{(x_{k},y_{k})}\right\rrbracket,\sum_{y_{k}:(x_{k},y_{k})\in E}\left\llbracket\psi^{(i)}(x_{k},y_{k})\in\pi_{(x_{k},y_{k})}\right\rrbracket\right\}$
	$\displaystyle={}$	$\displaystyle\frac{1}{\|E\|}\sum_{x}\min\left\{\sum_{y:(x,y)\in E}\left\llbracket\psi^{(i-1)}(x,y)\in\pi_{(x,y)}\right\rrbracket,\sum_{y:(x,y)\in E}\left\llbracket\psi^{(i)}(x,y)\in\pi_{(x,y)}\right\rrbracket\right\}$
	$\displaystyle={}$	$\displaystyle\min\Bigl{\{}\operatorname{\mathsf{val}}_{G}(\psi^{(i-1)}),\operatorname{\mathsf{val}}_{G}(\psi^{(i)})\Bigr{\}}.$

Concatenating reconfiguration sequences $\mathbf{\bm{\uppsi}}^{(k,i)}$ for all $i\in[\ell]$ , we have

\displaystyle\begin{aligned} &\operatorname{\mathsf{val}}_{G^{\otimes\rho}}(\psi_{\mathsf{s}}^{\otimes k}\otimes\psi_{\mathsf{t}}^{\otimes\rho-k}\leftrightsquigarrow\psi_{\mathsf{s}}^{\otimes k-1}\otimes\psi_{\mathsf{t}}^{\otimes\rho-k+1})\\ &\geqslant\min_{1\leqslant i\leqslant\ell}\operatorname{\mathsf{val}}_{G^{\otimes\rho}}(\psi_{\mathsf{s}}^{\otimes k-1}\otimes\psi^{(i-1)}\otimes\psi_{\mathsf{t}}^{\otimes\rho-k}\leftrightsquigarrow\psi_{\mathsf{s}}^{\otimes k-1}\otimes\psi^{(i)}\otimes\psi_{\mathsf{t}}^{\otimes\rho-k})\\ &\geqslant\min_{0\leqslant i\leqslant\ell}\operatorname{\mathsf{val}}_{G}(\psi^{(i)})\\ &=\operatorname{\mathsf{val}}_{G}(\mathbf{\bm{\uppsi}})=\operatorname{\mathsf{val}}_{G}(\psi_{\mathsf{s}}\leftrightsquigarrow\psi_{\mathsf{t}}).\end{aligned}

(3.9)

Consequently, we obtain

\displaystyle\operatorname{\mathsf{val}}_{G^{\otimes\rho}}(\psi_{\mathsf{s}}^{\otimes\rho}\leftrightsquigarrow\psi_{\mathsf{t}}^{\otimes\rho})\geqslant\min_{k\in[\rho]}\operatorname{\mathsf{val}}_{G^{\otimes\rho}}(\psi_{\mathsf{s}}^{\otimes k}\otimes\psi_{\mathsf{t}}^{\otimes\rho-k}\leftrightsquigarrow\psi_{\mathsf{s}}^{\otimes k-1}\otimes\psi_{\mathsf{t}}^{\otimes\rho-k+1})\geqslant\operatorname{\mathsf{val}}_{G}(\psi_{\mathsf{s}}\leftrightsquigarrow\psi_{\mathsf{t}}),

(3.10)

completing the proof. ∎

4 Polynomial-time Reconfiguration for Projection Games

We finally present a simple polynomial-time algorithm that decides reconfigurability between a pair of satisfying labelings for a projection game.

Theorem 4.1.

For a satisfiable projection game $G=(X,Y,E,\Sigma,\Pi)$ and its two satisfying labelings $\psi_{\mathsf{s}}$ and $\psi_{\mathsf{t}}$ , we can decide in polynomial time if there is a reconfiguration sequence from $\psi_{\mathsf{s}}$ to $\psi_{\mathsf{t}}$ of satisfying labelings for $G$ .

Proof.

Since each connected component of $G$ can be processed independently, we only consider the case that $G$ is connected. If $G$ consists of a single vertex (i.e., $X$ or $Y$ is empty), the answer is always “reconfigurable” as it has no edges; thus we can safely assume that $X,Y\neq\emptyset$ . We show that $\psi_{\mathsf{s}}$ and $\psi_{\mathsf{t}}$ are reconfigurable to each other if and only if $\psi_{\mathsf{s}}$ and $\psi_{\mathsf{t}}$ agree on $X$ .

We first show the only-if direction. Suppose that $\psi_{\mathsf{s}}(x)\neq\psi_{\mathsf{t}}(x)$ for some $x\in X$ . Starting from $\psi_{\mathsf{s}}$ , changing the value of $x$ from $\psi_{\mathsf{s}}(x)$ to any other value must violate edges $e=(x,y)$ incident to $x$ since the value of $y$ should be mapped to $\psi_{\mathsf{s}}(x)$ via $\pi_{e}$ , as claimed.

We then show the if direction. Suppose that $\psi_{\mathsf{s}}(x)=\psi_{\mathsf{t}}(x)$ for every $x\in X$ . Then, it holds that $\pi_{e}(\psi_{\mathsf{s}}(y))=\psi_{\mathsf{s}}(x)=\psi_{\mathsf{t}}(x)=\pi_{e}(\psi_{\mathsf{t}}(y))$ for every edge $e=(x,y)\in E$ . We can thus obtain a transformation from $\psi_{\mathsf{s}}$ to $\psi_{\mathsf{t}}$ without breaking any constraint, by changing the value of each vertex $y$ of $Y$ from $\psi_{\mathsf{s}}(y)$ to $\psi_{\mathsf{t}}(y)$ one by one, as desired. ∎

References

[ABSS97] Sanjeev Arora, László Babai, Jacques Stern, and Z. Sweedyk. The hardness of approximate optima in lattices, codes, and systems of linear equations. J. Comput. Syst. Sci., 54(2):317–331, 1997.
[ALM⁺98] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3):501–555, 1998.
[AS98] Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70–122, 1998.
[Fei98] Uriel Feige. A threshold of $\ln n$ for approximating set cover. J. ACM, 45(4):634–652, 1998.
[GKMP09] Parikshit Gopalan, Phokion G. Kolaitis, Elitza Maneva, and Christos H. Papadimitriou. The connectivity of Boolean satisfiability: Computational and structural dichotomies. SIAM J. Comput., 38(6):2330–2355, 2009.
[Hås99] Johan Håstad. Clique is hard to approximate within $n^{1-\varepsilon}$ . Acta Math., 182:105–142, 1999.
[Hås01] Johan Håstad. Some optimal inapproximability results. J. ACM, 48(4):798–859, 2001.
[IDH⁺11] Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno. On the complexity of reconfiguration problems. Theor. Comput. Sci., 412(12-14):1054–1065, 2011.
[KO03] Daniela Kühn and Deryk Osthus. Partitions of graphs with high minimum degree or connectivity. J. Comb. Theory. Ser. B, 88(1):29–43, 2003.
[Nis18] Naomi Nishimura. Introduction to reconfiguration. Algorithms, 11(4):52, 2018.
[Ohs23] Naoto Ohsaka. Gap preserving reductions between reconfiguration problems. In STACS, pages 49:1–49:18, 2023.
[Raz98] Ran Raz. A parallel repetition theorem. SIAM J. Comput., 27(3):763–803, 1998.
[vdH13] Jan van den Heuvel. The complexity of change. In Surveys in Combinatorics 2013, volume 409, pages 127–160. Cambridge University Press, 2013.

On Approximate Reconfigurability of Label Cover

Abstract

1 Introduction

Background.

Our Results.

Preliminaries.

2 Nearly 14\frac{1}{4}-factor Approximation

Theorem 2.1.

Claim 2.2.

Proof.

Lemma 2.3.

Proof.

Proof of Theorem 2.1.

3 Parallel Repetition Does Not Amplify Gap

Definition 3.1.

Observation 3.2.

Proof.

4 Polynomial-time Reconfiguration for Projection Games

Theorem 4.1.

Proof.

References

2 Nearly $\frac{1}{4}$ -factor Approximation