Mendive: Fast Claw Detection in Sparse Graphs

Fast Claw Detection in Sparse Graphs

Frank Vega
Information Physics Institute, 840 W 67th St, Hialeah, FL 33012, USA
[e-mail]

Introduction to the Claw Finding Problem

In graph theory, a claw is a specific structure in an undirected graph, also known as a $K_{1,3}$ graph. It consists of one central vertex (the "center") connected to three other vertices (the "leaves"), where the leaves are not connected to each other. Imagine a star with a hub city and three isolated towns connected only to the hub—that’s a claw! Formally, for a vertex set $(u, \{v, w, x\})$ , a claw exists if $u$ (the center) is connected to $v, w, x$ , but there are no edges among $v, w, x$ .

The Claw Finding Problem asks:

• Input: An undirected graph $G = (V, E)$ , where $|V| = n$ (number of vertices) and $|E| = m$ (number of edges).
• Output:
  • For the decision version: Determine if at least one claw exists.
  • For the listing version: Return all sets of four vertices $(\text{center}, \{ \text{leaf1}, \text{leaf2}, \text{leaf3} \})$ forming claws.

This problem is significant in network analysis (e.g., detecting specific patterns in social or biological networks) and is related to other graph problems like triangle detection. Finding claws efficiently is challenging because it requires identifying a vertex with at least three neighbors that form an independent set (no edges among them).

The algorithm presented here leverages the aegypti package’s linear-time triangle-finding algorithm to solve the Claw Finding Problem efficiently. This novel algorithm is designated Mendive. By checking for triangles in the complement of a node’s neighbor-induced subgraph, it identifies independent sets of three vertices, which, combined with the central vertex, form claws. Explore more details about the Aegypti algorithm in the following article:

📖 The Aegypti Algorithm

Implementation

Below is the Python implementation using NetworkX and the aegypti package’s triangle-finding algorithm.

import networkx as nx
import aegypti.algorithm as algo

def find_claw_coordinates(graph, first_claw=True):
    """
    Finds the coordinates of all claws in a given undirected NetworkX graph.

    Args:
        graph: An undirected NetworkX graph.
        first_claw: A boolean indicating whether to return only the first found claw.

    Returns:
        A list of sets, where each set represents the coordinates of a claw.
        Each claw is represented as a set of 4 vertex indices: (center, {leaf1, leaf2, leaf3})
        Returns None if no claws are found.
    """
    # Ensure the input is a valid undirected NetworkX graph
    if not isinstance(graph, nx.Graph):
        raise ValueError("Input must be an undirected NetworkX Graph.")

    # Initialize a set to store unique claws, each as a frozenset of 4 vertices
    claws = set()

    # Iterate over each node in the graph as a potential center of a claw
    for i in graph.nodes():
        # Skip nodes with fewer than 3 neighbors, as a claw requires a center with degree at least 3
        if graph.degree(i) < 3:
            continue

        # Get all neighbors of the current node i
        neighbors = graph.neighbors(i)

        # Create an induced subgraph containing only the neighbors of i
        neighbor_subgraph = graph.subgraph(neighbors)

        # Compute the complement of the neighbor subgraph
        # In the complement, an edge exists if the original graph has no edge between those neighbors
        neighbor_complement = nx.complement(neighbor_subgraph)

        # Use the aegypti algorithm to find triangles in the complement graph
        # A triangle in the complement means the three vertices form an independent set in the original graph
        # This is key: three independent neighbors of i, plus i, form a claw
        triangles = algo.find_triangle_coordinates(neighbor_complement, first_claw)

        # If no triangles are found, no claw exists with i as the center
        if triangles is None:
            continue

        # If only the first claw is needed, take one triangle and form a claw
        elif first_claw:
            triangle = triangles.pop()
            claws = {(i, triangle)}  # Combine the triangle (3 leaves) with center i
            break  # Stop after finding the first claw

        # Otherwise, collect all claws by combining each triangle with center i
        else:
            claws.update({(i, triangle) for triangle in triangles})

    # Return the list of claws, or None if none were found
    return list(claws) if claws else None

Basis in the Aegypti Algorithm

This implementation relies on the aegypti package (available at PyPI: aegypti), which provides a linear-time triangle-finding algorithm with a runtime of $O(n + m)$ . The key insight is that a claw’s three leaf vertices form an independent set in the original graph, which corresponds to a triangle in the complement graph of those vertices. By applying aegypti’s find_triangle_coordinates function to the complement of the induced subgraph of a node’s neighbors, the algorithm efficiently identifies claws.

The aegypti algorithm’s ability to detect triangles in $O(n + m)$ time is critical, as it ensures that the triangle-finding step for each node’s neighbor set is fast, contributing to the overall efficiency of claw detection.

---

Runtime Analysis

Let’s analyze the runtime of find_claw_coordinates for both first_claw=True (decision version) and first_claw=False (listing version).

Notation

• $n = |V|$ : Number of vertices.
• $m = |E|$ : Number of edges.
• $\text{deg}(i)$ : Degree of vertex $i$ .
• $\Delta$ : Maximum degree in the graph.
• For a node $i$ , the induced subgraph of its neighbors has:
  • $n' = \text{deg}(i)$ vertices.
  • $m' \leq \binom{\text{deg}(i)}{2}$ edges in the original subgraph, and up to $\binom{\text{deg}(i)}{2}$ edges in its complement.

Case 1: first_claw=True (Find One Claw)

• Outer Loop:
  • Iterates over nodes until a claw is found, at most $n$ iterations.
  • Checking graph.degree(i) is $O(1)$ in NetworkX.
• Per Node i:
  • Skip if $\text{deg}(i) < 3$ : $O(1)$ .
  • Create neighbors: $O(\text{deg}(i))$ .
  • Induced subgraph: $O(\text{deg}(i) + m')$ , where $m' \leq \binom{\text{deg}(i)}{2}$ .
  • Complement graph: $O(\binom{\text{deg}(i)}{2}) = O(\text{deg}(i)^2)$ .
  • Run aegypti.find_triangle_coordinates with first_claw=True: $O(n' + m') = O(\text{deg}(i) + \text{deg}(i)^2) = O(\text{deg}(i)^2)$ .
  • Process triangle (if found): $O(1)$ (union and set operations).
  • Break after first claw: Stops after finding one.
• Worst Case:
  • No claws exist, so check all nodes.
  • Total: $\sum_i O(\text{deg}(i)^2)$ .
  • By the Handshaking Lemma, $\sum_i \text{deg}(i) = 2m$ .
  • Worst case: $\sum_i \text{deg}(i)^2 \leq \Delta \cdot \sum_i \text{deg}(i) = \Delta \cdot 2m = O(m \cdot \Delta)$ .
  • In sparse graphs ( $m = O(n)$ , $\Delta = O(n)$ ): $O(n^2)$ .
  • In dense graphs ( $m = O(n^2)$ , $\Delta = O(n)$ ): $O(n^3)$ .
• Best Case:
  • Finds a claw at the first node with $\text{deg}(i) = O(1)$ , so $O(1)$ .

Case 2: first_claw=False (List All Claws)

• Outer Loop: Iterates over all $n$ nodes.
• Per Node i:
  • Same as above: $O(\text{deg}(i)^2)$ for subgraph, complement, and triangle finding.
  • aegypti lists all triangles in the complement: Still $O(\text{deg}(i) + m') = O(\text{deg}(i)^2)$ , but processes all triangles (output-sensitive).
  • For each triangle, form a claw: $O(1)$ per triangle, up to $\binom{\text{deg}(i)}{3}$ triangles.
  • Total per node: $O(\text{deg}(i)^2 + \text{\#triangles})$ .
• Total:
  • Sum over all nodes: $\sum_i O(\text{deg}(i)^2) = O(m \cdot \Delta)$ .
  • Output size: Up to $\sum_i \binom{\text{deg}(i)}{3}$ claws, which could be $O(n^3)$ in a complete graph.
  • Total time: $O(m \cdot \Delta + \text{\#claws})$ .
  • Sparse graphs: $O(n^2) + \text{output size}$ .
  • Dense graphs: $O(n^3) + \text{output size}$ .

Summary

• Decision (first_claw=True): $O(m \cdot \Delta)$ , efficient for sparse graphs, but not linear in $n + m$ .
• Listing (first_claw=False): $O(m \cdot \Delta + \text{\#claws})$ , output-sensitive, dominated by the number of claws in dense graphs.

---

Algorithmic Approach for Identifying Claw-Free Graphs

Algorithm Description

The concept of a claw-free graph—where no induced subgraph forms a $K_{1,3}$ (a central vertex connected to three non-adjacent leaves)—is a key focus in graph theory. Research by Kloks, Kratsch, and Müller (2000) (Kloks, Ton, Kratsch, Dieter, Müller, Haiko. "Finding and counting small induced subgraphs efficiently." Information Processing Letters, 74, no. 3-4 (2000): 115–121. doi:10.1016/S0020-0190(00)00047-8) noted that in any claw-free graph, each vertex has at most $2\sqrt{m}$ neighbors. This stems from Turán's theorem, which suggests that if a vertex had more neighbors, their induced subgraph would contain a triangle in its complement, implying the presence of a claw.

This observation has algorithmic consequences:

• The neighborhood check in the fast matrix multiplication-based algorithm can be performed in the same asymptotic time as multiplying two $2\sqrt{m} \times 2\sqrt{m}$ matrices.
• Vertices with even lower degrees allow for faster computation.

Worst-case scenario:

When $\Omega(\sqrt{m})$ vertices each have $\Omega(\sqrt{m})$ neighbors (and the rest have few neighbors), the total time complexity becomes

$$O(m^{3.372/2}) = O(m^{1.686}).$$

Our solution adapts this insight using the find_claw_coordinates algorithm with first_claw=True, leveraging the aegypti package’s linear-time triangle detection.

Key Steps:

1. Neighborhood Analysis:

   • For each vertex $i$ , extract the induced subgraph of its neighbors and compute its complement.
   • The complement’s triangle-free nature (due to claw-freeness) is checked using aegypti’s find_triangle_coordinates.

2. Claw Detection:

   • If no triangles are found in the complement (indicating no independent set of three among neighbors), the vertex cannot be the center of a claw.
   • With first_claw=True, the algorithm stops after detecting the first claw (if any), allowing us to determine if the graph is claw-free by checking all vertices.

3. Claw-Free Verification:

   • A graph is claw-free if find_claw_coordinates returns None after inspecting all vertices, confirming no claws exist.

---

Runtime Analysis

Our algorithm’s runtime benefits from the aegypti package’s efficient triangle detection, tailored to the claw-free context where neighbor degrees are bounded.

Notation:

• $n = |V|$ : Number of vertices.
• $m = |E|$ : Number of edges.
• $\text{deg}(i)$ : Degree of vertex $i$ .
• $\Delta$ : Maximum degree, bounded by $2\sqrt{m}$ in claw-free graphs.

Runtime for first_claw=True:

• Process: Iterates over all $n$ vertices, checking each for a potential claw.
• Per Vertex $i$ :
  • Subgraph and complement construction: $O(\text{deg}(i)^2)$ .
  • aegypti triangle detection in the complement: $O(\text{deg}(i)^2)$ , since the complement has $\text{deg}(i)$ vertices and up to $\binom{\text{deg}(i)}{2}$ edges.
  • Total per vertex: $O(\text{deg}(i)^2)$ .
• Total:
  • Worst case: All vertices have $\text{deg}(i) \leq 2\sqrt{m}$ .
  • Sum of costs: $\sum_i O(\text{deg}(i)^2) \leq \sum_i (2\sqrt{m})^2 = n \cdot 4m$ .
  • However, the degree sum $\sum_i \text{deg}(i) = 2m$ , and $\text{deg}(i)^2 \leq (2\sqrt{m})^2 = 4m$ , so $\sum_i \text{deg}(i)^2 \leq \Delta \cdot 2m$ .
  • With $\Delta \leq 2\sqrt{m}$ , the total is $O(m \cdot 2\sqrt{m}) = O(m^{3/2})$ .
• Conclusion:
  $$O(m^{3/2}),$$

  significantly better than the

  $$O(m^{1.686})$$

  of matrix multiplication-based methods, especially in sparse claw-free graphs.

Special Case: Claw-Free Graphs

• If the graph is claw-free, no triangles are found in any complement subgraph, and the algorithm completes the full iteration.
• Runtime remains $O(m^{3/2})$ , as it depends on the bounded degree $2\sqrt{m}$ and total edge checks.

---

Impact of the General Claw-Free Recognition Algorithm

This claw-free detection method, powered by the aegypti package, offers notable advantages such as:

1. Efficiency Gain:

   • Outperforms the $O(m^{1.686})$ matrix multiplication approach by Kloks et al. (2000), achieving $O(m^{3/2})$ due to aegypti’s linear-time triangle detection within bounded subgraphs.
   • Ideal for sparse graphs where $m = O(n)$ , reducing to $O(n^{3/2})$ .

2. Practical Accessibility:

   • Available via pip install aegypti, it’s easy to deploy in Python environments for network analysis or graph validation tasks.

3. Theoretical Promise:

   • If aegypti’s $O(n + m)$ claim holds against 3SUM-hard instances, this could challenge fine-grained complexity barriers (e.g., sparse triangle hypothesis), suggesting new bounds for claw-free recognition.
   • Enhances research into graph properties like perfect graphs or chordal graphs, where claw-freeness is relevant.

4. Limitations:

   • The $O(m^{3/2})$ bound assumes the $2\sqrt{m}$ degree limit; dense graphs near $m = n^2$ may push $\Delta$ higher, increasing runtime.
   • Relies on aegypti’s linear-time claim for full validation.

In summary, this algorithm provides a practical and potentially groundbreaking tool for verifying claw-free graphs, leveraging aegypti’s efficiency to surpass traditional methods.

---

The Algorithm’s Overall Impact

This claw-finding algorithm is significant for several reasons:

1. Leverages Aegypti’s Breakthrough:

   • The aegypti algorithm’s claimed $O(n + m)$ triangle detection (potentially challenging fine-grained complexity barriers like the sparse triangle hypothesis) makes the claw-finding step per node highly efficient.
   • By applying linear-time triangle finding to small complement subgraphs, it achieves good performance for each node’s neighbor set.

2. Practical Efficiency:

   • Available via pip install aegypti, it’s accessible for real-world applications in network analysis, bioinformatics, and social network pattern detection.
   • The algorithm is straightforward to integrate with NetworkX, a popular graph library.

3. Theoretical Implications:

   • If aegypti’s linear-time triangle finding holds against 3SUM-hard instances, this claw-finding algorithm could contribute to broader breakthroughs in graph algorithms.
   • Claw detection is related to problems like independent set detection, so improvements here may inspire new approaches elsewhere.

4. Limitations:

   • The runtime depends on the maximum degree $\Delta$ , making it less efficient in dense graphs compared to aegypti’s triangle finding.
   • The listing version’s output size can dominate, limiting scalability in graphs with many claws.

5. Availability and Deployment:

   • The tool is deployed via mendive (available on PyPI), making it readily accessible for real-world applications.
   • You can access the tool at Mendive: Claw-Free Solver.

---

Conclusion

In summary, this algorithm showcases the power of aegypti’s triangle-finding efficiency, extending it to a new problem. While not linear-time itself due to the degree-dependent terms, it’s a practical and theoretically interesting approach that could spark further research, especially if aegypti proves to be a complexity breakthrough.