Przejdź do treści

Sparse induced subgraphs in P_6-free graphs

Udowadniamy, że wiele problemów obliczeniowych, które polegają na znalezieniu największego rzadkiego indukowanego podgrafu spełniającego pewną właściwość definiowalną w logice CMSO2, w tym w szczególności problemu zbioru wierzchołków przecinających wszystkie cykle (Feedback Vertex Set), można rozwiązać w czasie wielomianowym w klasie grafów, które nie zawierają indukowanej ścieżki o sześciu wierzchołkach​. Uogólnia to wyniki Grzesika, Klimošovej, Pilipczuka i Pilipczuka dotyczące problemu największego zbioru niezależnego zbioru w tej samej klasie grafów​ [SODA 2019, TALG 2022] oraz wyniki Abrishami, Chudnovsky, Pilipczuka, Rzążewskiego i Seymoura dotyczące analogicznych problemów w grafach, które nie zawierają indukowanej ścieżki o pięciu wierzchołkach [SODA 2021]. Kluczowym krokiem jest nowe uogólnienie metody potencjalnych maksymalnych klik. Pokazujemy, że zamiast generowania dużej rodziny potencjalnych maksymalnych klik, wystarczy jedynie znaleźć ich przybliżone wersje (nazwane carvers)  – zbiory wierzchołków, które zawierają te same wierzchołki z poszukiwanego rozwiązania i mają podobne właściwości separacyjne.

Materiał konferencyjny:

Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA24)

Autorzy z PW:

Paweł Rzążewski

Dyscyplina:

Rok wydania: