# Finding subgraphs Flashcards

1
Q
A
2
Q

Assume G has n vertices and H has k vertices.

suggest a naive algorithm which determines whether H is an induced sub graph of G.

What is the run time?

A
3
Q

Write the naive algorithm for finding triangles.

What its run-time? for which graph it is good?

A
4
Q

What does A^2 represent?

write the algorithm for finding a triangle.

write the run time

A
5
Q

What does A^3 represent?

A
6
Q

Find a triangle in O(m^1.41) time.

Show the algorithm, correctness proof and run-time analysis.

A
7
Q

Assume G with n vertices and H with 3k vertices.

Write an algorithm which determines where H is an induced subgraph of G in O(n^2.38k)

A
8
Q

Decribe the open question regarding all paths

A
9
Q

Let A be an adjacent matrix of G, what does A^k resemble?

Let k be the minimal integer for which (A^k)i,j > 0. what does it tell us?

Define G^2.

A
10
Q

Let d^2 denote the distances in G^2, and d to denote the distances in G.

A
11
Q

How the adjacency matrix B of G^2 can be computed?

A
12
Q
A
13
Q

Write ASAP and its run-time

A

depth of the recursion - O(log n)

In each step we perform two matrix multiplications and two creations of matrices - O(n^2.373)

in total - O(n^2.373 * log n) = O(2.38)

14
Q

For a weighted graph on limited range {1,… , M}, what is the run-time for all-pairs using matrix multiplication?

A

O(n^2.38 * m)

15
Q

Define an alpha-additive algorithm which computes d’(u,v)

A
16
Q

Describe the Hitting Set problem

A
17
Q

Write the first hitting set approximation algorithm.

Write the chance of it to get a right hitting set.

A
18
Q

Prove the observation

A
19
Q

Prove the lemma

A
20
Q

Write the algorithm for all-pairs approximation

A
21
Q

What is the size of E’?

A
22
Q

prove

A
23
Q

Analyze the run-time

A