Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

Finding Large H-Colorable Subgraphs in Hereditary Graph Classes

Uproszczony widok
cris.lastimport.scopus2024-02-12T19:35:07Z
dc.abstract.enWe study the Max Partial H-Coloring problem: given a graph G, find the largest induced subgraph of G that admits a homomorphism into H, where H is a fixed pattern graph without loops. Note that when H is a complete graph on k vertices, the problem reduces to finding the largest induced k-colorable subgraph, which for k = 2 is equivalent (by complementation) to Odd Cycle Transversal. We prove that for every fixed pattern graph H without loops, Max Partial H-Coloring can be solved: - in {P₅,F}-free graphs in polynomial time, whenever F is a threshold graph, - in {P₅,bull}-free graphs in polynomial time, - in P₅-free graphs in time n^O(ω(G)), - in {P₆,1-subdivided claw}-free graphs in time n^O(ω(G)³). Here, n is the number of vertices of the input graph G and ω(G) is the maximum size of a clique in G. Furthermore, by combining the mentioned algorithms for P₅-free and for {P₆,1-subdivided claw}-free graphs with a simple branching procedure, we obtain subexponential-time algorithms for Max Partial H-Coloring in these classes of graphs. Finally, we show that even a restricted variant of Max Partial H-Coloring is NP-hard in the considered subclasses of P₅-free graphs, if we allow loops on H.
dc.abstract.plW pracy badamy złożoność problemu znajdowania największego indukowanego podgrafu, który jest homomorficzny z ustalonym grafem H. Pokazujemy, że przy pewnych założeniach na instancje wejściowe, problem może być rozwiązany w czasie wielomianowym (lub podwykładniczym).
dc.affiliationUniwersytet Warszawski
dc.conference.countryWłochy
dc.conference.datefinish2020-09-09
dc.conference.datestart2020-09-07
dc.conference.placePisa
dc.conference.seriesEuropean Symposium on Algorithms
dc.conference.seriesEuropean Symposium on Algorithms
dc.conference.seriesshortcutESA
dc.conference.shortcutESA 2020
dc.conference.weblinkhttp://algo2020.di.unipi.it/ESA2020/index.html
dc.contributor.authorPilipczuk, Michał
dc.contributor.authorChudnovsky, Maria
dc.contributor.authorKing, Jason
dc.contributor.authorRzążewski, Paweł
dc.contributor.authorSpirkl, Sophie
dc.date.accessioned2024-01-25T00:40:52Z
dc.date.available2024-01-25T00:40:52Z
dc.date.issued2020
dc.description.financePublikacja bezkosztowa
dc.identifier.doi10.4230/LIPICS.ESA.2020.35
dc.identifier.issn1868-8969
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/107158
dc.identifier.weblinkhttps://drops.dagstuhl.de/opus/frontdoor.php?source_opus=12901
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.ispartofLeibniz International Proceedings in Informatics
dc.relation.pages35:1-35:17
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.subject.enhomomorphisms
dc.subject.enhereditary graph classes
dc.subject.enodd cycle transversal
dc.subject.plhomomorfizmy
dc.subject.pldziedziczne klasy grafów
dc.subject.plzbiór przecinający cykle nieparzyste
dc.titleFinding Large H-Colorable Subgraphs in Hereditary Graph Classes
dc.typeJournalArticle
dspace.entity.typePublication