Fair Vertex Problems Parameterized by Cluster Vertex Deletion

1. Problem Definition and Context

Fair Vertex Problems:
The paper investigates "fair" variants of standard graph problems. Unlike traditional problems that seek a solution set $X$ of minimum cardinality (size), fair problems seek a set $X$ that minimizes the fair cost.

• Fair Cost ($fc$): Defined as $fc(X) := \max_{v \in V(G)} |N(v) \cap X|$.
• Goal: Find a set $X$ satisfying a specific logical property (e.g., $G \setminus X$ is a forest) such that no vertex in the graph has more than $k$ neighbors in $X$.

Parameterization:
The study focuses on structural parameterization by the Cluster Vertex Deletion (CVD) number.

• CVD Number: The size of the smallest set $D \subseteq V(G)$ (called a modulator) such that $G \setminus D$ is a collection of disjoint cliques.
• Context: Previous work established that Fair MSO$_1$ problems are Fixed-Parameter Tractable (FPT) when parameterized by Twin Cover (a stronger parameter). The open question was whether this extends to the more general Cluster Vertex Deletion parameter.

Logical Framework:
The problems are defined using Monadic Second-Order logic (MSO$_1$), which allows quantification over vertices and sets of vertices (but not edges). The paper considers two main variants:

1. L-FairVD (Deletion): Find $X$ such that $G \setminus X \models \phi$.
2. L-FairVE (Evaluation): Find sets $W_1, \dots, W_\ell$ satisfying a formula $\phi(W_1, \dots, W_\ell)$.

---

2. Key Contributions

The paper provides a dichotomy for Fair MSO$_1$ problems parameterized by CVD:

1. Hardness Result (Negative):

   • Theorem 1: The Fair Vertex FO Deletion problem is W[1]-hard when parameterized by the cluster vertex deletion number (for CVD $>3$) and the size of the formula.
   • This answers the open question from [16] negatively, proving that a general FPT algorithm for all Fair MSO$_1$ problems under CVD parameterization is impossible (unless FPT = W[1]).

2. Positive Result (Metatheorem):

   • Theorem 3 & 24: The authors identify a sufficient condition under which Fair MSO$_1$ problems are FPT parameterized by CVD.
   • The condition relies on the concept of $\alpha$-coherent shapes. If a problem admits a solution where the interaction between the solution set and the cliques in $G \setminus D$ follows a specific "coherent" pattern (either selecting almost all vertices or almost none from specific neighborhood types within cliques), an FPT algorithm exists.

3. Algorithmic Application:

   • The metatheorem is applied to solve several natural problems in FPT time, including:
     • Fair Vertex Cover
     • Fair Feedback Vertex Set
     • Fair Odd Cycle Transversal
     • Fair Dominating Set
     • Fair $[\sigma, \rho]$-Domination (for finite $\sigma$, or cofinite $\sigma, \rho$).

---

3. Methodology

The authors employ a sophisticated combination of model-checking techniques, structural graph theory, and Integer Linear Programming (ILP).

A. Structural Decomposition and "Shapes"

The core of the algorithm relies on compressing the solution space using Shapes.

• Modulator ($D$): The graph is split into the modulator $D$ and a collection of cliques $\mathcal{C}$ in $G \setminus D$.
• Clique Types: Vertices in a clique $C$ are categorized by their neighborhood in $D$. A Clique Type is a vector counting how many vertices in $C$ connect to each subset of $D$.
• Solution Patterns: For a clique $C$, the solution $X$ is described by how many vertices it selects from each neighborhood type.
• Shapes: A "Shape" is a compact representation (a matrix) that aggregates the counts of cliques of specific types and the solution patterns they follow.
  • Boundedness: The number of vertices selected from a specific neighborhood type is capped at a threshold $\alpha$. If the count exceeds $\alpha$, it is treated as "unbounded" but categorized as either thin (few selected) or thick (few excluded).
  • Coherence: A shape is $\alpha$-coherent if, for every unbounded neighborhood type, the solution is consistently "thin" (selecting few) or "thick" (selecting most) across all cliques of that type.

B. Model-Checking on Shapes

• Irrelevant Vertices/Cliques: Using logical tools (specifically the "irrelevant vertex" lemma and "irrelevant clique" lemma), the authors prove that if a graph has many cliques of the same type, the truth of an MSO$_1$ formula depends only on the shape of the solution, not the exact number of cliques (provided the number is large enough).
• Lemma 13: Establishes that for sufficiently large $\alpha$ and $\gamma$, $G \models \phi(X)$ if and only if the shape of $(G, X)$ satisfies the formula. This allows the algorithm to check the logical condition on the compressed shape rather than the full graph.

C. Integer Linear Programming (ILP)

Once a valid shape (satisfying the logical formula) is identified, the algorithm must reconstruct a solution with minimal fair cost.

• ILP Formulation: The problem of finding a set $X$ matching a specific shape with fair cost $\le k$ is formulated as an ILP.
  • Variables: Represent the number of cliques of a certain type assigned to a specific solution pattern.
  • Constraints:
    1. Consistency: The number of cliques assigned must match the counts in the shape matrix.
    2. Fair Cost: The total number of neighbors in $X$ for any vertex in the modulator $D$ must not exceed $k$.
• Complexity: The number of variables in the ILP depends only on the parameters (formula size, CVD number, $\alpha$, $\gamma$), not on the graph size.
• Solving: The ILP is solved using Lenstra's algorithm (improved by Reis and Rothvoss), which runs in time $f(p) \cdot \text{poly}(n)$, where $p$ is the number of variables. This ensures the overall algorithm is FPT.

---

4. Hardness Proof (W[1]-hardness)

To prove that the general case is W[1]-hard, the authors reduce from Unary $\ell$-Bin Packing (known to be W[1]-hard parameterized by $\ell$).

1. Reduction: They construct a graph where the modulator size corresponds to the number of bins ($d = \ell$).
2. Cliques as Items: Each item in the bin packing instance is represented by a clique. The size of the clique and its connections to the modulator encode the item's size.
3. Logic: An FO formula is constructed to enforce that for every clique, the solution must "remove" a specific subset of vertices corresponding to the item being placed in a specific bin.
4. Fair Cost: The fair cost constraint ensures that the capacity of the bins is not exceeded.
5. Result: A solution to the Fair Vertex FO Deletion problem exists if and only if the Bin Packing instance is solvable. Since Bin Packing is W[1]-hard, so is the general Fair Vertex problem under CVD.

---

5. Significance and Impact

• Resolution of Open Questions: The paper definitively resolves the question of whether Fair MSO$_1$ problems are FPT under CVD parameterization. It shows that while the general problem is intractable (W[1]-hard), a large and natural subclass of problems is tractable.
• Metatheorem for Fair Problems: It provides a powerful metatheorem (Theorem 24) that allows researchers to determine if a specific fair problem is FPT by verifying the "coherence" of its solution structure on cliques.
• Bridging Logic and Optimization: The work elegantly combines MSO model-checking (logic) with combinatorial optimization (ILP) to handle fairness constraints, which are notoriously difficult to parameterize.
• Future Directions: The paper highlights open questions, such as whether the tractability extends to the Modular Width parameter (a denser parameter) and whether all cases of Fair $[\sigma, \rho]$-Domination are FPT. It also raises the question of whether these problems are in XP (polynomial for fixed parameter) when parameterized by Clique-width.

In summary, this paper establishes a nuanced boundary for the parameterized complexity of fair graph problems, proving that while a universal FPT algorithm is impossible for CVD, a robust framework exists for solving many fundamental problems efficiently.