# 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

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

### 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

• 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

• 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

• 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