Zusammenfassung - Konsensprobleme mit Swaps und Substitutionen für Strings

Konsensprobleme mit Swaps und Substitutionen für Strings

2025-07-25 10:20:55

{"Estéban Gabory","Laurent Bulteau","Gabriele Fici","Hilde Verbeek"}

{cs.DS,cs.CC}

Das Papier untersucht Konsensprobleme für Zeichenketten, insbesondere das Nähereste-Zeichenkette-Problem, bei dem das Ziel darin besteht, eine Zeichenkette zu finden, die eine gegebene Distanz (wie die Hamming-Distanz) zu einem Eingabesatz von Zeichenketten minimiert. Das Papier erweitert dieses Problem durch die Erlaubnis von Vertauschungen benachbarter Zeichen zusätzlich zu Substitutionen, wobei jede Operation einen Einheitskosten verursacht. Die Hauptbeiträge des Papiers sind: 1. Die Autoren zeigen, dass das allgemeine Problem der Suche nach einer Zeichenkette, die die maximale Distanz zu allen Eingabezeichenketten minimiert (mit Vertauschungen und Substitutionen erlaubt), NP-schwer ist, selbst wenn nur Vertauschungen erlaubt sind. 2. Sie beweisen, dass dieses Problem in Bezug auf den Parameter d (die erlaubte maximale Distanz) fixparameterträchtig (FPT) ist. Dies bedeutet, dass es ein Algorithmus gibt, der in Zeit polynomiell in der Größe des Eingangs und exponentiell in d läuft. 3. Sie untersuchen eine Variante des Problems, bei der das Ziel darin besteht, die Summe der Distanzen von der Ausgangszeichenkette zu allen Eingabezeichenketten zu minimieren. Sie präsentieren einen polynomiellen Algorithmus für diese Variante. Das Papier betrachtet auch die Vertauschungs-Distanz, die die minimale Anzahl der erforderlichen Vertauschungen ist, um eine Zeichenkette in eine andere zu verwandeln. Sie zeigen, dass die Radius-nur-Variante des Näheresten-Zeichenkette- Problems unter der Vertauschungs-Distanz FPT ist und dass die Summe-nur-Variante in P (polynomialer Zeit) liegt. Insgesamt bietet das Papier eine umfassende Analyse von Konsensproblemen für Zeichenketten mit Vertauschungen und Substitutionen und präsentiert effiziente Algorithmen zur Lösung dieser Probleme.