Perfect Edge Domination in $P_6$-free Graphs and in Graphs Without Efficient Edge Dominating Sets

This paper establishes the NP-completeness of determining whether graphs lacking efficient edge dominating sets possess at least two perfect edge dominating sets, while also presenting a cubic-time algorithm to find, count, and weight minimal perfect edge dominating sets in $P_6$-free graphs.

The Gist

Imagine a city made of intersections (vertices) and roads (edges). In this city, we have a special rule: a road "dominates" itself and any other road that shares an intersection with it.

Now, imagine you are a city planner trying to place "Traffic Controllers" on specific roads. Your goal is to cover the entire city with these controllers, but you have two different sets of rules you might be trying to follow:

1. The "Perfect" Rule (Perfect Edge Domination): Every road without a controller must be watched by exactly one controller. A road with a controller doesn't need to be watched by anyone else.
2. The "Efficient" Rule (Efficient Edge Domination): This is even stricter. Every road in the city, whether it has a controller or not, must be watched by exactly one controller. This means no two controllers can ever be on roads that touch each other.

The Big Problem

The paper tackles two main questions about these Traffic Controllers:

1. The "Impossible City" Problem (DIM-less Graphs)
Some cities are built in such a weird way that it is impossible to place controllers following the strict "Efficient" rule. There is no way to arrange them so that every road is watched exactly once.

• The Paper's Discovery: The authors proved that for these "impossible" cities, figuring out if there are at least two different ways to place controllers following the looser "Perfect" rule is a nightmare for computers. It's an NP-complete problem.
• The Analogy: Imagine trying to solve a maze where the exit doesn't exist. The computer has to check every single dead end to prove there isn't a hidden exit, which takes forever as the maze gets bigger. The paper shows that even asking "Are there two different ways to arrange the controllers?" is just as hard as solving the whole maze.

2. The "No Long Roads" City (P6-free Graphs)
Now, imagine a city where you are forbidden from building any straight road that has 6 intersections in a row. These are called P6-free graphs.

• The Paper's Discovery: For these specific cities, the authors found a fast, cubic-time algorithm.
• The Analogy: Think of the city as a building block structure. The authors realized that if you can't build a long straight line of 6 blocks, the whole structure must be built around a specific "core" shape (like a hexagon or a star).
  • Instead of checking every single road in the city, their algorithm finds this core shape first.
  • Once they find the core, they can predict exactly how the rest of the city must be colored (where to put the controllers) based on a few simple patterns.
  • This turns a problem that usually takes a lifetime to solve into something a computer can do in seconds, even for huge cities.

The "Three-Color" Secret Sauce

To solve this, the authors use a clever trick called 3-Coloring. They imagine painting every intersection in the city one of three colors:

• Black: The intersection is part of a "heavy" traffic zone (connected to multiple controllers).
• Yellow: The intersection is connected to exactly one controller.
• White: The intersection is far away from any controller.

The magic is that if you can paint the whole city correctly using these rules, you instantly know where to put the Traffic Controllers. The paper maps out every possible way to paint the "core" shapes (the hexagon or the star) and then shows how to extend that painting to the rest of the city without breaking the rules.

What Else Can This Do?

The authors didn't just stop at finding one solution. They showed how to tweak their fast algorithm to do three more things:

1. Weighted Version: If some roads are more expensive to patrol than others, the algorithm can find the cheapest way to set up the controllers.
2. Counting: It can count exactly how many different valid ways there are to set up the controllers.
3. Efficient Sets: It can also count how many ways you can set up the "Efficient" (perfectly non-touching) controllers, if they exist.

Summary

• The Bad News: For cities with no "Efficient" solution, checking for multiple "Perfect" solutions is computationally impossible to do quickly for general graphs.
• The Good News: If the city doesn't have long straight roads (P6-free), we have a super-fast, smart algorithm that finds the best solution, counts all possibilities, and handles costs, all by looking at the city's "skeleton" first.

It's like realizing that while you can't solve a jigsaw puzzle of a random cloud quickly, if the puzzle pieces only form a specific type of flower, you can solve it in your sleep because you know exactly where the petals go.

Technical Summary

Here is a detailed technical summary of the paper "Perfect Edge Domination in P6-free Graphs and in Graphs Without Efficient Edge Dominating Sets" by Grippo, Lin, and Vera.

1. Problem Definition and Context

The paper investigates two variations of the Edge Domination problem in undirected graphs:

• Efficient Edge Dominating Set (EED) / Dominating Induced Matching (DIM): A subset of edges $D$ such that every edge in the graph is dominated by exactly one edge in $D$. The paper notes that such a set may not exist for a given graph.
• Perfect Edge Dominating Set (PED-set): A subset of edges $P$ such that every edge outside $P$ is dominated by exactly one edge in $P$. Unlike DIMs, every graph admits at least one PED-set (the set of all edges, known as the trivial PED-set).

The authors focus on two specific decision and optimization problems:

1. Proper-PED: Deciding if a graph admits a proper PED-set (one that is neither the trivial set of all edges nor a DIM).
2. Minimum Weighted PED: Finding a PED-set with minimum cardinality (or minimum weight in the weighted version) for specific graph classes.

The study targets two distinct graph classes:

• DIM-less graphs: Graphs that do not admit any efficient edge dominating set.
• $P_6$-free graphs: Graphs that do not contain an induced path of 6 vertices.

2. Methodology

The authors employ a combination of complexity theory reductions and structural graph analysis to develop algorithms.

A. Complexity Analysis (DIM-less Graphs)

To address the complexity of the Proper-PED problem, the authors utilize a reduction from the DIM problem on Neighborhood Star-Free (NSF) graphs.

• NSF Graphs: Graphs where every vertex of degree $\ge 2$ belongs to a triangle.
• Reduction: They construct a gadget (a specific subgraph with 13 edges) attached to a vertex of maximum degree in a connected NSF graph $G$.
• Logic: They prove that $G$ has a DIM if and only if the constructed graph $G'$ has a non-trivial PED-set. Since finding a DIM in NSF graphs is NP-complete, this reduction establishes the hardness of the Proper-PED problem.

B. Algorithmic Approach ($P_6$-free Graphs)

For $P_6$-free graphs, the authors leverage a structural characterization theorem (Theorem 2.1):

A connected $P_6$-free graph contains either a dominating induced $C_6$ (cycle of length 6) or a dominating complete bipartite subgraph.

The proposed cubic-time algorithm ($O(n^3)$) proceeds as follows:

1. Pre-check: Attempt to find a DIM using existing linear-time algorithms for $P_7$-free graphs. If found, it is the optimal solution.
2. Structural Decomposition: Identify the dominating structure (Induced $C_6$ or Complete Bipartite Graph $K_{p,q}$).
3. Case Analysis & Coloring: The algorithm maps the PED-set problem to a valid 3-coloring of vertices:
   • Black ($B$): Vertices with $\ge 2$ incident edges in the PED-set.
   • Yellow ($Y$): Vertices with exactly 1 incident edge in the PED-set.
   • White ($W$): Vertices with 0 incident edges in the PED-set.
   • Constraints: $W$ must be an independent set; $Y$ vertices must have exactly one non-white neighbor; $B$ vertices cannot have white neighbors.
4. Enumeration:
   • Case 1 (Dominating $C_6$): Enumerate all valid partial 3-colorings of the $C_6$ (5 types). Extend these to the rest of the graph based on the domination properties of $P_6$-free graphs.
   • Case 2 (Dominating Bipartite $K$): Analyze three configurations based on the presence of Black vertices in the bipartition sets ($R, S$):
     • No Black vertices.
     • Exactly one Black vertex.
     • At least two Black vertices (implies $K$ is a star $K_{1,t}$).
   • For each configuration, the algorithm deterministically extends the partial coloring to the entire graph, checking validity and calculating the PED-set size/weight.

3. Key Contributions

1. NP-Completeness Result: The authors prove that deciding whether a connected DIM-less graph admits a proper PED-set is NP-complete. Consequently, deciding if a DIM-less graph has at least two PED-sets is also NP-complete.
2. Cubic-Time Algorithm for $P_6$-free Graphs: They present the first polynomial-time algorithm (specifically $O(n^3)$) to find a minimum cardinality PED-set for $P_6$-free graphs.
   • The algorithm relies on the structural decomposition of $P_6$-free graphs into dominating $C_6$ or bipartite subgraphs.
   • It handles the extension of partial 3-colorings efficiently.
3. Generalization to Weighted and Counting Problems: The framework is adapted to solve:
   • Weighted Minimum PED: Finding the PED-set with minimum total edge weight.
   • Counting PED-sets: Calculating the total number of distinct PED-sets in a $P_6$-free graph.
   • Counting DIMs: The algorithm can be modified to count DIMs in $P_6$-free graphs in cubic time.
4. Refinement of Existing Results: The work extends previous research on $P_k$-free graphs (where $k \ge 7$) and clarifies the complexity landscape for $P_6$-free graphs, which was previously an open problem for PED.

4. Results

• Complexity Dichotomy: The paper confirms that while finding a DIM is NP-complete for DIM-less graphs, finding a minimum PED-set is polynomial for $P_6$-free graphs.
• Algorithm Efficiency: The proposed algorithm runs in $O(n^3)$ time. If the dominating structure ($C_6$ or $K_{p,q}$) is provided as input, the runtime reduces to $O(n+m)$ (linear).
• Counting Capability: The counting version of the algorithm maintains the same time complexity, allowing for the enumeration of all solutions without exponential blowup.
• Weighted Adaptation: The algorithm successfully incorporates edge weights by converting them to vertex weights (via $\psi(u) = \sum \omega(uv)$) and maximizing the weight of the White set ($W$), which corresponds to minimizing the PED-set weight.

5. Significance

• Theoretical Advancement: This paper closes a significant gap in the complexity classification of the Perfect Edge Domination problem. While the problem is generally hard, identifying $P_6$-free graphs as a tractable class is a major theoretical contribution.
• Algorithmic Framework: The method of using valid 3-colorings (Black, Yellow, White) to model edge domination constraints provides a robust framework that can be adapted to other domination variants and graph classes.
• Practical Utility: The ability to count PED-sets and solve the weighted version in polynomial time for $P_6$-free graphs has implications for network design, resource allocation, and scheduling problems modeled by such graphs.
• Foundation for Future Work: By establishing the hardness for DIM-less graphs and the tractability for $P_6$-free graphs, the paper sets the stage for investigating $P_k$-free graphs for $k > 6$ and other hereditary graph classes.

In summary, the paper provides a comprehensive analysis of Perfect Edge Domination, proving its hardness in specific restricted classes (DIM-less) while delivering an efficient, versatile, and cubic-time algorithm for $P_6$-free graphs that solves the unweighted, weighted, and counting variants of the problem.