Finding largebipartite subgraphs (Part 2 of 2)

Finding a bipartite subgraph with maximum number of edges in a given graph is a classical problem in combinatorial optimization and extremal graph theory. It has been studied in computer science from an algorithmic point of view (as the MAX-CUT problem) and in combinatorics from a more structural point of view. The problem is NP-complete, so the research focus has been on heuristics, approximation algorithms, and extremal results (conditions on graph parameters that guarantee large bipartite subgraphs).

We will discuss open problems and related results from both the extremal and algorithmic realms. In particular, we will discuss some recent results on locally improving algorithms.

Event Topic

Discrete Applied Math Seminar