Detecting a Long Odd Hole
- PDF / 442,097 Bytes
- 30 Pages / 442.205 x 665.008 pts Page_size
- 67 Downloads / 222 Views
Bolyai Society – Springer-Verlag
Combinatorica 30pp. DOI: 10.1007/s00493-020-4301-z
DETECTING A LONG ODD HOLE MARIA CHUDNOVSKY∗ , ALEX SCOTT† , PAUL SEYMOUR‡ Received August 23, 2019 Revised March 10, 2020 For each integer ` ≥ 5, we give a polynomial-time algorithm to test whether a graph contains an induced cycle with length at least ` and odd.
1. Introduction All graphs in this paper are finite and have no loops or parallel edges. A hole of G is an induced subgraph of G that is a cycle of length at least four, and an antihole is an induced subgraph whose complement is a cycle of length at least four. In 2005, two of us, with Cornu´ejols, Liu and Vuˇskovi´c [4], gave an algorithm to test whether an input graph G has an odd hole or odd antihole, and thereby to test whether G is perfect, with running time at most polynomial in |G|. (|G| denotes the number of vertices of G.) At that time we were unable to separate the test for odd holes from the test for odd antiholes, and testing for odd holes in poly-time has remained open until very recently. Indeed, it seemed quite likely that testing for an odd hole was NP-complete; for instance, D. Bienstock [2,3] showed that testing if a graph has an odd hole containing a given vertex is NP-complete. So it Mathematics Subject Classification (2010): 05C38; 05C85 This material is based upon work supported in part by the U. S. Army Research Office under grant number W911NF-16-1-0404, and by NSF grant DMS-1763817. † Supported by a Leverhulme Trust Research Fellowship. ‡ Supported by NSF grant DMS-1800053 and AFOSR grant A9550-19-1-0187, and partially supported by the Simons Foundation and by the Mathematisches Forschungsinstitut Oberwolfach. ∗
2
M. CHUDNOVSKY, A. SCOTT, P. SEYMOUR
was something of a surprise when recently we found a poly-time algorithm to test for odd holes [6]. (This is modified to run faster in a recent paper [10] by Lai, Lu, and Thorup.) In this paper we extend that result: for each integer ` ≥ 5 we give a polytime algorithm to test whether G has an odd hole of length at least `. More exactly: 1.1. For each integer ` ≥ 5, there is an algorithm with the following specifications: Input: A graph G. Output: Decides whether G has an odd hole of length at least `. Running time: O(|G|20`+40 ). We have not tried very hard to optimize the exponent in the running time (although getting the exponent to be linear in ` took some effort). We are not aware of previous work on detecting “long” induced subgraphs of specific type, although it seems a sensible question. Here are three current pieces of work that are related: • Linda Cook, with Seymour, has a poly-time algorithm to test if a graph has a long even hole [9]. • Eli Berger and Sophie Spirkl, with Seymour, have a poly-time algorithm to test if there is an induced path between specified vertices s, t of a graph that has length longer than the shortest st-path [1]. It is open whether there is a poly-time algorithm to test for an induced st-path of length at least three more than the shortest st-path. • We have a p
Data Loading...
