Efficient Vertex Cover Approximation via Iterative Dominating Set Transformations

Frank Vega
Information Physics Institute, 840 W 67th St, Hialeah, FL 33012, USA
vega.frank@gmail.com

Problem Statement

Vertex Cover Problem

Given an undirected graph $G=(V,E)$ , where $V$ is the set of vertices and $E$ is the set of edges, the Vertex Cover Problem seeks to find a subset $C\subseteq V$ of minimum size such that for every edge $(u,v)\in E$ , at least one of the endpoints $u$ or $v$ is in $C$ . In other words, $C$ "covers" all edges by ensuring each edge is incident to at least one vertex in $C$ . The goal is to minimize $|C|$ , the size of the vertex cover. This is an NP-hard problem, and the provided algorithm computes an approximate solution.

• Input: An undirected graph $G=(V,E)$ .
• Output: A subset $C\subseteq V$ such that for every $(u,v)\in E$ , $u\in C$ or $v\in C$ , with $|C|$ as small as possible.

Dominating Set Problem

Given an undirected graph H=(VH,EH)H = (V_H, E_H)H=(VH​,EH​) , the Dominating Set Problem aims to find a subset D⊆VHD \subseteq V_HD⊆VH​ of minimum size such that every vertex in VHV_HVH​ is either in $D$ or adjacent to a vertex in $D$ . Formally, for every vertex v∈VHv \in V_Hv∈VH​ , either $v\in D$ , or there exists some $u\in D$ such that (u,v)∈EH(u, v) \in E_H(u,v)∈EH​ . The objective is to minimize $|D|$ , the size of the dominating set. This problem is also NP-hard, and the algorithm leverages a 2-approximation method (alg.find_dominating_set) to solve it as a subroutine for the vertex cover problem. The alg.find_dominating_set algorithm is detailed in the article Bipartite-Based 2-Approximation for Dominating Sets in General Graphs.

• Input: An undirected graph H=(VH,EH)H = (V_H, E_H)H=(VH​,EH​) .
• Output: A subset D⊆VHD \subseteq V_HD⊆VH​ such that every vertex in VHV_HVH​ is either in $D$ or has a neighbor in $D$ , with $|D|$ as small as possible.

Algorithm Overview

Consider the algorithm implemented in Python:

import networkx as nx
import baldor.algorithm as alg

def find_vertex_cover(graph):
    """
    Compute an approximate minimum vertex cover set for an undirected graph by transforming it into a chordal graph.

    Args:
        graph (nx.Graph): A NetworkX Graph object representing the input graph.

    Returns:
        set: A set of vertex indices representing the minimum vertex cover set.
             Returns an empty set if the graph is empty or has no edges.
    """
    # Check if the input graph is a valid undirected NetworkX Graph; raises an error if not.
    if not isinstance(graph, nx.Graph):
        raise ValueError("Input must be an undirected NetworkX Graph.")

    # Handle edge cases: return an empty set if the graph has no nodes or no edges, as no vertex cover is needed.
    if graph.number_of_nodes() == 0 or graph.number_of_edges() == 0:
        return set()

    # Identify and remove isolated nodes (nodes with degree 0) since they cannot be part of a vertex cover.
    isolated_nodes = list(nx.isolates(graph))
    graph.remove_nodes_from(isolated_nodes)

    # After removing isolated nodes, if the graph is empty, return an empty set (no vertex cover needed).
    if graph.number_of_nodes() == 0:
        return set()

    # Initialize an empty set to store the approximate vertex cover.
    approximate_vertex_cover = set()

    # Create a working copy of the graph to iteratively modify during the vertex cover computation.
    iterative_graph = graph.copy()

    # Continue iterating until the current set forms a vertex cover for the original graph.
    while not utils.is_vertex_cover(graph, approximate_vertex_cover):

        # Create a new bipartite graph to transform the current iterative graph for dominating set computation.
        new_graph = nx.Graph()

        # Construct the new bipartite graph by creating tuple nodes for each vertex and edge.
        for i in iterative_graph.nodes():
            for j in iterative_graph.neighbors(i):
                if i < j:  # Ensure each edge (i, j) is processed only once by ordering i < j.
                    # Add edges to represent the bipartite structure:
                    # (i, i) to (i, j): vertex i's representative to edge (i, j).
                    # (j, j) to (i, j): vertex j's representative to edge (i, j).
                    # (i, i) to (j, j): connect the vertex representatives.
                    new_graph.add_edge((i, i), (i, j))
                    new_graph.add_edge((j, j), (i, j))
                    new_graph.add_edge((i, i), (j, j))

        # Use Baldor's 2-approximation algorithm to find a dominating set in the new bipartite graph.
        # This dominating set corresponds to a vertex cover in the original graph via the transformation.
        tuple_vertex_cover = alg.find_dominating_set(new_graph)

        # Extract vertices from the dominating set where the tuple node is of the form (i, i),
        # meaning the vertex i is selected for the vertex cover; update the approximate vertex cover.
        approximate_vertex_cover.update({tuple_node[0] 
                                for tuple_node in tuple_vertex_cover 
                                if tuple_node[0] == tuple_node[1]})

        # Reconstruct the iterative graph using edges from the dominating set where tuple nodes
        # are of the form (i, j) with i != j, representing remaining edges to cover.
        iterative_graph = nx.Graph()
        iterative_graph.add_edges_from({tuple_node 
                                  for tuple_node in tuple_vertex_cover 
                                  if tuple_node[0] != tuple_node[1]})

    # Return the computed approximate vertex cover set.
    return approximate_vertex_cover

The find_vertex_cover(graph) algorithm computes an approximate minimum vertex cover for an undirected graph $G=(V,E)$ by transforming the vertex cover problem into a series of dominating set problems. Here's a step-by-step breakdown:

• Input Validation and Edge Cases:

  • Ensures the input is an undirected NetworkX graph.
  • Returns an empty set if the graph has no nodes or edges (no vertex cover needed).
  • Removes isolated nodes, as they cannot be part of a vertex cover.

• Iterative Process:

  • Initializes an empty vertex cover set $C$ .
  • Maintains an iterative_graph, initially a copy of $G$ , representing the subgraph of uncovered edges.
  • While $C$ is not a vertex cover for $G$ :
  • Transformation to Bipartite Graph $H$ :
    • For each vertex $i\in V$ , create a vertex $(i,i)$ .
    • For each edge $(i,j)\in E$ (with $i<j$ ), create a vertex $(i,j)$ .
    • Add edges: $((i,i),(i,j))$ , $((j,j),(i,j))$ , and $((i,i),(j,j))$ .
  • Dominating Set Computation:
    • Use alg.find_dominating_set to compute a 2-approximation dominating set $D$ in $H$ . For a deep dive into this algorithm, check out the article Bipartite-Based 2-Approximation for Dominating Sets in General Graphs, which provides a thorough explanation.
    • Extract vertices $i$ where $(i,i)\in D$ , adding them to $C$ .
  • Update Iterative Graph:
    • Reconstruct iterative_graph with edges $(i,j)$ where $(i,j)\in D$ , representing edges not yet covered.
  • Return $C$ as the approximate vertex cover.

The transformation leverages the fact that a dominating set in $H$ corresponds to a vertex cover in iterative_graph, and the iterative process ensures all edges in $G$ are eventually covered.

Runtime Analysis

Let $n=|V|$ (number of vertices) and $m=|E|$ (number of edges) in the input graph $G$ .

• Initial Setup:

  • Input validation and isolated node removal: $O(n+m)$ using NetworkX operations.
  • Copying the graph: $O(n+m)$ .

• Main Loop:

  • Number of Iterations: In the worst case, each iteration covers at least one edge. If an iteration selects one vertex to cover one edge, there can be up to $m$ iterations. However, since alg.find_dominating_set selects a dominating set, it typically covers multiple edges per iteration, often closer to $O(\log m)$ iterations in practice (similar to greedy set cover).
  • Per Iteration:
  • Constructing $H$ :
    • Vertices in $H$ : $O(n)$ for $(i,i)$ , $O(m)$ for $(i,j)$ , total $O(n+m)$ .
    • Edges in $H$ : For each edge $(i,j)$ , add three edges ( $((i,i),(i,j))$ , $((j,j),(i,j))$ , $((i,i),(j,j))$ ), so $O(m)$ edges.
    • Construction time: $O(n+m)$ .
  • Running alg.find_dominating_set:
    • alg.find_dominating_set uses the greedy algorithm with mirror strategy, as previously described, with runtime O(∣VH∣⋅log⁡∣VH∣+∣EH∣)O(|V_H| \cdot \log |V_H| + |E_H|)O(∣VH​∣⋅log∣VH​∣+∣EH​∣) .
    • ∣VH∣=O(n+m)|V_H| = O(n + m)∣VH​∣=O(n+m) , ∣EH∣=O(m)|E_H| = O(m)∣EH​∣=O(m) , so runtime per call is $O((n+m)\cdot \log (n+m)+m)$ .
  • Updating $C$ and iterative_graph:
    • Extracting vertices from $D$ : $O(|D|)$ , where ∣D∣≤∣VH∣=O(n+m)|D| \leq |V_H| = O(n + m)∣D∣≤∣VH​∣=O(n+m) .
    • Reconstructing iterative_graph: $O(m)$ .
  • Total per iteration: Dominated by $O((n+m)\cdot \log (n+m)+m)$ .

• Total Runtime:

  • Worst case: $O(m)$ iterations, each taking $O((n+m)\cdot \log (n+m)+m)$ , so O(((n+m)⋅log⁡(n+m)+m)⋅m)=O(m2+m⋅(n+m)⋅log⁡(n+m))O(((n + m) \cdot \log (n + m) + m) \cdot m) = O(m^2 + m \cdot (n + m) \cdot \log (n + m))O(((n+m)⋅log(n+m)+m)⋅m)=O(m2+m⋅(n+m)⋅log(n+m)) .
  • In practice: Often fewer iterations (e.g., $O(\log m)$ ), reducing the runtime to $O(((n+m)\cdot \log (n+m)+m)\cdot \log m)$ .

Approximation Ratio: Less Than 2 When Dominating Set Ratio Is Less Than 2

The algorithm’s approximation ratio depends on alg.find_dominating_set:

• Standard Case:

  • As proven previously, alg.find_dominating_set provides a 2-approximation for the dominating set problem, i.e., ∣D∣≤2⋅∣D∣|D| \leq 2 \cdot |D^{}|∣D∣≤2⋅∣D∣ , where DD^{}D is the minimum dominating set in $H$ .
  • The vertex cover $C$ extracted from $D$ satisfies $|C|\le |D|$ , since $C=\{i\mid (i,i)\in D\}$ .
  • The transformation ensures ∣D∣≤2⋅∣C∣|D^{}| \leq 2 \cdot |C^{}|∣D∣≤2⋅∣C∣ , where C∗C^{*}C∗ is the minimum vertex cover of $G$ , because each edge requires at least one vertex, and the bipartite structure may double the representation.
  • Iteratively, the total size of approximate_vertex_cover is at most 2⋅∣C∗∣2 \cdot |C^{*}|2⋅∣C∗∣ , as the 2-approximation applies per iteration, but edges are covered exactly once across iterations.

• Improved Ratio:

  • If alg.find_dominating_set achieves an approximation ratio $\alpha <2$ , i.e., ∣D∣≤α⋅∣D∗∣|D| \leq \alpha \cdot |D^{*}|∣D∣≤α⋅∣D∗∣ , the overall vertex cover approximation improves.
  • Per iteration, ∣Citer∣≤∣D∣≤α⋅∣D∗∣|C_{\text{iter}}| \leq |D| \leq \alpha \cdot |D^{*}|∣Citer​∣≤∣D∣≤α⋅∣D∗∣ .
  • Since ∣D∣≤2⋅∣Citer∣|D^{}| \leq 2 \cdot |C^{}{\text{iter}}|∣D∣≤2⋅∣Citer∣ (where C∗iterC^{*}{\text{iter}}C∗iter is the minimum vertex cover for the current iterative_graph), the total size of approximate_vertex_cover across iterations becomes:
    ∣C∣≤α⋅∣D∣≤α⋅2⋅∣Citer∣|C| \leq \alpha \cdot |D^{}| \leq \alpha \cdot 2 \cdot |C^{}_{\text{iter}}| ∣C∣≤α⋅∣D∣≤α⋅2⋅∣Citer​∣
  • However, the iterative process ensures that each edge is covered exactly once, and the effective ratio aligns with the dominating set ratio:
    ∣C∣≤α⋅∣C∗∣.|C| \leq \alpha \cdot |C^{*}|. ∣C∣≤α⋅∣C∗∣.
  • Thus, if the dominating set ratio
    $$\alpha <2,$$

    the vertex cover approximation ratio is also

    $$\alpha <2.$$

Research Data

A Python implementation, titled Varela: Approximate Vertex Cover Solver—in tribute to the Cuban Catholic priest Felix Varela y Morales—has been developed to efficiently solve the Approximate Vertex Cover Problem. This implementation is publicly accessible through the Python Package Index (PyPI): https://pypi.org/project/varela/. By constructing an approximate solution, the algorithm guarantees an approximation ratio of at most 2 for the Vertex Cover Problem.

Table: Code Metadata

Implications of Approximating Vertex Cover with a Factor Smaller Than 2

If an algorithm could consistently approximate solutions to the Vertex Cover problem within any constant factor smaller than 2, it would have profound implications for computational complexity theory. Such a breakthrough would imply that the Unique Games Conjecture (UGC) is false. The UGC is a cornerstone of theoretical computer science, significantly influencing our understanding of approximation algorithms and the hardness of approximation. Falsifying the UGC would fundamentally reshape these fields. Specifically:

• Impact on Hardness Results: Many hardness-of-approximation results depend on the UGC. If the conjecture were disproven, these results would need re-evaluation, potentially leading to new algorithms for problems previously considered inapproximable.

• New Algorithmic Techniques: The failure of the UGC would pave the way for novel algorithmic techniques and approaches, facilitating progress on long-standing open problems in optimization and related areas.

• Broader Scientific Implications: The UGC has connections to disciplines beyond computer science, including mathematics, physics, and economics. Resolving the conjecture would create ripple effects across these fields, encouraging interdisciplinary research and innovation.

Therefore, the development of our algorithm not only pushes the boundaries of vertex cover approximation but also contributes to fundamental questions in computational complexity, with wide-reaching scientific impacts.

Conclusion: The algorithm guarantees a vertex cover with an approximation ratio matching the dominating set algorithm’s ratio, which is 2 in the standard case but reduces to $\alpha <2$ if alg.find_dominating_set performs better.