Maximum Weighted Clique

The Maximum Weighted Clique (MWC) problem is an extension of the Maximum Clique problem where each vertex has an associated weight. The goal is to find a clique (a fully connected subgraph) with the maximum total weight.

Problem Definition

Given an undirected graph with a weight function , find a subset such that:

1. Every pair of vertices in is connected by an edge (clique property)
2. The sum of weights is maximized

Complexity

The MWC problem is NP-hard, being a generalization of the already NP-hard maximum clique problem. The problem becomes even more challenging with weights, as the greedy strategies that work well for unweighted cases may perform poorly.

Algorithms

1. Branch and Bound Algorithm

code.py
1def max_weighted_clique(graph, weights):
2    n = len(graph)
3    best_weight = 0
4    best_clique = []
5    
6    def is_connected_to_all(vertex, clique):
7        return all(graph[vertex][v] for v in clique)
8    
9    def branch_and_bound(candidates, current_clique, current_weight):
10        nonlocal best_weight, best_clique
11        
12        # Update best solution if current is better
13        if current_weight > best_weight:
14            best_weight = current_weight
15            best_clique = current_clique.copy()
16        
17        # Upper bound calculation
18        potential = current_weight + sum(weights[v] for v in candidates)
19        if potential <= best_weight:
20            return
21        
22        # Try adding each candidate
23        for v in candidates:
24            if is_connected_to_all(v, current_clique):
25                new_candidates = [u for u in candidates 
26                                if u > v and graph[v][u]]
27                branch_and_bound(new_candidates, 
28                               current_clique + [v],
29                               current_weight + weights[v])
30    
31    initial_candidates = list(range(n))
32    branch_and_bound(initial_candidates, [], 0)
33    return best_clique, best_weight

2. Greedy Approximation

code.py
1def greedy_weighted_clique(graph, weights):
2    n = len(graph)
3    clique = []
4    vertices = list(range(n))
5    # Sort vertices by weight
6    vertices.sort(key=lambda v: weights[v], reverse=True)
7    
8    for v in vertices:
9        # Check if v can be added to clique
10        if all(graph[v][u] for u in clique):
11            clique.append(v)
12    
13    return clique, sum(weights[v] for v in clique)

Advanced Techniques

1. Color-based Branch and Bound

This technique uses graph coloring to improve the upper bound:

code.py
1def color_based_bound(graph, weights, vertices):
2    colors = {}
3    weight_bounds = []
4    
5    for v in vertices:
6        # Find first available color
7        used_colors = {colors[u] for u in graph[v] 
8                      if u in colors}
9        color = 0
10        while color in used_colors:
11            color += 1
12        colors[v] = color
13        
14        # Update weight bounds for each color
15        while len(weight_bounds) <= color:
16            weight_bounds.append(0)
17        weight_bounds[color] = max(weight_bounds[color], 
18                                 weights[v])
19    
20    return sum(sorted(weight_bounds, reverse=True))

Applications

1. Social Network Analysis: Finding closely connected groups with weighted importance
2. Portfolio Optimization: Selecting groups of compatible investments
3. Pattern Recognition: Identifying strongly related features
4. Molecular Biology: Protein interaction network analysis
5. Market Analysis: Finding groups of related products with weights based on profitability

Implementation Considerations

1. Graph Representation

   • Adjacency matrix for dense graphs
   • Adjacency list for sparse graphs
   • Bit-parallel operations for efficiency

2. Weight Handling

   • Efficient weight storage and access
   • Handling floating-point precision
   • Normalization techniques

3. Performance Optimization

   • Vertex ordering heuristics
   • Pruning strategies
   • Parallel processing for large graphs

Time and Space Complexity

1. Exact Solution (Branch and Bound)

   • Time Complexity: worst case
   • Space Complexity:

2. Greedy Approximation

   • Time Complexity:
   • Space Complexity:

3. Color-based Branch and Bound

   • Time Complexity: worst case
   • Space Complexity:

Where is the number of vertices.

Theoretical Bounds

1. Approximation Hardness

   • Cannot be approximated within factor unless P = NP
   • Best known polynomial-time approximation ratio:

2. Special Cases

   • Perfect graphs: Polynomial time solvable
   • Planar graphs: Remains NP-hard
   • Bipartite graphs: Polynomial time solvable

Best Practices

1. Input Validation

   • Check graph connectivity
   • Verify weight positivity
   • Handle special cases

2. Solution Verification

   • Confirm clique property
   • Validate weight calculations
   • Check optimality conditions

3. Performance Monitoring

   • Track computation time
   • Memory usage optimization
   • Solution quality metrics"