KAIST Discrete Math Seminar

Given a graph, we are interested in studying the problem of finding an induced subgraph of a fixed order with largest number of edges. More generally, let G = (V, E) be an undirected graph, with a weight (budget) function on the vertices, w: V → ℤ⁺, and a benefit function on vertices and edges b: E ∪ V → ℤ. The benefit of a subgraph H =(V_H,E_H) is b(H) = ∑ _v∈VH b(v) + ∑ _e∈EH b(e) while its weight is w(H) = ∑ _v∈VH w(v). What can be said about the maximum benefit of an induced subgraph with the restriction that its weight is less than W?

This problem is closely related to the Quadratic Knapsack Problem, the Densest Subgraph Problem, and classical problems in Extremal Graph Theory. We will discuss these connections, give applications in resource allocation, and present new results on approximation algorithms using methods from convex optimization and probability. This is joint work with Kapoor.