TY - JOUR
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:
∗Received by the editors September 17, 2020; accepted for publication (in revised form) July 11, 2021; published electronically October 14, 2021. The extended abstract of this paper was presented on the conference ESA 2020, Pisa, Italy, 2020, pp. 35:1–35:17. https://doi.org/10.1137/20M1367660 Funding: The first author’s material is based upon work supported in part by the U.S. Army Research Office under grant W911NF-16-1-0404 and by NSF grant DMS-1763817. The third author’s 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 677651). The fourth author was supported by Polish National Science Centre grant 2018/31/D/ST6/00062. The fifth author’s material is based upon work supported by the National Science Foundation under award DMS-1802201.
Publisher Copyright:
© 2021 Society for Industrial and Applied Mathematics
PY - 2021
Y1 - 2021
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)); and 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)); and 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 - Graph homomorphism
KW - Odd cycle transversal
KW - P-free graphs
UR - http://www.scopus.com/inward/record.url?scp=85117162734&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85117162734&partnerID=8YFLogxK
U2 - 10.1137/20M1367660
DO - 10.1137/20M1367660
M3 - Article
AN - SCOPUS:85117162734
SN - 0895-4801
VL - 35
SP - 2357
EP - 2386
JO - SIAM Journal on Discrete Mathematics
JF - SIAM Journal on Discrete Mathematics
IS - 4
ER -