0x312 Combinatorial

Tree

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

Sequence Tree

Tree structures to handle sequences.

Segment Tree

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

Binary Index Tree:

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

  • prefix sum query
  • point update query

Radix Tree (Patricia Tree):

Trie which nodes get merged when there is only one child

  • Inverted index

Binary Tree

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))$

AVL Tree

N-ary Tree

B/B+ Tree

  • for database Indexing

BK Tree

efficient structure for edit distance search.

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

Graph Property Problems

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

Subgraph Problems

Bipartite graph decision

Maximum Clique

  • NP-Complete

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

SCC problem

Strongly Connected Component

Edge Problems

Problems related to paths and subsets of edges

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

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

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)$

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)

Covering problems

Min Edge Cover

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

Vertex Problems

Min vertex cover and max independent set are complementary problems

$$\mathrm{MinVertexCover} + \mathrm{MaxIndependentSet} = |V|$$

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.

Independent Set

Min Independent Set

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