TY - GEN

T1 - Finding large H-colorable subgraphs in hereditary graph classes

AU - Chudnovsky, Maria

AU - King, Jason

AU - Pilipczuk, Michał

AU - Rzążewski, Paweł

AU - Spirkl, Sophie

N1 - Funding Information:
Funding Maria Chudnovsky: This material is based upon work supported in part by the U. S. Army Research Office under grant number W911NF-16-1-0404, and by NSF grant DMS-1763817. Michał Pilipczuk: This work is a part of project TOTAL that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 677651).
Funding Information:
Paweł Rzążewski: Supported by Polish National Science Centre grant no. 2018/31/D/ST6/00062. Sophie Spirkl: This material is based upon work supported by the National Science Foundation under Award No. DMS1802201.
Publisher Copyright:
© Maria Chudnovsky, Jason King, Michał Pilipczuk, Paweł Rzążewski, and Sophie Spirkl

PY - 2020/8/1

Y1 - 2020/8/1

N2 - 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 {P5, F}-free graphs in polynomial time, whenever F is a threshold graph; in {P5, bull}-free graphs in polynomial time; in P5-free graphs in time nO(ω(G)); in {P6, 1-subdivided claw}-free graphs in time nO(ω(G)3) . 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 P5-free and for {P6, 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 P5-free graphs, if we allow loops on H.

AB - 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 {P5, F}-free graphs in polynomial time, whenever F is a threshold graph; in {P5, bull}-free graphs in polynomial time; in P5-free graphs in time nO(ω(G)); in {P6, 1-subdivided claw}-free graphs in time nO(ω(G)3) . 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 P5-free and for {P6, 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 P5-free graphs, if we allow loops on H.

KW - Hereditary graph classes

KW - Homomorphisms

KW - Odd cycle transversal

UR - http://www.scopus.com/inward/record.url?scp=85092463318&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85092463318&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ESA.2020.35

DO - 10.4230/LIPIcs.ESA.2020.35

M3 - Conference contribution

AN - SCOPUS:85092463318

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 28th Annual European Symposium on Algorithms, ESA 2020

A2 - Grandoni, Fabrizio

A2 - Herman, Grzegorz

A2 - Sanders, Peter

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 28th Annual European Symposium on Algorithms, ESA 2020

Y2 - 7 September 2020 through 9 September 2020

ER -