Logical Approaches to Computational Barriers

Induced matchings in graphs of maximum degree three

Speaker:
| Grazyna Zwozniak |

Slot: |
Array, 17:10-17:30, col. 1 |

An induced matching is a matching $M$ where each two edges $e_1,\,e_2 \in M$ are at the distance greater than one. In this paper we consider the problem of finding maximum induced matchings in graphs of maximum degree three. The problem is NP-hard. We present an algorithm which finds the maximum induced matching of size at least $n/6+O(1)$, where $n$ is the number of vertices in a graph. Using this bound we achieve an approximation ratio of 1.8 in cubic graphs.

websites: Arnold Beckmann | 2008-05-23 |