170 exercises

Search tip: add tags and a query to focus your search

246

views

3

votes

Graph Isomorphism, BPP and RP

The Graph Isomorphism Problem is to determine whether two given graphs are isomorphic to each other. Prove that if Gra…

• COMPLEXITY THEORY

 

• graph-isomorphism

156

views

1

vote

$K_4$ subdivision and 3-colorability

Prove that every graph with no subgraph isomorphic to a subdivision of $K_4$ is 3-colorable.

• GRAPH THEORY

 

• graph-coloring

136

views

no

votes

Party Problem

Suppose there are six people at a party. Prove that there are always three of them so that every two know each other (or…

• COMBINATORICS
• GRAPH THEORY

 

• counting

99

views

no

votes

Properties of Petersen Graph

Petersen Graph is the graph shown below : Prove the following properties of the Petersen Graph : It is not planar.…

• GRAPH THEORY

 

• petersen-graph
• connectivity
• hamiltonian-cycle
• matching

63

views

3

votes

Orienting a Planar Graph

Exercise (easy) : Prove that the edges of any planar graph $G$ can be oriented to obtain a directed graph $D$ so that t…

• GRAPH THEORY

 

• planar-graphs

54

views

2

votes

Subtrees of a Tree

Let $T_1, T_2, \dots, T_k$ be subtrees of a tree $T$. Prove that if every two of them have a vertex in common, then they…

• GRAPH THEORY

 

• trees

56

views

no

votes

Happy Ending Problem

Prove the following : Any set of five points in the plane in general position has a subset of four points that from th…

• COMBINATORICS
• GEOMETRY

 

• counting

75

views

no

votes

Erdos-Szekeres Theorem

Prove that for given integers $r, s$ any sequence of distinct real numbers of length at least $(r - 1)(s - 1) + 1$ cont…

• COMBINATORICS

 

• pigeonhole-principle

55

views

2

votes

Reservoir Sampling

You are watching a stream of packets go by one at a time, and want to take a random sample of $k$ distinct packets from…

• RANDOMIZED ALGORITHMS

 

• sampling

38

views

no

votes

Minimum Flip Connectivity Problem

Let $G(V,E)$ be a directed graph such that if $e=(u,v) \in E$ then $(v,u) \notin E$, i.e., $G$ is an orientation of the…

• ALGORITHMS
• GRAPH THEORY

 

• connectivity

134

views

2

votes

Read Once Promised Majority

Suppose the input is $n$ numbers from $1$ to $n$, separated by commas and we know that one of the number occurs more tha…

• COMPLEXITY THEORY
• PUZZLES

 

• read-once

35

views

no

votes

Graphs with treewidth equal to pathwidth

Let $G(V,E)$ be an undirected graph with $|V|=n$ vertices. Let $tw(G)$ and $pw(G)$ represent the treewidth and pathwidth…

• GRAPH THEORY

 

• treewidth
• pathwidth

52

views

no

votes

Perfect Matchings in Cubic Graphs

Let $G$ be a cubic graph with no cut-edge. Let $PM(G)$ be the convex hull of the perfect matchings of $G$. Prove that…

• GRAPH THEORY

 

• matching

68

views

1

vote

Distances between points in a plane

Let $S$ be a set of $n \geq 3$ points in the plane such that the distance between any two points is at least 1. Prove…

• COMBINATORICS
• GEOMETRY

 

• counting

80

views

2

votes

Longest increasing digital subsequence

Let $S[1..n]$ be a sequence of integers between $0$ and $9$. A digital subsequence of $S$ is a sequence $D[1..k]$ of in…

• ALGORITHMS

 

• dynamic-programming

33

views

no

votes

Algebraic dual of graphs

Let $G$ be a connected graph. An algebraic dual of $G$ is a graph $G'$ such that $G$ and $G'$ have the same set of edges…

• GRAPH THEORY

 

• matroids

37

views

no

votes

Mycielskian graphs

A factor-critical graph is a graph with $n$ vertices in which every subset of $n-1$ vertices has a perfect matching. Let…

• GRAPH THEORY

 

• graph-coloring

32

views

1

vote

3-2-ary numbers

Prove that every positive integer can be expressed as a sum of numbers of the kind $2^i3^j$, where no term in the summat…

• ALGORITHMS

 

• dynamic-programming

64

views

1

vote

An Odd Party

$N$ people are at a party. Every pair of guests has an odd number of common friends. Show that $N$ is odd.

• COMBINATORICS
• PUZZLES

 

• counting

73

views

2

votes

Maintaining fitstrings

Every non-negative integer can be represented as the sum of distinct positive Fibonacci numbers. (As a warmup exercise,…

• ALGORITHMS

 

• amortized-analysis

24

views

no

votes

Fixed-parameter tractability of Vertex Cover

Let $G(V,E)$ be an undirected graph. A subset $S \subseteq V$ is a vertex cover of $G$ if every edge has at least one en…

• ALGORITHMS

 

• fpt-algorithms
• vertex-cover

33

views

no

votes

Planar Graphs are Pfaffians

Let $G(V,E)$ be an undirected graph. An orientation of $G$ is Pfaffian if every even cycle $C$ such that $G \setminus V(…

• GRAPH THEORY

 

• planar-graphs
• pfaffian

27

views

no

votes

Recognizing series-parallel graphs in linear time

Let $G(V,E)$ be a simple undirected graph with $|V| = n$ and $|E| = m$. Let the treewidth of $G$ be at most $k$. Deriv…

• ALGORITHMS
• GRAPH THEORY

 

• treewidth
• chordal-graph
• series-parallel
• linear-time-algorith...

98

views

no

votes

Caterpillars are Graceful

Graceful Labeling : Label the vertices of a simple undirected graph $G(V,E)$ (where $|V| = n$ and $|E| = m$) with intege…

• GRAPH THEORY

 

• graph-labeling

21

views

1

vote

Number of edges in a quasi-planar graph

A graph $G(V,E)$ is called quasi-planar if it can be drawn in the plane with no three pairwise crossing edges. Prove tha…

• GRAPH THEORY

 

• planar-graphs

28

views

no

votes

Approximating (1,2)-TSP

Let $G$ be a complete directed graph i.e., if $u$ and $v$ are vertices of $G$ then both the directed edges $(u,v)$ and $…

• APPROXIMATION ALGORITHMS

 

• traveling-salesman

111

views

no

votes

Simplicial vertices in Chordal graphs

Let $G(V,E)$ be a simple undirected graph. Let $v \in V$ and let $N(v)$ denote the neighbors of $v$ in $G$. The vertex $…

• GRAPH THEORY

 

• chordal-graph

54

views

no

votes

Block Decomposition in Linear Time

A block of a graph $G$ is a maximal connected subgraph of $G$ that has no cut-vertex. If $G$ itself is connected and has…

• ALGORITHMS
• GRAPH THEORY

 

• linear-time-algorith...

34

views

no

votes

Exact Algorithms for Subset Sum

Let $a_1, a_2, \dots, a_n$ be natural numbers in the range $[1,M]$. Let $b$ be another natural number. Subset Sum Proble…

• ALGORITHMS

 

• exponential-algorith...
• subset-sum
• dynamic-programming

62

views

1

vote

Linear time algorithms on trees

Let $T(V,E)$ be a tree. Design linear time (i.e., $O(|V|)$ time) algorithms for the following problems : Find an optim…

• ALGORITHMS
• GRAPH THEORY

 

• linear-time-algorith...
• trees
• vertex-cover
• matching
• independent-set