MATH Seminar
| Title: Extending Partial Geometric Representations of Graphs |
|---|
| Seminar: Combinatorics |
| Speaker: Jan Kratochvil of Charles University, Prague |
| Contact: Dwight Duffus, dwight@mathcs.emory.edu |
| Date: 2015-04-17 at 4:00PM |
| Venue: MSC W303 |
| Download Flyer |
| Abstract: Intersection-defined classes of graphs are intensively studied for their applications and interesting properties. Many of them allow polynomial-time algorithms for otherwise computationally hard problems such as independent set, clique or coloring problems. And many of them can be recognized in polynomial time. In fact the polynomial-time algorithms often need a representation to be given or constructed as the initial step. The rather natural question of extending a partial representation has been studied only recently. It falls into the more general paradigm of extending a partial solution of a problem. Sometimes a global solution can be reached by incremental steps from a partial one in polynomial-time, but in many cases an otherwise easy problem may become hard. Examples of such behavior can be found for instance in graph colorings (e.g., deciding if a partial edge-coloring of a cubic bipartite graph can be extended to a full 3-coloring of it is NP-complete, though it is well known that every cubic bipartite graph is 3-edge-colorable and such a coloring can be found in polynomial time). In this talk we survey the known results about the computational complexity of extending partial geometric representations of graphs. |
See All Seminars