Skip to content

0x314 Combinatorial Optimization

1. Tree

1.1. Traversals

We have three tree traversals:

  • inorder: left, root, right
  • preorder: root, left, right
  • postorder: left, right, root

All of them can be implemented with recursion or a single stack.

traversals and syntax notations

Each of them are corresponding to a syntax notation:

  • inorder: infix (e.g: 2+2)
  • preorder: (Polish) prefix (e.g: + 2 2)
  • postorder: (reverse Polish) postfix (e.g: 2 2 +)

inorder can be transformed into preorder or postorder using shunting-yard algorithm with \(O(n)\)

1.2. Tree Property Problem

  • Isomorphism decision: encoding the tree by sorting theirs children with respect to their hash
  • centroid decomposition: a centroid of a tree is a node which would split the tree into child trees whose number of nodes are at most half of the original tree

1.3. Sequence Tree

Tree structures to handle sequences.

1.3.1. Segment Tree

segment tree is good at handling range queries (e.g: RMQ)

1.3.2. Binary Index Tree:

BIT (Fenwick tree) is good at handling following queries with \(O(log(n))\)

  • prefix sum query
  • point update query

1.3.3. Radix Tree (Patricia Tree):

Trie which nodes get merged when there is only one child

  • Inverted index

1.4. Binary Tree

The followings are self-balancing binary search tree, the blanced tree is generally defined by - left and right tree are recursively balanced - left and right height has at most 1 height difference.

1.4.1. Red-Black Tree:

A balanced binary tree which preserves following 4 properties.

  • each node is either red or black
  • root, leaves are black
  • red children must be black
  • black height for each node must be same

Complexity: \(O(log(n))\)

1.4.2. AVL Tree

1.4.3. Treap

\[Treap = tree + heap\]

For each incoming key, assign a random priority to the key, then construct the normal binary tree with the key, but it should maintain the heap structure (child's priority should be lower than parent) by rotations.

Suppose the priority is the (fixed) hash of the key, then the structure of the final tree is fixed regardless of the order key coming in.

1.4.4. Splay Tree

When accessing an element, rotating it to the root node. This will work like an cache

1.5. N-ary Tree

1.5.1. B/B+ Tree

  • for database Indexing

1.5.2. BK Tree

efficient structure for edit distance search.

1.5.3. Trie

2. Graph

Graph is defined as \(G(V,E)\) where \(V\) is its set of vertex and \(E\) is its set of edges.

I divided graph problems into 4 types:

  1. Problems to compute general properties of a graph
  2. Problems related to subgraphs such as whether a subgraph meeting a property exist or not
  3. Problems related to edges or paths (e.g.: TSP)
  4. Problems related to vertex

2.1. Graph Traversal

Algorithm (A-star search) At each iteration, it expands its path using the cost so far and a heuristic cost estimate

\[f(n) = g(n) + h(n)\]

where \(g\) is the cost so far and \(h\) is the heuristic function from current node to goal. If \(h\) is admissible (always underestimates the actual cost), then it is guaranteed to find the global optimum. Dijkstra can be seen as a special case by setting \(h(n)=0\)

2.2. Graph Property Problems

  • Graph Isomorphism: decide whether there is a bijective mapping between vertex sets of two graphs (unknown whether it is NP-complete)

2.3. Subgraph Problems

Bipartite graph decision

2.3.1. Maximum Clique

  • NP-Complete

2.3.2. MST problem (Minimum Spanning Tree)

MST problem is to compute the minimum cost subset of edges which could maintain input graph connected.

  • Prim: greedily connect a new vertex with minimum cost from reachable vertex set.
  • Kruskal: sort all edges based on costs and iteratively connecting new vertex

2.3.3. SCC problem

Strongly Connected Component

2.4. Edge Problems

Problems related to paths and subsets of edges

2.4.1. Cycle Problems

  • Euler Cycle: a cycle that visits each edge exactly once. Easy to solve by checking degree of each vertex
  • Hamilton Cycle: a cycle that visits each vertex exactly once. NP-hard
  • Traveling Sales Problem (TSP): a cycle of least cost visiting each vertex. NP-hard

2.4.2. Network Flow problems

Max Flow

compute max flow from one source to one sink

  • Ford-Fulkerson: \(O(F|E|)\) basic idea is to repeat the following process: greedily find a path which can flow within remaining capacity, then increase current flow for each edge within the path and decrease the increment for the reverse edge within the path.

Min Cut

complement of max flow

Multi-commodity Flow problem [wiki]

A generalization of max flow with multiple sources and sinks

2.4.3. Shortest Path

Single Source Shortest Path

  • Bellman-Ford [C++]: Iteratively update shortest distance with all edges. It can find negative loop when the update happens more than V loops. complexity \(O(|V||E|)\). used in RIP
  • Dijsktra [C++]: iteratively update shortest distance from shortest nodes. complexity is \(O(|E|log(|V|))\) with priority queue.

All Pairs Shortest Path

  • Warshall-Floyd: for for for. complexity \(O(V^3)\)

2.4.4. Matching problems

a matching is a subset of edges which did not share any common vertices.

\[ \mathrm{MaxMatching} + \mathrm{MinEdgeCover} = |V|\]

Max Matching

Reference: https://upload.wikimedia.org/wikipedia/commons/9/98/Maximum-matching-labels.svg

  • NP-hard
  • bigraph max matching can be reduced to max flow problem (by adding source and sink to each side of bigraph)

Stable Matching Problem

  • Gale-Shapley: algorithm for stable matching problem. (rough idea is to propose greedily from one side until stable marriage)

2.4.5. Covering problems

Min Edge Cover

  • NP-hard
  • complement of max matching, can also be reduced to max flow problem when it is a bigraph.

2.5. Vertex Problems

Min vertex cover and max independent set are complementary problems

\[\mathrm{MinVertexCover} + \mathrm{MaxIndependentSet} = |V|\]

2.5.1. Vertex Cover

Min Vertex Cover

Reference: https://upload.wikimedia.org/wikipedia/commons/5/58/Vertex-cover.svg

  • Select a subset of vertex so that each edge is covered at by at least one vertex in the set
  • NP hard
  • the answer is same as max matching when it is a bigraph.

2.5.2. Independent Set

Min Independent Set

  • select a subset of vertex so that none of them in subset are adjacent.
  • NP hard