La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Open Access
Finding a Reconfiguration Sequence between Longest Increasing Subsequences
Open Access
Recherche d'une séquence de reconfiguration entre les sous-séquences croissantes les plus longues

Yuuki AOIKE, Masashi KIYOMI, Yasuaki KOBAYASHI, Yota OTACHI

  • Vues en texte intégral

    318

  • Citer
  • Free PDF (78.8KB)

Résumé:

Dans cette note, nous considérons le problème de trouver une transformation étape par étape entre deux sous-séquences croissantes les plus longues d'une séquence, à savoir RECONFIGURATION DE SOUS-SÉQUENCE CROISSANTE LA PLUS LONGUE. Nous donnons un algorithme en temps polynomial pour décider s'il existe une séquence de reconfiguration entre deux sous-séquences croissantes les plus longues dans une séquence. Ceci implique que RECONFIGURATION INDÉPENDANTE DES ENSEMBLES et à la JETON COULISSANT sont résolubles en temps polynomial sur des graphes de permutation, à condition que les deux ensembles indépendants d'entrée soient les plus grands parmi tous les ensembles indépendants du graphe d'entrée. Nous considérons également un cas particulier, où le graphe de permutation sous-jacent d’une séquence d’entrée est biparti. Dans ce cas, nous donnons un algorithme en temps polynomial pour trouver la séquence de reconfiguration la plus courte (si elle existe).

Publication
IEICE TRANSACTIONS on Information Vol.E107-D No.4 pp.559-563
Date de publication
2024/04/01
Publicisé
2023/12/11
ISSN en ligne
1745-1361
DOI
10.1587/transinf.2023EDL8067
Type de manuscrit
LETTER
Catégories
Fondamentaux des Systèmes d'Information

1. Introduction

Pour un entier non négatif \(n\), nous définissons \([n] = \{1, 2, \ldots, n\}\). Laisse moi \(A = (a_i)_{i = 1, 2, \ldots, n}\) être une séquence d’entiers distincts compris entre 1 et \(n\). Nous disons que \(I \subseteq [n]\) is réalisable (Pour \(A\)) si \(a_i < a_j\) XNUMX \(i, j \in I\) avec \(i < j\). En d'autres termes, \(I\) est l’ensemble des indices d’une sous-suite croissante de \(A\). A ensemble maximal réalisable (Pour \(A\)) est un ensemble réalisable \(I\) XNUMX \(A\) tel qu'il n'y a pas d'ensemble réalisable (pour \(A\)) de cardinalité strictement supérieure à \(I\). Le problème du calcul d’un ensemble maximum réalisable d’une séquence donnée \(A\), aussi connu sous le nom Sous-séquence croissante la plus longue, est un exemple typique qui peut être résolu en temps polynomial avec une programmation dynamique [1].

Dans cette note, nous considérons la variante de reconfiguration de Sous-séquence croissante la plus longue, défini comme suit. Étant donné une séquence de \(n\) entiers distincts \(A\) et (pas nécessairement maximum) deux ensembles réalisables \(I\) et à la \(J\) avec \(|I| = |J|\), le but est de déterminer s'il existe une séquence d'ensembles réalisables \(I_0, I_1, \ldots, I_\ell\) tel que \(I_0 = I\), \(I_\ell = J\), Et pour \(1 \le i \le \ell\), \(I_{i}\) est obtenu à partir de \(I_{i-1}\) en ajoutant simultanément un élément \(j \notin I_{i-1}\) et enlever \(k \in I_{i-1}\) (c'est à dire, \(I_{i} = (I_{i-1} \cup \{j\}) \setminus \{k\}\)). Nous appelons ce problème Augmentation de la reconfiguration des sous-séquences et une telle séquence une séquence de reconfiguration entre \(I\) et à la \(J\). Si deux ensembles d’entrées constituent les ensembles maximaux réalisables pour \(A\), nous appelons particulièrement le problème Reconfiguration de sous-séquence croissante la plus longue. Dans cet article, nous donnons un algorithme en temps polynomial pour Reconfiguration de sous-séquence croissante la plus longue.

Théorème 1. Reconfiguration de sous-séquence croissante la plus longue peut être résolu en temps polynomial.

Augmentation de la reconfiguration des sous-séquences peut être considéré comme un cas particulier d'un problème de reconfiguration bien étudié, appelé Reconfiguration d'ensemble indépendante. Étant donné un graphique \(G = (V, E)\) et deux ensembles indépendants \(I, J\) of \(G\) avec \(|I| = |J|\), Reconfiguration d'ensemble indépendante demande s'il existe une séquence d'ensembles indépendants \(I_0, I_1, \ldots, I_\ell\) tel que \(I_0 = I\), \(I_\ell = J\), Et pour \(1 \le i \le \ell\), \(I_{i} \setminus I_{i - 1} = \{v\}\) et à la \(I_{i - 1} \setminus I_{i} = \{u\}\) pour certains \(u, v \in V\). Augmentation de la reconfiguration des sous-séquences correspond à Reconfiguration d'ensemble indépendante sur les graphes de permutations : un graphe non orienté \(G = (V, E)\) avec \(V = [n]\) est appelé un graphique de permutation s'il y a une permutation \(\pi\colon [n] \to [n]\) tel que pour \(1 \le i < j \le n\), \(\pi(i) > \pi(j)\) si et seulement si \(\{i, j\} \in E\). Observez que pour \(I \subseteq V\), \(I\) est un ensemble indépendant du graphe de permutation \(G\) si et seulement si \(I\) est un ensemble réalisable pour \(A = (\pi(i))_{i = 1, 2, \ldots, n}\). Ainsi, notre problème, Augmentation de la reconfiguration des sous-séquences, est équivalent à Reconfiguration d'ensemble indépendante sur les graphiques de permutation. Jeton coulissant est une variante de Reconfiguration d'ensemble indépendante, où deux sommets \(u, v\) dans la définition ci-dessus doivent être adjacents dans \(G\). Il est facile de voir que si \(I\) et à la \(J\) sont des ensembles indépendants maximaux de \(G\), ces deux problèmes sont équivalents.

Corollaire 1. Reconfiguration d'ensemble indépendante et à la Jeton coulissant peut être résolu en temps polynomial, à condition que le graphe d'entrée \(G\) est un graphe de permutation et deux ensembles \(I\) et à la \(J\) sont des ensembles indépendants maximaux de \(G\).

Cela résout un cas particulier de question ouverte posée par Briański et al. [2], où ils demandent un algorithme en temps polynomial pour Jeton coulissant sur les graphiques de permutation.

La perspective de la théorie des graphes de Reconfiguration de sous-séquence croissante la plus longue donne une autre conséquence intéressante de la recherche d'un le plus court séquence de reconfiguration entre des ensembles indépendants maximum sur des graphes de permutation bipartites. Pour toute séquence de reconfiguration \((I_0, I_1, \ldots, I_\ell)\), on a \(\ell \ge |I_0 \setminus I_\ell|\), car nous pouvons supprimer au plus un élément de \(I_0 \setminus I_\ell\) en une seule étape. Pour les graphes de permutation bipartis, on peut toujours trouver une séquence de reconfiguration entre des ensembles indépendants maximaux \(I\) et à la \(J\) avec longueur \(\ell = |I \setminus J|\) s'il existe une séquence de reconfiguration entre eux.

Théorème 2. Laisser nous \(G\) être un graphe de permutation biparti et laisser \(I\) et à la \(J\) être des ensembles indépendants maximaux de \(G\). Supposons qu'il y ait une séquence de reconfiguration entre \(I\) et à la \(J\). Ensuite, il y a une séquence de reconfiguration de longueur \(|I \setminus J|\) jusqu'à XNUMX fois \(I\) et à la \(J\).

La preuve du théorème 2 implique un algorithme en temps polynomial pour la « variante de séquence la plus courte » de Reconfiguration de sous-séquence croissante la plus longue lorsque le graphe de permutation sous-jacent d'une séquence d'entrée \(A\) est limité à être bipartite.

Reconfiguration d'ensemble indépendante et à la Jeton coulissant sont tous deux connus pour être PSPACE-complets [3]-[6] et étudiés sur de nombreuses classes de graphes. Reconfiguration d'ensemble indépendante est résoluble en temps polynomial sur les graphes libres à trous pairs [6] et les cographes [7], [8], alors qu'il est NP-complet sur les graphes bipartis [9]. Jeton coulissant est résoluble en temps polynomial sur les cographes [6], les graphes de permutation bipartis [10] et les graphes d'intervalles [2], [11], tandis qu'il est PSPACE-complet sur les graphes divisés [3] et les graphes bipartis [9]. Le résultat de [10] ne donne pas le théorème 2 puisque leur algorithme en temps polynomial peut fournir une séquence de reconfiguration non la plus courte sur les graphes de permutation bipartis. Nous soulignons particulièrement que les deux problèmes de reconfiguration restent PSPACE-complets même si deux ensembles indépendants d'entrée sont des ensembles indépendants maximum du graphe d'entrée [4].

Comme mentionné ci-dessus, Reconfiguration d'ensemble indépendante peut être résolu en temps polynomial sur la classe des graphes libres à trous pairs. En fait, pour les graphes libres à trous pairs, Kami\(\acute{\mathrm{n}}\)ski et coll. [6] ont montré que chaque instance de Reconfiguration d'ensemble indépendante est une instance oui (en supposant que deux ensembles indépendants d'entrée ont la même cardinalité). Ce phénomène ne s'applique pas à la classe des graphes de permutation : l'instance constituée de \(G := K_{2, 2}\) avec deux classes de couleurs \(I\) et à la \(J\) est une non-instance, et \(G\) est bien un graphe de permutation, correspondant à la séquence \(A = (7,8,5,6)\)1. Aussi les deux \(I = \{1, 2\}\) et à la \(J = \{3, 4\}\) sont des ensembles indépendants maximaux de \(G\). Il n’est donc pas trivial de concevoir un algorithme en temps polynomial pour Reconfiguration de sous-séquence croissante la plus longue. Notre algorithme en temps polynomial exploite une propriété structurelle de l'ensemble des ensembles réalisables pour une séquence donnée \(A\).

2. Algorithme

Laisser nous \(A = (a_i)_{i = 1, 2, \ldots, n}\) être une séquence de \(n\) entiers distincts compris entre 1 et \(n\). Laisse moi \(V = [n]\) et laisser \(P = (V, \preceq_A)\) être une commande partielle sur \(V\) tel que pour \(i, j \in V\),

\[\begin{aligned} i \preceq_A j \iff (i = j) \lor (i < j \land a_i < a_j). \end{aligned}\]

Ensuite, un sous-ensemble de \([n]\) est réalisable pour \(A\) si et seulement s'il s'agit d'une chaîne de cet ordre partiel. De plus, d'après le théorème de Mirsky [12], la plus grande taille d'une chaîne de \(P\) est égal à la taille minimale d'une partition antichain de \(V\), et une telle partition peut être calculée en \(O(n \log n)\) temps par un algorithme de programmation dynamique standard pour le problème de sous-séquence croissante la plus longue (voir [13] par exemple).

Pour comprendre la structure d'une partition antichaîne minimale, nous utilisons une construction spécifique, appelée patience, tri [14], qui est brièvement décrit comme suit. Pour simplifier, on ajoute 0 à \(A\) as \(a_0 = 0\). Nous utilisons \(n + 1\) pieux \(P_0, P_1, \ldots, P_n\) qui sont initialement tous vides et mettent itérativement un entier \(a_i\) in \(A\) au sommet d'une des piles pour \(0 \le i \le n\) dans cet ordre. Pour chaque \(0 \le i \le n\), nous mettons \(a_i\) en haut de la pile « la plus à gauche » \(P_j\) tel que \(P_j\) est vide ou en haut de \(P_j\) est supérieure \(a_i\). Notons que les éléments supérieurs de toutes les piles non vides sont toujours triés par ordre croissant. Maintenant, laisse \(P_0, P_1, \ldots, P_n\) être les pieux obtenus en exécutant l’algorithme ci-dessus pour \(A\). Clairement, \(P_0\) contient seulement \(a_0\). Pour chaque pile \(P_i\), Observe ceci \(P_i\) est une antichaîne (par rapport à \(\preceq_A\)): Si \(a_i\) est placé en dessous \(a_j\) dans la pile, alors \(i < j\) et à la \(a_i > a_j\). Pour chaque \(1 \le i \le n\), Lorsque \(a_i\) est placé au sommet de \(P_k\) pour certains \(1 \le k \le n\), l'élément supérieur \(a_j\) of \(P_{k - 1}\) est plus petit que \(a_i\) (c'est à dire, \(a_j < a_i\)). Dans ce cas, on dit que \(a_j\) blocs \(a_i\) et à la \(a_i\) est bloqué par \(a_j\). Laisse moi \(k\) être le plus grand indice d'une pile non vide. Par définition, pour \(1 \le i \le n\), Chaque \(a_i\) a un élément unique \(a_j\) qui bloque \(a_i\). De plus, si \(a_i\) est bloqué par \(a_j\), on a \(a_j \preceq_A a_i\). Cela implique qu'il existe une chaîne (par rapport à \(\preceq_A\)) de taille \(k + 1\), ce qui correspond à un ensemble réalisable \(I\) XNUMX \(A\). Comme chacun \(P_i\) est une antichaîne, cette chaîne contient exactement un élément de \(P_i\) pour chaque \(0 \le i \le k\). Donc, \(I\) est un ensemble maximum réalisable pour \(A\). La construction de pieux ci-dessus implique en outre les observations suivantes.

Observation 1. Laisser nous \(I\) être un ensemble arbitraire de maximum réalisable pour \(A\).

  1. If \(a_v\) est placé en dessous \(a_u\) dans une pile \(P_i\), ensuite nous avons \(u > v\) et à la \(a_u < a_v\).
  2. Chaque pile \(P_i\) contient exactement un élément \(a_u\) avec \(u \in I\).
  3. Laisser nous \(u, v \in I\) tel que \(a_u \in P_i\) et à la \(a_v \in P_j\) XNUMX \(0 \le i < j \le k\). Ensuite nous avons \(u \preceq_A v\).

Preuves. La première affirmation découle de la construction de \(P_i\). La deuxième affirmation découle du fait que \(P_i\) est une antichaîne par rapport à \(\preceq_A\). Pour la troisième affirmation, il suffit de montrer que \(u < v\) (comme la faisabilité de \(I\) implique que \(a_u < a_v\)). Supposons par contradiction que \(u > v\). Quand \(a_u\) est placé au sommet de \(P_i\), l'élément supérieur d'une pile \(P_{j}\) est strictement plus grand que \(a_u\). Ceci et la première déclaration impliquent ensemble que \(a_u < a_v\), contredisant le fait que \(I\) Est faisable.\(\tag*{◻}\)

Maintenant, nous nous tournons vers Reconfiguration de sous-séquence croissante la plus longue. Laisse moi

\[\begin{aligned} \mathcal I = \{I \subseteq \{0\} \cup [n]: I \text{ is a maximum feasible set of } A\} \end{aligned}\]

et laisser \(P_0, P_1, \ldots, P_k\) être les piles non vides obtenues en appliquant l'algorithme ci-dessus à \(A = (a_i)_{i = 0, 1, \ldots, n}\) avec \(a_0 = 0\). L’observation suivante découle de (2) dans l’observation 1.

Observation 2. Laisser nous \(I, J \in \mathcal I\) tel que \(I \setminus J = \{u\}\) et à la \(J \setminus I = \{v\}\). Alors, \(a_u, a_v \in P_j\) pour certains \(0 \le j \le k\).

Notre algorithme pour Reconfiguration de sous-séquence croissante la plus longue est basé sur une certaine relation d’équivalence sur \(\mathcal I\). For \(I, J \in \mathcal I\), on note par \(I \vartriangleleft J\) if \(I \setminus J = \{u\}\) et à la \(J \setminus I = \{v\}\) tel que \(a_u\) est placé (strictement) en dessous \(a_v\) sur pile \(P_i\) pour certains \(1 \le i \le k\). Nous notons que ceci \(\vartriangleleft\) la relation n'est pas transitive : \(I \vartriangleleft I'\) et à la \(I' \vartriangleleft I''\) ne peut pas impliquer \(I \vartriangleleft I''\). For \(I \in \mathcal I\), une famille d'ensembles réalisables \(\mathcal M(I) \subseteq \mathcal I\) est défini inductivement comme suit : (1) \(\mathcal M(I)\) contient \(I\) et (2) pour chaque \(J \in \mathcal M(I)\), \(J' \vartriangleleft J\) implique \(J' \in \mathcal M(I)\). En d'autres termes, \(\mathcal M(I)\) est l'ensemble inférieur de \(I\) dans la fermeture transitive de \(\vartriangleleft\) in \(\mathcal I\). Par définition, pour \(I \in \mathcal I\), \(\mathcal M(J) \subsetneq \mathcal M(I)\) if \(J \in \mathcal M(I)\) avec \(J \neq I\). Nous disons que \(I \in \mathcal I\) is \(\vartriangleleft\)Minime si il n'y a pas \(J \in \mathcal I\) avec \(J \vartriangleleft I\).

Lemme 1. Laisser nous \(I, J, J' \in \mathcal I\) tel que \(J \vartriangleleft I\), \(J' \vartriangleleft I\) et \(J \neq J'\). Alors, au moins une des conditions suivantes est remplie : \(J' \vartriangleleft J\), \(J \vartriangleleft J'\), ou il y a \(J'' \in \mathcal I\) tel que \(J'' \vartriangleleft J\) et à la \(J'' \vartriangleleft J'\).

Preuves. Laisser nous \(I \setminus J = \{u\}\), \(J \setminus I = \{v\}\), \(I \setminus J' = \{u'\}\) et \(J' \setminus I = \{v'\}\). Si \(u\) et à la \(u'\) appartiennent à la même pile \(P_i\), par observation 2, \(v\) et à la \(v'\) appartiennent à la même pile \(P_i\). Cela implique soit \(J' \vartriangleleft J\) or \(J \vartriangleleft J'\). Supposons le contraire. Par observation 2, \(v\) et à la \(v'\) appartiennent à des tas distincts et donc \(v \neq v'\). Nous affirmons que \((J \setminus \{u'\}) \cup \{v'\}\) est un ensemble maximum réalisable, ce qui implique symétriquement que \((J' \setminus \{u\}) \cup \{v\}\) est également un ensemble maximum réalisable. Supposons par contradiction que \((J \setminus \{u'\}) \cup \{v'\}\) n'est pas un ensemble réalisable. Depuis \(J \setminus \{u'\}\) et à la \(J' = (I \setminus \{u'\}) \cup \{v'\}\) sont réalisables, \(v\) et à la \(v'\) sont l'unique couple incomparable par rapport à \(\preceq_A\) in \((J \setminus \{u'\}) \cup \{v'\}\). Nous supposons que \(a_v\) et à la \(a_{v'}\) sont contenus dans des tas \(P_i\) et à la \(P_j\) avec \(i < j\), respectivement. Comme \(v, u' \in J\), d'après l'observation 1, nous avons \(a_{v} < a_{u'}\). De plus, comme \(a_{v'}\) est placé en dessous \(a_{u'}\) in \(P_j\), on a \(a_{u'} < a_{v'}\) (par (1) dans l’observation 1). Ensemble, cela implique que \(a_{v} < a_{v'}\). Comme \(a_v\) est placé en dessous \(a_u\) in \(P_i\), on a \(v < u\) (par (1) dans l’observation 1). De plus, par (3) dans l’observation 1, \(u \preceq_A v'\) as \(u, v' \in J'\). Ainsi, nous avons \(v < v'\), contredisant l'hypothèse selon laquelle \(v\) et à la \(v'\) sont incomparables en ce qui concerne \(\preceq_A\).\(\tag*{◻}\)

Lemme 2. Pour \(I \in \mathcal I\), il y en a exactement un \(\vartriangleleft\)-mise en place minimale \(\mathcal M(I)\).

Preuves. On prouve le lemme par récurrence sur \(|\mathcal M(I)|\). Si \(|\mathcal M(I)| = 1\), puis \(I\) lui-même est l'unique \(\vartriangleleft\)-mise en place minimale \(\mathcal M(I)\). Supposer que \(\mathcal M(I)\) contient au moins deux ensembles. S'il y en a exactement un \(J \in \mathcal M(I)\) avec \(J \vartriangleleft I\), par l'hypothèse d'induction, \(\mathcal M(J) \subsetneq \mathcal M(I)\) offre une expérience unique grâce aux technologies \(\vartriangleleft\)-ensemble minimal, qui est aussi l'unique \(\vartriangleleft\)-mise en place minimale \(\mathcal M(I)\). Sinon il y en a deux \(J, J' \in \mathcal M(I)\) tel que \(J \vartriangleleft I\) et à la \(J' \vartriangleleft I\). D’après le lemme 1, au moins une des conditions suivantes est satisfaite : \(J' \vartriangleleft J\), \(J \vartriangleleft J'\), ou il y a \(J'' \in \mathcal I\) tel que \(J'' \vartriangleleft J\) et à la \(J'' \vartriangleleft J'\). Si \(J' \vartriangleleft J\), puis \(\mathcal M(J') \subseteq \mathcal M(J) \subsetneq \mathcal M(I)\). Par induction, les deux \(\mathcal M(J)\) et à la \(\mathcal M(J')\) avoir unique \(\vartriangleleft\)-ensembles minimaux, et comme \(\mathcal M(J') \subseteq \mathcal M(J)\), ces deux ensembles sont identiques. Le cas où \(J \vartriangleleft J'\) est symétrique. Supposons donc qu'il y ait \(J'' \in \mathcal I\) tel que \(J'' \vartriangleleft J\) et à la \(J'' \vartriangleleft J'\). Par induction, \(\mathcal M(J)\), \(\mathcal M(J')\) et \(\mathcal M(J'')\) avoir unique \(\vartriangleleft\)-ensembles minimaux. De même, comme \(\mathcal M(J'') \subseteq \mathcal M(J)\) et à la \(\mathcal M(J'') \subseteq \mathcal M(J')\), ces trois \(\vartriangleleft\)-les ensembles minimaux sont identiques, ce qui complète la preuve.\(\tag*{◻}\)

La preuve du lemme 2 implique immédiatement le corollaire suivant.

Corollaire 2. Pour \(I, J \in \mathcal I\) avec \(I \vartriangleleft J\), \(\vartriangleleft\)-ensembles minimaux de \(\mathcal M(I)\) et à la \(\mathcal M(J)\) sont identiques.

Nous définissons une relation d'équivalence sur \(\mathcal I\) basé sur \(\vartriangleleft\)-minimalité. D'après le lemme 2, le \(\vartriangleleft\)-mise en place minimale \(\mathcal M(I)\) est uniquement déterminé pour \(I \in \mathcal I\). On dit que deux ensembles maximum réalisables \(I\) et à la \(J\) \(\vartriangleleft\)-équivalent si le \(\vartriangleleft\)-mise en place minimale \(\mathcal M(I)\) est égal à celui dans \(\mathcal M(J)\). La clé de notre algorithme est le lemme suivant.

Lemme 3. Laisser nous \(I, J \in \mathcal I\). Ensuite, il y a une séquence de reconfiguration entre \(I\) et à la \(J\) si et seulement si \(I\) et à la \(J\) \(\vartriangleleft\)-équivalent.

Preuves. Supposons qu'il existe une séquence de reconfiguration \((I_0, I_1, \ldots, I_\ell)\) jusqu'à XNUMX fois \(I_0 = I\) et à la \(I_\ell = J\). Nous prouvons que tous les ensembles maximaux réalisables \(I_i\) appartiennent au même \(\vartriangleleft\)-classe d'équivalence. Par définition, soit \(I_{i} \vartriangleleft I_{i + 1}\) or \(I_{i + 1} \vartriangleleft I_{i}\), ce qui implique respectivement que \(\mathcal M(I_i) \subseteq \mathcal M(I_{i + 1})\) or \(\mathcal M(I_{i + 1}) \subseteq \mathcal M(I_{i})\). Par le corollaire 2, leur \(\vartriangleleft\)-les ensembles minimaux sont identiques, ce qui prouve la direction vers l'avant.

Supposer que \(I\) et à la \(J\) \(\vartriangleleft\)-équivalent. Ensuite il y a \(I' \in \mathcal M(I) \cap \mathcal M(J)\). Cela implique qu'il existe des séquences de reconfiguration entre \(I\) et à la \(I'\) et entre \(J\) et à la \(I'\). En concaténant ces séquences, on obtient une séquence de reconfiguration entre \(I\) et à la \(J\).\(\tag*{◻}\)

Notre algorithme est assez simple. Étant donné deux ensembles maximum réalisables \(I\) et à la \(J\), on calcule leur \(\vartriangleleft\)-ensembles minimaux \(I'\) et à la \(J'\), respectivement. D’après le lemme 3, il existe une séquence de reconfiguration entre \(I\) et à la \(J\) si et seulement si \(I' = J'\). À partir d'un ensemble maximum réalisable \(I\), nous pouvons calculer un unique \(\vartriangleleft\)-mise en place minimale \(\mathcal M(I)\) en temps polynomial par un algorithme glouton. D’où le théorème 1.

3. Affaire bipartite

Avant de prouver le théorème 2, nous aimerions mentionner que la bipartité dans le théorème 2 est cruciale, c'est-à-dire Reconfiguration de sous-séquence croissante la plus longue n'admet pas de séquence de reconfiguration de longueur \(|I \setminus J|\) en général. Considérons une instance composée de \(A = (15, 11, 16, 13, 17, 12, 14)\)2, \(I = \{1,3,5\}\) et \(J = \{2,6,7\}\). Cette instance nécessite quatre étapes pour se transformer \(I\) développement \(J\): \(I_0 = \{1, 3, 5\} = I\), \(I_1 = \{2,3,5\}\), \(I_2 = \{2,4,5\}\), \(I_3 = \{2,4,7\}\), \(I_4 = \{2,6,7\} = J\), tandis que \(|I\setminus J| = 3\).

Laisser nous \((A = (a_i)_{i=1,2,\ldots, n}, I, J)\) être un exemple de Reconfiguration de sous-séquence croissante la plus longue tel que le graphe de permutation sous-jacent \(G_A\) of \(A\) est bipartite. Dans ce qui suit, nous ne pourrons pas distinguer les éléments de \(A\) à partir de leurs indices et se réfèrent ensuite également aux éléments de \(A\) comme les sommets de \(G_A\). Laisse moi \(P_1, P_2, \ldots, P_k\) être les tas pour \(A\) défini dans la section précédente. D'après (1) dans l'observation 2, chaque paire d'indices d'éléments dans une pile est incomparable par rapport à \(\preceq_A\). Cela implique qu'ils sont adjacents dans le graphe de permutation \(G_A\). Ainsi, chaque pile contient au plus deux éléments, sinon \(G_A\) contient un triangle. Une pile \(P_t\) est appelé un pile mélangée s'il contient exactement deux éléments \(a_{i}\) et à la \(a_{j}\) avec \(i \in I\) et à la \(j \in J\). Notez que, pour une telle pile mélangée \(P_t\), À la fois \(j \notin I\) et à la \(i \notin J\) prise. Une paire de deux pieux mélangés est appelée un paire interdite si les quatre sommets correspondant à deux pieux mixtes induisent un cycle de longueur 4 en \(G_A\). Il est facile de constater que \((A, I, J)\) n'est pas une instance s'il a une paire interdite.

Un tas mélangé \(P_i\) est appelé le plus à gauche pile mélangée si pas de pile \(P_j\) avec \(j < i\) est mixte. Le lemme suivant est une clé pour prouver le théorème 2.

Lemme 4. Supposer que \((A, I, J)\) n'a pas de paires interdites. Laisser \(a_i, a_j\) être les éléments de la pile mélangée la plus à gauche \(P_{t}\) avec \(i \in I\) et à la \(j \in J\). Ensuite, au moins un des \((I \setminus \{i\}) \cup \{j\}\) or \((J \setminus \{j\}) \cup \{i\}\) Est faisable.

Preuves. Supposons que les deux \(I' = (I \setminus \{i\}) \cup \{j\}\) et à la \(J' = (J \setminus \{j\}) \cup \{i\}\) ne sont pas réalisables. Comme \(I'\) n'est pas réalisable, il y a \(i' \in I \setminus \{i\}\) qui est adjacent à \(j\) in \(G_A\). Laisse moi \(P_{t'}\) être la pile contenant \(a_{i'}\). Depuis \(j \in J\), pile \(P_{t'}\) a un élément \(a_{j'}\) avec \(j' \in J\), ce qui implique que \(P_{t'}\) est une pile mélangée avec \(t < t'\). Symétriquement, comme \(J'\) n'est pas réalisable, il y a une pile mélangée \(P_{t''}\) avec \(t < t''\) qui a un élément \(a_{j''}\) avec \(j'' \in J \setminus \{j\}\) adjacente à \(i\) in \(G_A\). Si \(t' = t''\), la paire \(P_t\) et à la \(P_t'\) forme une paire interdite, contredisant l’hypothèse. Supposons, sans perte de généralité, que \(t < t' < t''\). Puisqu'il y a des bords entre \(j\) et à la \(i'\) et entre \(i\) et à la \(j''\), on a \(a_j > a_{i'}\) et à la \(a_i > a_{j''}\). Comme \(j, j'' \in J\), on a \(a_{j} < a_{j''}\). Ainsi, nous avons \(a_{i'} < a_j < a_{j''} < a_i\), en contradiction avec le fait \(a_{i} < a_{i'}\) as \(i, i' \in I\).\(\tag*{◻}\)

Il convient de mentionner que le lemme 4 est similaire au lemme 6 dans [6], où ils ont montré que si \(G\) est pair sans trous, le sous-graphe de \(G\) induit par \(I \mathbin{\triangle} J = (I \setminus J) \cup (J \setminus I)\) n'a pas de cycles et alors il existe toujours une séquence de reconfiguration entre deux ensembles indépendants \(I\) et à la \(J\) avec la même cardinalité. Cependant, le sous-graphe de \(G_A\) induit par \(I \mathbin{\triangle} J\) peut contenir un cycle, même s'il exclut les paires interdites. Voir la figure 1 pour une illustration.

Fig. 1  La figure représente le graphe de permutation bipartite \(G_A\) correspondant à la séquence \(A=(10,7,11,8,12,9)\) avec \(I = \{1, 3, 5\}\) et à la \(J = \{2, 4, 6\}\).

D'après le lemme 4, au moins un des \((I \setminus \{i\}) \cup \{j\}\) or \((J \setminus \{j\}) \cup \{i\}\), dire \(I' = (I \setminus \{i\}) \cup \{j\}\), Est faisable. Cela diminue la différence \(|I'\setminus J|\) par 1 et ne crée pas de nouvelle paire interdite. En appliquant ceci à plusieurs reprises, le théorème 2 s’ensuit.

Remerciements

Nous apprécions les évaluateurs anonymes pour leur lecture attentive de notre manuscrit et leurs précieux commentaires. Ce travail a été partiellement soutenu par les numéros de subvention JSPS Kakenhi JP20H00595, JP21K11752, JP22H00513 et JP23H03344.

Références

[1] T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms, 4th ed., The MIT Press, 2022.

[2] M. Briański, S. Felsner, J. Hodor, and P. Micek, “Reconfiguring Independent Sets on Interval Graphs,” 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), ed. F. Bonchi and S.J. Puglisi, Leibniz International Proceedings in Informatics (LIPIcs), vol.202, Dagstuhl, Germany, pp.23:1-23:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.

[3] R. Belmonte, E.J. Kim, M. Lampis, V. Mitsou, Y. Otachi, and F. Sikora, “Token sliding on split graphs,” Theory Comput. Syst., vol.65, no.4, pp.662-686, 2021.
CrossRef

[4] P. Bonsma and L. Cereceda, “Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances,” Theor. Comput. Sci., vol.410, no.50, pp.5215-5226, 2009.
CrossRef

[5] R.A. Hearn and E.D. Demaine, “PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation,” Theor. Comput. Sci., vol.343, no.1-2, pp.72-96, 2005.
CrossRef

[6] M. Kamiński, P. Medvedev, and M. Milanič, “Complexity of independent set reconfigurability problems,” Theor. Comput. Sci., vol.439, pp.9-15, 2012.
CrossRef

[7]  M. Bonamy and N. Bousquet, “Reconfiguring independent sets in cographs,” CoRR, vol.abs/1406.1433, 2014.

[8] P. Bonsma, “Independent set reconfiguration in cographs and their generalizations,” J. Graph Theory, vol.83, no.2, pp.164-195, 2016.
CrossRef

[9] D. Lokshtanov and A.E. Mouawad, “The complexity of independent set reconfiguration on bipartite graphs,” ACM Trans. Algorithms, vol.15, no.1, pp.1-19, 2019.
CrossRef

[10] E. Fox-Epstein, D.A. Hoang, Y. Otachi, and R. Uehara, “Sliding token on bipartite permutation graphs,” Algorithms and Computation - 26th International Symposium, ISAAC 2015, Nagoya, Japan, Dec. 9-11, 2015, Proceedings, ed. K.M. Elbassioni and K. Makino, Lecture Notes in Computer Science, vol.9472, pp.237-247, Springer, 2015.
CrossRef

[11] M. Bonamy and N. Bousquet, “Token sliding on chordal graphs,” Graph-Theoretic Concepts in Computer Science - 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers, ed. H.L. Bodlaender and G.J. Woeginger, Lecture Notes in Computer Science, vol.10520, pp.127-139, Springer, 2017.

[12] L. Mirsky, “A dual of Dilworth's decomposition theorem,” The American Mathematical Monthly, vol.78, no.8, pp.876-877, 1971.
CrossRef

[13] M.L. Fredman, “On computing the length of longest increasing subsequences,” Discret. Math., vol.11, no.1, pp.29-35, 1975.
CrossRef

[14] D. Aldous and P. Diaconis, “Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem,” Bulletin of the American Mathematical Society, vol.36, pp.413-432, 1999.
CrossRef

Notes

1. Pour les éléments dans \(A\), nous préférons utiliser des entiers plutôt que \(n\) à distinguer de leurs indices dans quelques exemples concrets.
2. Encore une fois, nous utilisons des nombres entiers plus que \(n\) pour les éléments dans \(A\) pour éviter toute confusion.

Auteurs

Yuuki AOIKE
  Yokohama City University
Masashi KIYOMI
  Seikei University
Yasuaki KOBAYASHI
  Hokkaido University
Yota OTACHI
  Nagoya University

Mots-clés