Article ID Journal Published Year Pages File Type
4656781 Journal of Combinatorial Theory, Series B 2015 21 Pages PDF
Abstract

We study the problem of determining whether an n-node graph G contains an even hole  , i.e., an induced simple cycle consisting of an even number of nodes. Conforti, Cornuéjols, Kapoor, and Vušković gave the first polynomial-time algorithm for the problem, which runs in O(n40)O(n40) time. Later, Chudnovsky, Kawarabayashi, and Seymour reduced the running time to O(n31)O(n31). The best previously known algorithm for the problem, due to da Silva and Vušković, runs in O(n19)O(n19) time. In this paper, we solve the problem in O(n11)O(n11) time via a decomposition-based algorithm that relies on the decomposition theorem of da Silva and Vušković. Moreover, if G contains even holes, then our algorithm also outputs an even hole of G   in O(n11)O(n11) time.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,