Ομιλητής: Δημήτριος Μ. Θηλυκός (Τμ. Μαθηματικών ΕΚΠΑ
Τίτλος: Μετρώντας Τέλεια Ταιριάσματα σε Γραφήματα
Ημέρα: 08-05-2023, 15:30
Μέρος: Αίθουσα Γ22, Τμήμα Μαθηματικών ΕΚΠΑ
Σύνοψη
Το πρόβλημα μέτρησης #Τέλεια Ταιριάσματα αφορά τον υπολογισμό του πλήθους των τέλειων ταιριασμάτων ενός γραφήματος G. Το πρόβλημα αυτό σχετίζεται άμεσα με τον υπολογισμό της παραμένουσας δυαδικών πινάκων και είναι #P-πλήρες (Valiant 1979). Εξετάζουμε την παραμετρική έκδοση του προβλήματος #Τέλεια Ταιριάσματα(F) όπου οι είσοδοι του πρόβληματος είναι γραφήματα που αποκλείουν ως ελάσσονα τα γραφήματα ενός δεδομένου συνόλου γραφημάτων F. Το ερώτημα που τίθεται είναι: «για ποια σύνολα F το πρόβλημα είναι πολυωνυμικά επιλύσιμο και για ποια παραμένει #P-πλήρες;». Για παράδειγμα, το #Τέλεια Ταιριάσματα({K_5 , K_3,3 }) (δηλ. ο υπολογισμός του πλήθους τέλειων ταιριασμάτων επίπεδων γραφημάτων) είναι πολυωνυμικά υπολογίσιμο χάρη στον κλασικό FKT-αλγόριθμο (Kasteleyn 1961 και Temperley & Fisher 1961), ο οποίος βασίζεται σε μια αναγωγή στο πρόβλημα του υπολογισμού της ορίζουσας, βασιζόμενη στην χρήση Φαφιανών (Phaffian) πινάκων. Από την άλλη, το #Τέλεια Ταιριάσματα({K_8}) είναι #P-πλήρες, σύμφωνα με τα πρόσφατα αποτελέσματα των Curticapean & Xia (2021). Για την επίλυση του παραπάνω προβλήματος για κάθε F, ορίζουμε ένα παραμετρικό γράφημα το οποίο καλούμε ρηχή δίνη. Η υπολογιστική πολυπλοκότητα μέτρησης του προβλήματος #Τέλεια Ταιριάσματα(F) επιλύεται πλήρως ως εξής: είναι πολυωνυμικά επιλύσιμο αν το F περιέχει κάποιο έλασσον ρηχής δίνης, διαφορετικά είναι #P-πλήρες. Για την απόδειξη της παραπάνω υπολογιστικής διχοτομίας χρησιμοποιούμε τεχνικές από την Δομική Θεωρία Γραφημάτων. Συγκεκριμένα αποδεικνύουμε μια παραλλαγή του Δομικού Θεωρήματος των Ελάσσόνων Γραφημάτων των Robertson & Seymour (Graph Minors XVI, 2003) στην οποία αναδεικνύουμε των δομή των γραφημάτων που δεν περιέχουν ρηχές δίνες ως ελάσσονα.