Odd Cycle Transversal on $H$-free graphs

1 Introduction

• Earlier results established polynomial-time cases for induced subgraphs of kP3 or P5+kP1 and NP-hardness when H contains P6 or P5+P2; for r ≥5, hardness also holds when H contains P4+P2.For r ≥5, these results already give a complete polynomial-time-versus-NP-hard dichotomy; the remaining open cases for r ∈{2, 3, 4} involved H induced by kP4.Source: §1 · p. 3

1.1 Our results

• For every fixed k, Max-Weight List 2-Colorable Induced Subgraph has an n^O_k(log n)-time algorithm on kP4-free graphs, and Odd Cycle Transversal follows as a special case.The running-time exponent hides factors depending on k.Source: §1.1 · p. 3
• For both problems on H-free graphs, they are polynomial-time solvable when H is an induced subgraph of kP3 or P5 + kP1 for some k ≥ 1, quasi-polynomial-time solvable in the remaining cases where H is an induced subgraph of kP4 for some k ≥ 1, and NP-hard otherwise.This resolves [1, Problem 4, p. 5288].Source: §1.1 · p. 4
• Theorem 3 classifies both two-color problems as polynomial-time solvable for H induced by kP3 or P5+kP1, quasi-polynomial-time solvable for the remaining H induced by kP4, and NP-hard otherwise.The hardness for H that is not a linear forest follows from the result of Chiarelli, Hartinger, Johnson, Milanič, and Paulusma [4].Source: §1.1 · p. 4
• For every fixed H without isolated vertices and fixed k ≥2, each n-vertex kH-free graph has a constructible H-amiable family of size n^O_H,k(log n).The family is a key ingredient in the proof of the two-color algorithm.Source: §1.1 · p. 4
• For connected H and fixed k ≥2, an oracle for Max-Weight Independent Set on H-free graphs gives an n^O_H,k(log n)-overhead reduction from kH-free graphs.This improves the n^O_H(log^3 n) overhead of the general reduction in [12].Source: §1.1 · p. 5

1.2 Technical overview

• A branching procedure selects a maximum-score vertex, splitting independent sets into those avoiding it and those containing it; the second branch removes a constant fraction of induced H-copies.The resulting recurrence bounds the family construction by quasi-polynomial size and time, while the absence of isolated vertices in H preserves H-freeness when the selected vertex is added.Source: §1.2 · p. 6
• A two-layer auxiliary graph encodes feasible list colorings as stable sets and is perfect when both input subsets induce P4-free graphs.The algorithm enumerates quasi-polynomially many subset pairs using the P4-amiable family, solves maximum-weight stable set on each perfect graph, and returns the largest solution.Source: §1.2 · pp. 6–7

• The paper denotes the positive integers by N and writes [n] for {1, …, n}.Source: §2 · p. 7
• For a vertex set X, G[X] is the subgraph induced by X; X may also denote that induced subgraph.Source: §2 · p. 7
• N_G(v) and N_G[v] denote the open and closed neighborhoods of v, respectively.Source: §2 · p. 7
• Vertex sets are complete to one another when all cross-pairs are edges, and anticomplete when none are.Source: §2 · p. 7
• An isomorphism preserves adjacency and non-adjacency, and is written φ: G → G′.Source: §2 · p. 7

• Every n-vertex kH-free graph admits an H-amiable family of size n^O_H,k(log n), constructible in time n^O_H,k(log n).Source: §3 · p. 7
• The recursion chooses a maximum-score vertex; its score counts H-copies meeting its closed neighborhood, and the selected vertex has score at least µ(F)/((k−1)h).Source: §3 · pp. 7–8
• An H-amiable family consists of H-free induced subgraphs and contains a member covering every independent set of the input graph.Source: §3 · p. 8
• The recursion has two branches, on F−v_F and F−N_F[v_F], with v_F added to the selected set on the second branch.Source: §3 · p. 9
• The distinct outputs at the recursion leaves are precisely the members of the constructed family, and lazy construction with deduplication achieves the stated quasi-polynomial running time.Source: §3 · p. 9

4 The proof of Theorem 1

• Stable sets of the two-layer auxiliary graph correspond weight-preservingly to feasible list-colored induced subgraphs whose color classes lie in the chosen containers.With both containers equal to V(G), maximizing stable-set weight solves the original optimization problem.Source: §4 · p. 10
• When both containers induce P4-free graphs, the two-layer list auxiliary graph is perfect.This permits polynomial-time maximum-weight stable-set computation on each auxiliary graph.Source: §4 · p. 11
• The perfectness proof excludes odd holes by bounding layer-segment lengths and excludes long odd antiholes because each layer contributes at most three vertices.With no odd holes or odd antiholes, the Strong Perfect Graph Theorem gives perfectness.Source: §4 · pp. 11–12
• For every fixed k, Max-Weight List 2-Colorable Induced Subgraph is solvable optimally on kP4-free graphs in quasi-polynomial time.The stated running time is n^{O_k(log n)}.Source: §4 · p. 13
• The algorithm enumerates ordered pairs from a quasi-polynomial-size P4-amiable family and solves a maximum-weight stable-set problem for each pair.The family covers every stable set, and its members induce P4-free graphs, making the auxiliary graphs perfect.Source: §4 · p. 13
• The enumerated pair containing the optimum coloring’s two stable color classes produces a feasible candidate of at least optimal weight, so the best candidate is optimal.The stable-set and coloring correspondence preserves weights.Source: §4 · pp. 10, 13

5 Concluding remarks

• The result for kP4-free graphs, combined with known literature results, resolves the open quasi-polynomial-time-versus-NP-hard dichotomy for Odd Cycle Transversal on H-free graphs.The paper identifies this as resolving an open problem posed by Agrawal, Lima, Lokshtanov, Saurabh, and Sharma.Source: §5 · p. 14
• Whether the algorithms for Odd Cycle Transversal and Max-Weight List 2-Colorable Induced Subgraph can be made polynomial-time on kP4-free graphs remains open.The paper connects a positive answer to completing the P-versus-NP-hard dichotomy for both problems on H-free graphs.Source: §5 · p. 14
• Similar dichotomies for Max-Weight List r-Colorable Induced Subgraph remain to be established for r in {3, 4}.The paper also notes that no quasi-polynomial-time algorithm for List 4-Coloring on kP4-free graphs is known to its authors.Source: §5 · p. 14
• Extending the method to bounded induced-P4-packing treewidth would require a local perfectness argument or another way to solve the residual instances.The current lemma requires both auxiliary-graph layers to be globally P4-free.Source: §5 · p. 14