🧮Combinatorial Optimization Unit 2 – Graph Theory and Algorithms

Key Concepts and Terminology

• Graphs consist of vertices (nodes) connected by edges (links) representing relationships or connections between entities
• Directed graphs (digraphs) contain edges with a specific direction, while undirected graphs have edges without a direction
• Weighted graphs assign values (weights) to edges, representing costs, distances, or capacities
• Degree of a vertex refers to the number of edges incident to it, with in-degree and out-degree for directed graphs
• Paths are sequences of vertices connected by edges, with simple paths having no repeated vertices
  • Cycles are paths that start and end at the same vertex
  • Connected graphs have a path between every pair of vertices
• Trees are connected acyclic graphs, while forests are disjoint sets of trees
• Bipartite graphs divide vertices into two disjoint sets, with edges only between sets
• Planar graphs can be drawn on a plane without edge crossings, while non-planar graphs require edge crossings

Graph Representations and Properties

• Adjacency matrix represents a graph using a square matrix, with entries indicating edge presence or weight
  • Space complexity of $O(V^2)$, suitable for dense graphs
  • Edge existence and weight lookup in constant time $O(1)$
• Adjacency list stores a graph as an array of lists, with each list containing the neighbors of a vertex
  • Space complexity of $O(V+E)$, efficient for sparse graphs
  • Allows for efficient traversal of a vertex's neighbors
• Edge list is a simple representation storing a list of edges, each represented as a pair of vertices
• Incidence matrix represents the relationship between vertices and edges, with rows for vertices and columns for edges
• Graph density measures the ratio of actual edges to the maximum possible edges, with sparse and dense graphs
• Connectivity properties include connected components, strongly connected components (SCCs) in directed graphs, and bridges/articulation points
• Graph isomorphism determines if two graphs are structurally equivalent, with efficient algorithms for special cases

Basic Graph Algorithms

• Breadth-First Search (BFS) traverses a graph level by level, exploring all neighbors before moving to the next level
  • Finds shortest paths in unweighted graphs and connected components
  • Time complexity of $O(V+E)$ using a queue data structure
• Depth-First Search (DFS) explores a graph by going as deep as possible before backtracking
  • Useful for cycle detection, topological sorting, and finding strongly connected components
  • Implemented using a stack or recursion, with time complexity $O(V+E)$
• Topological sorting orders the vertices of a directed acyclic graph (DAG) such that for every directed edge $(u,v)$, $u$ comes before $v$
  • Kahn's algorithm and DFS-based approaches are common
• Minimum Spanning Tree (MST) algorithms (Kruskal's, Prim's) find a tree that connects all vertices with minimum total edge weight
  • Kruskal's algorithm sorts edges by weight and adds them greedily, avoiding cycles
  • Prim's algorithm grows the MST from a starting vertex, adding the cheapest connected edge at each step
• Shortest path algorithms (Dijkstra's, Bellman-Ford) find paths with minimum total weight between vertices
  • Dijkstra's algorithm uses a priority queue and greedy approach for non-negative weights
  • Bellman-Ford handles negative weights and detects negative cycles

Advanced Graph Algorithms

• Floyd-Warshall algorithm finds shortest paths between all pairs of vertices using dynamic programming
  • Computes a distance matrix in $O(V^3)$ time, handling negative weights but not negative cycles
• Johnson's algorithm combines Bellman-Ford and Dijkstra's algorithms for sparse graphs with negative weights
  • Reweights edges to eliminate negative weights, then runs Dijkstra's from each vertex
• Maximum flow algorithms (Ford-Fulkerson, Edmonds-Karp) find the maximum flow through a network from source to sink
  • Ford-Fulkerson uses augmenting paths to increase flow, with Edmonds-Karp using BFS for better performance
• Minimum cut algorithms (Karger's, Stoer-Wagner) find a cut with minimum total weight that separates a graph into two parts
• Strongly Connected Components (SCCs) algorithms (Kosaraju's, Tarjan's) identify maximal strongly connected subgraphs in directed graphs
  • Kosaraju's algorithm uses two DFS passes on the original and transposed graph
  • Tarjan's algorithm uses a single DFS with lowlink values and a stack
• Bipartite matching algorithms (Hungarian, Hopcroft-Karp) find maximum matchings in bipartite graphs
  • Hungarian algorithm solves the assignment problem in $O(V^3)$ time
  • Hopcroft-Karp finds maximum matchings in $O(\sqrt{V}E)$ time

Optimization Problems on Graphs

• Traveling Salesman Problem (TSP) seeks the shortest tour visiting each vertex exactly once
  • NP-hard problem, approximated using heuristics like Christofides' algorithm
• Vehicle Routing Problem (VRP) extends TSP with multiple vehicles, capacities, and time windows
  • Variants include Capacitated VRP (CVRP), VRP with Time Windows (VRPTW), and VRP with Pickups and Deliveries (VRPPD)
• Facility Location Problem aims to optimally place facilities to minimize costs and maximize coverage
  • Uncapacitated and capacitated versions, with heuristics and approximation algorithms
• Graph Coloring assigns colors to vertices such that no adjacent vertices share the same color
  • Chromatic number is the minimum number of colors needed
  • Applications in scheduling, register allocation, and frequency assignment
• Maximum Independent Set finds the largest subset of vertices with no edges between them
  • Complement of the minimum vertex cover problem
• Minimum Dominating Set seeks the smallest subset of vertices such that each vertex is either in the set or adjacent to a vertex in the set
  • Variants include connected dominating set and independent dominating set

Applications in Real-World Scenarios

• Social Networks use graphs to model relationships, with vertices as individuals and edges as connections
  • Community detection, influence maximization, and link prediction are common tasks
• Transportation Networks represent roads, railways, or flights as edges, with vertices as junctions or stations
  • Used for route planning, traffic flow optimization, and logistics
• Computer Networks model devices as vertices and connections as edges
  • Helps in network design, routing protocols, and resource allocation
• Biological Networks depict interactions between biological entities (proteins, genes)
  • Protein-protein interaction networks, gene regulatory networks, and metabolic pathways
• Recommendation Systems employ bipartite graphs with users and items as vertices, and ratings or interactions as edges
  • Collaborative filtering, content-based filtering, and hybrid approaches
• Project Scheduling represents tasks as vertices and dependencies as edges
  • Critical Path Method (CPM) and Program Evaluation and Review Technique (PERT) for scheduling and resource allocation

Problem-Solving Techniques

• Identify the problem type and select an appropriate graph representation
• Break down complex problems into subproblems, solving them independently and combining results
• Use heuristics and approximation algorithms for NP-hard problems, balancing solution quality and computational efficiency
• Employ dynamic programming for problems with overlapping subproblems and optimal substructure
• Consider greedy approaches when making locally optimal choices leads to a globally optimal solution
• Analyze time and space complexity, optimizing for the given constraints and problem size
• Test solutions on small instances, edge cases, and large-scale datasets
• Iterate and refine the approach based on feedback and performance analysis

Further Reading and Resources

• "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein (CLRS) covers fundamental graph algorithms and data structures
• "Algorithm Design" by Kleinberg and Tardos provides a comprehensive treatment of graph algorithms and their applications
• "Network Flows: Theory, Algorithms, and Applications" by Ahuja, Magnanti, and Orlin focuses on network flow problems and algorithms
• "Approximation Algorithms" by Vazirani explores techniques for designing approximation algorithms for NP-hard graph problems
• "Graph Theory" by Diestel offers a rigorous mathematical treatment of graph theory concepts and results
• Online platforms like LeetCode, HackerRank, and Codeforces for practicing graph-based coding problems
• Research papers and conferences (e.g., SODA, STOC, FOCS) for advanced topics and state-of-the-art algorithms
• Open-source libraries (NetworkX, igraph, LEMON) for implementing and visualizing graph algorithms in various programming languages