On Approximate Reconfigurability of Label Cover
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912178715492352 |
|---|---|
| author | Ohsaka, Naoto |
| author_facet | Ohsaka, Naoto |
| contents | Given a two-prover game $G$ and its two satisfying labelings $ψ_\mathsf{ini}$ and $ψ_\mathsf{tar}$, the Label Cover Reconfiguration problem asks whether $ψ_\mathsf{ini}$ can be transformed into $ψ_\mathsf{tar}$ by repeatedly changing the label of a single vertex while preserving any intermediate labeling satisfying $G$. We consider its optimization version by relaxing the feasibility of labelings, referred to as Maxmin Label Cover Reconfiguration: We are allowed to pass through any non-satisfying labelings, but required to maximize the ``soundness error,'' which is defined as the minimum fraction of satisfied edges during transformation from $ψ_\mathsf{ini}$ to $ψ_\mathsf{tar}$. Since the parallel repetition theorem of Raz (SIAM J. Comput., 1998), which implies $\mathbf{NP}$-hardness of approximating Label Cover within any constant factor, gives strong inapproximability results for many $\mathbf{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:
$\bullet$ Maxmin Label Cover Reconfiguration can be approximated within a factor of $\frac{1}{4} - o(1)$ for some restricted graph classes, including biregular graphs, balanced bipartite graphs with no isolated vertices, and superconstant average degree graphs.
$\bullet$ A ``naive'' parallel repetition of Maxmin Label Cover Reconfiguration does not decrease the soundness error for every two-prover game.
$\bullet$ Label Cover Reconfiguration on projection games can be decided in polynomial time.
Our results suggest that a reconfiguration analogue of the parallel repetition theorem is unlikely. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_08746 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On Approximate Reconfigurability of Label Cover Ohsaka, Naoto Discrete Mathematics Computational Complexity Data Structures and Algorithms Given a two-prover game $G$ and its two satisfying labelings $ψ_\mathsf{ini}$ and $ψ_\mathsf{tar}$, the Label Cover Reconfiguration problem asks whether $ψ_\mathsf{ini}$ can be transformed into $ψ_\mathsf{tar}$ by repeatedly changing the label of a single vertex while preserving any intermediate labeling satisfying $G$. We consider its optimization version by relaxing the feasibility of labelings, referred to as Maxmin Label Cover Reconfiguration: We are allowed to pass through any non-satisfying labelings, but required to maximize the ``soundness error,'' which is defined as the minimum fraction of satisfied edges during transformation from $ψ_\mathsf{ini}$ to $ψ_\mathsf{tar}$. Since the parallel repetition theorem of Raz (SIAM J. Comput., 1998), which implies $\mathbf{NP}$-hardness of approximating Label Cover within any constant factor, gives strong inapproximability results for many $\mathbf{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: $\bullet$ Maxmin Label Cover Reconfiguration can be approximated within a factor of $\frac{1}{4} - o(1)$ for some restricted graph classes, including biregular graphs, balanced bipartite graphs with no isolated vertices, and superconstant average degree graphs. $\bullet$ A ``naive'' parallel repetition of Maxmin Label Cover Reconfiguration does not decrease the soundness error for every two-prover game. $\bullet$ Label Cover Reconfiguration on projection games can be decided in polynomial time. Our results suggest that a reconfiguration analogue of the parallel repetition theorem is unlikely. |
| title | On Approximate Reconfigurability of Label Cover |
| topic | Discrete Mathematics Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2304.08746 |