License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2020.35
URN: urn:nbn:de:0030-drops-129019
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12901/
Go to the corresponding LIPIcs Volume Portal

Chudnovsky, Maria ; King, Jason ; Pilipczuk, Michał ; Rzążewski, Paweł ; Spirkl, Sophie

Finding Large H-Colorable Subgraphs in Hereditary Graph Classes

pdf-format:
LIPIcs-ESA-2020-35.pdf (0.9 MB)

Abstract

We 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^?(ω(G));
- in {P₆,1-subdivided claw}-free graphs in time n^?(ω(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.

BibTeX - Entry

@InProceedings{chudnovsky_et_al:LIPIcs:2020:12901,
  author =	{Maria Chudnovsky and Jason King and Micha{\l} Pilipczuk and Pawe{\l} Rzążewski and Sophie Spirkl},
  title =	{{Finding Large H-Colorable Subgraphs in Hereditary Graph Classes}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{35:1--35:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12901},
  URN =		{urn:nbn:de:0030-drops-129019},
  doi =		{10.4230/LIPIcs.ESA.2020.35},
  annote =	{Keywords: homomorphisms, hereditary graph classes, odd cycle transversal}
}

Keywords: homomorphisms, hereditary graph classes, odd cycle transversal
Collection: 28th Annual European Symposium on Algorithms (ESA 2020)
Issue Date: 2020
Date of publication: 26.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI