15th CoRe Seminar
Date and time: | 2021.10.07 Thu. 10:00-12:00
|
---|---|
Venue: | Online |
Speaker: | ETO, Hiroshi (Tohoku U., Group A01) |
Title: | The complexity of maximum induced subgraph problem with some properties |
Summary: | The Maximum Induced Subgraph problem with Property P is one of graph optimization problems. In the problem, we find a maximum cardinality induced subgraph satisfying some property P. By setting the property P appropriately, we can formulate many graph optimization problems as the Maximum Induced Subgraph problem. For example, if the property is "induced subgraph is an independent set," the problem is equivalent to the Maximum Independent Set problem. A property P of graph G is said to be hereditary whenever a graph G satisfies the property P and any induced subgraph of G also satisfies the same property P. It is known that the Maximum Induced Subgraph problem with hereditary property is extremely hard to approximate. In this talk, I will talk about the Maximum Induced Subgraph problem with non-hereditary property, in particular, "induced subgraph is regular."
|
Update:2021.09.21