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: