EE Seminar: On finding small subgraphs in bounded-degree graphs
Speaker: Yaniv Sabo
M.Sc. student under the supervision of Prof. Dana Ron
Wednesday, January 11th 2017 at 15:30
Room 011, Kitot Bldg., Faculty of Engineering
On finding small subgraphs in bounded-degree graphs
Abstract
We study the problem of finding a copy of a subgraph H in a graph G that is far from being free of having copies of H. We consider this problem in the bounded-degree graphs model. In this model, each of the n vertices has at most d neighbors, and an algorithm is allowed to make queries regarding the neighbors of vertices in the graph. The graph is said to be $\epsilon$-far from being H-free if more than $\epsilon$dn of its edges must be deleted to make the graph free from having copies of H.
We present an algorithm for finding a copy of H in graphs that are e-far from being H-free and have bounded (constant) treewidth. This algorithm makes a number of queries that is polynomial in 1/$\epsilon$, the size of H and the degree bound d. The complexity of the algorithm is independent of the number of vertices, n.
We also present an algorithm for the special case in which H is a path of length k. Our algorithm uses specific properties of graphs that are far from having k-paths. Finding k-paths was previously studied by Reznik (Master's thesis, Weizmann Institute of Science, 2011). Reznik gave an algorithm for the case in which G is cycle-free, where the query complexity of the algorithm is polynomial in k, d and 1/$\epsilon$. We propose a conjecture that, if proven to be true, implies that our algorithm works for any graph that is $\epsilon$-far from being k-path free with query complexity polynomial in k, d, and 1/$\epsilon$. As a sanity check, we establish the conjecture for cycle-free graphs.
