Maximum Partial List H-Coloring on P_5-free graphs in polynomial time

This paper proves that the Maximum Partial List H-Coloring problem is solvable in polynomial time on P_5-free graphs for any fixed graph H, thereby resolving an open question from SODA 2024 and improving upon a previous algorithm by Chudnovsky et al.

The Gist

Imagine you are the manager of a massive, chaotic office building (the Graph). You have a strict set of rules about who can sit next to whom (the Target Graph H). For example, maybe "Managers" can sit next to "Interns," but two "Managers" cannot sit next to each other.

Your goal is to pick the largest, most valuable group of employees to keep in the building so that everyone follows the seating rules. Some employees are more valuable than others (the Weights). Some employees have restrictions on who they can sit next to (the Lists).

This is the Maximum Partial List H-Coloring problem. It's a classic puzzle in computer science that is usually incredibly hard to solve, often taking longer than the age of the universe for large buildings.

The Big Breakthrough

The authors of this paper solved a specific, very tricky version of this puzzle: What if the office building has no long, winding corridors of 5 empty desks in a row?

In math-speak, they call these "P5-free graphs." In our analogy, it means the building layout is "clumped" or "bubbly" rather than having long, straight, empty hallways.

They proved that for these specific types of buildings, you can find the perfect group of employees quickly (in polynomial time). Before this, the best known method was slow and depended on how many cliques (groups of friends who all know each other) existed in the building. This new method is fast regardless of how many friend groups there are.

How Did They Do It? (The Analogy)

The authors used a clever "divide and conquer" strategy, which they built in three main steps:

1. The "Dominating" Team (Finding the Core)

Imagine you need to find a small team of "Team Leaders" who can keep an eye on the entire group you want to keep.

• The Trick: In these "clumped" buildings (P5-free), you can always find a tiny team of leaders (either a small clique or a short line of 3 people) that "dominates" the whole group. Everyone else is either a leader or sitting right next to a leader.
• Why it helps: Instead of guessing the position of every single employee, you only need to guess the positions of this tiny team of leaders. Once you know where they sit, the rules for everyone else become much simpler.

2. The "List Shrinker" (Simplifying the Rules)

Once you've guessed where the leaders sit, you can update the rules for everyone else.

• The Magic: If a leader sits in "Seat A," then anyone sitting next to them cannot sit in "Seat A" (or any seat that conflicts with A).
• The Result: This shrinks the list of possible seats for the remaining employees. The authors showed that if you do this right, you can break the problem down into smaller, easier problems where the employees have fewer choices to make.
• The Recursion: They repeat this process. Every time they shrink the lists, the problem gets simpler. Since there are only a limited number of seats (k), they only have to do this shrinking a few times before the lists are so small (just 1 seat left) that the answer is obvious.

3. The "Blob" Map (Connecting the Dots)

After breaking the building down into manageable chunks, they realized something amazing:

• The problem of picking the best group of employees is mathematically identical to finding the Maximum Weight Independent Set on a new, smaller map called a "Blob Graph."
• The Blob Graph: Imagine each "chunk" of the building is a single dot (a blob). If two chunks are too close to each other (they touch or have neighbors), draw a line between the dots.
• The P5-Free Superpower: The authors proved that if the original building had no long empty corridors, this new "Blob Graph" also has no long empty corridors.
• The Final Step: Finding the best group of non-touching blobs in a "P5-free" Blob Graph is a problem that computers can already solve very fast (thanks to previous research).

Why Does This Matter?

1. It Solves a Long-Standing Mystery: For years, computer scientists wondered if this specific coloring problem could be solved quickly on these types of graphs. This paper says, "Yes, it can!"
2. It's Faster: Previous methods were slow if the building had many tight-knit friend groups (cliques). This new method is fast no matter how many friend groups exist.
3. Real-World Impact: While this sounds abstract, these graph problems show up in real life:
   • Scheduling: Assigning tasks to workers without conflicts.
   • Frequency Assignment: Giving radio towers frequencies so they don't interfere.
   • Bioinformatics: Understanding how proteins fold and interact.

Summary

The authors took a nightmare of a puzzle, realized that the "no long corridors" rule (P5-free) makes the building layout very structured, used that structure to shrink the problem down to its simplest parts, and then mapped the whole thing onto a simpler puzzle that computers already know how to win.

They didn't just find a solution; they found a fast, reliable recipe for solving it, turning a problem that was thought to be nearly impossible into a routine calculation.

Technical Summary

Here is a detailed technical summary of the paper "Maximum Partial List H-Coloring on P5-free graphs in polynomial time."

1. Problem Definition

The paper addresses the Maximum Partial List H-Coloring problem.

• Input: A fixed graph $H$ (without loops), an input graph $G$, a weight function $wt: V(G) \to \mathbb{Q}_{\geq 0}$, and a list function $list: V(G) \to 2^{V(H)}$.
• Goal: Find an induced subgraph $G^*$ of $G$ such that:
  1. There exists a homomorphism $hom: V(G^*) \to V(H)$ respecting the list function (i.e., $hom(v) \in list(v)$ for all $v \in V(G^*)$).
  2. The total weight $wt(V(G^*))$ is maximized.
• Special Cases:
  • If $H$ is a clique of size $k$ and lists are unrestricted, this becomes the Maximum $k$-Colorable Subgraph problem.
  • If $k=2$, it is equivalent to the dual of the Odd Cycle Transversal problem.

2. Context and Motivation

• Previous State of the Art:
  • For general graphs, the problem is NP-hard.
  • On $P_5$-free graphs (graphs excluding the path on 5 vertices as an induced subgraph), the complexity was open.
  • Chudnovsky et al. (2021) provided an algorithm running in $n^{O(\omega(G))}$ time, where $\omega(G)$ is the clique number. This is not polynomial if $\omega(G)$ is unbounded.
  • Agrawal et al. (SODA 2024) showed that Odd Cycle Transversal is polynomial-time solvable on $P_5$-free graphs, leaving the general Maximum $k$-Colorable Subgraph as the last open case for $H$-free dichotomies.
• The Open Question: Is Maximum $k$-Colorable Subgraph (and by extension, Maximum Partial List H-Coloring) solvable in polynomial time on $P_5$-free graphs?

3. Key Contributions and Results

The authors resolve the open question positively with the following main result:

Theorem 1: Maximum Partial List H-Coloring can be solved in $n^{O(k^4)}$ time on $P_5$-free graphs, where $k = |V(H)|$.

• This result is polynomial for any fixed $H$, independent of the clique number $\omega(G)$ of the input graph.
• It implies that Maximum $k$-Colorable Subgraph is polynomial-time solvable on $P_5$-free graphs.

4. Methodology and Algorithmic Approach

The proof follows a structural decomposition strategy inspired by recent work on Odd Cycle Transversal but requires significant adaptation due to the complexity of the homomorphism constraints. The approach consists of three main stages:

A. Inductive Step: Reducing List Size (Lemma 1)

The core challenge is handling the case where a maximum weight solution is connected.

• Strategy: The authors design an algorithm (Algorithm 1) that, assuming a connected maximum weight solution exists, either finds it or reduces the problem to a family of sub-instances where the list size (maximum number of allowed colors for any vertex) is strictly smaller.
• Mechanism:
  1. Dominating Set: Utilizing the property that connected $P_5$-free graphs have a small dominating set (either a $P_3$ or a clique), the algorithm guesses a small dominating set $D$ for the solution.
  2. Partitioning: The graph is partitioned based on $D$.
  3. List Pruning: By guessing the mapping of $D$ to $H$ and analyzing neighbors, the algorithm prunes the lists of vertices in the remaining components. Specifically, if a vertex $v$ is adjacent to a set of vertices mapped to color $r$, $v$ cannot be mapped to $r$ or any non-neighbor of $r$ in $H$.
  4. Recursion: This pruning ensures that for the resulting sub-instances, the maximum list size decreases. Since the list size is bounded by $k$, this allows for a recursion depth of at most $k$.

B. Constructing a Polynomial-Sized Family (Lemma 2 & Algorithm 2)

To solve the general case (where the solution may not be connected), the authors construct a family $\mathcal{C}$ of connected vertex sets.

• Goal: Find a family $\mathcal{C}$ such that:
  1. Every set in $\mathcal{C}$ admits a valid homomorphism to $H$.
  2. There exists a maximum weight solution $S$ that is a disjoint union of sets from $\mathcal{C}$ (where no two sets in the union touch).
• Algorithm 2: This is a recursive procedure that:
  1. Guesses a "core" structure (dominating set $D$ and its mapping $h$) for a potential connected component of the solution.
  2. Uses the Inductive Step (Lemma 1) to handle the component containing $D$.
  3. Recursively calls itself on the remaining parts of the graph.
  4. Ensures that the family size remains polynomial ($n^{O(k^4)}$) by bounding the number of guesses and recursive branches.

C. Reduction to Maximum Weight Independent Set (MWIS)

Once the family $\mathcal{C}$ is constructed, the problem is transformed:

1. Blob Graph Construction: Create an auxiliary graph $G_{blob}^{\mathcal{C}}$ where each vertex represents a set $C \in \mathcal{C}$. An edge exists between two vertices if the corresponding sets $C_1$ and $C_2$ "touch" (intersect or have an edge between them).
2. Weight Assignment: The weight of a vertex in $G_{blob}^{\mathcal{C}}$ is the sum of weights of vertices in the corresponding set $C$.
3. Equivalence: Finding the maximum weight solution in $G$ is equivalent to finding the Maximum Weight Independent Set (MWIS) in $G_{blob}^{\mathcal{C}}$.
4. Final Step: A key structural proposition (Proposition 5.1) states that if $G$ is $P_5$-free, then $G_{blob}^{\mathcal{C}}$ is also $P_5$-free. Since MWIS is solvable in polynomial time on $P_5$-free graphs (Lokshtanov et al., 2014), the entire problem is solved in polynomial time.

5. Significance

• Resolution of an Open Problem: It definitively answers the question posed by Agrawal et al. (SODA 2024) regarding the complexity of Maximum $k$-Colorable Subgraph on $P_5$-free graphs.
• Generalization: It solves a much more general problem (List H-Coloring) compared to previous specific cases, unifying the understanding of coloring problems on $P_5$-free graphs.
• Algorithmic Improvement: It improves upon the $n^{O(\omega(G))}$ algorithm by Chudnovsky et al. (2021) to a true polynomial time algorithm $n^{O(k^4)}$ that does not depend on the clique number of the input graph.
• Structural Insight: The paper provides a novel framework for handling homomorphism constraints on $P_5$-free graphs by combining structural graph theory (dominating sets, modules) with list reduction techniques and the "blob graph" reduction to MWIS.

6. Conclusion

The paper establishes that Maximum Partial List H-Coloring is in P for $P_5$-free graphs. The authors achieve this by designing a recursive algorithm that reduces list constraints and constructing a polynomial-sized family of candidate connected components, ultimately reducing the problem to the known polynomial-time solvable Maximum Weight Independent Set problem on $P_5$-free graphs. This represents a significant advancement in the algorithmic theory of graph coloring and homomorphism problems.