Even-hole-free graph

In the mathematical area of graph theory, a graph is even-hole-free if it contains no induced cycle with an even number of vertices.

Addario-Berry et al. (2008) demonstrated that every even-hole-free graph contains a bisimplicial vertex, which settled a conjecture by Reed.

Recognition

Conforti et al. (2002) gave the first polynomial time recognition algorithm for even-hole-free graphs, which runs in time.[1] da Silva & Vušković (2008) later improved this to . Chang & Lu (2012) and Chang & Lu (2015) improved this to time. The best currently known algorithm is given by Lai, Lu & Thorup (2020) which runs in time.

While even-hole-free graphs can be recognized in polynomial time, it is NP-complete to determine whether a graph contains an even hole that includes a specific vertex.[2]

It is unknown whether graph coloring and the maximum independent set problem can be solved in polynomial time on even-hole-free graphs, or whether they are NP-complete. However the maximum clique can be found in even-hole-free graphs in polynomial time.[3]

Notes
  1. Conforti et al. (2002) present their algorithm and assert that it runs in polynomial time without giving an explicit analysis. Chudnovsky, Kawarabayashi & Seymour (2004) estimate that it runs in "time about ."
  2. Bienstock (1991)
  3. Vušković (2010).
gollark: Oh, this is neat, via accursed javascriptoids it is possible to pull stats from my bad consumer router into prometheus.
gollark: > https://dwm.suckless.org/
gollark: > Because dwm is customized through editing its source code, it's pointless to make binary packages of it. This keeps its userbase small and elitist. No novices asking stupid questions. There are some distributions that provide binary packages though.
gollark: Also... Minecraft?
gollark: Anyway, with sufficient accursed programs I can apparently export APIONET metrics to graphs.

References
  • Addario-Berry, Louigi; Chudnovsky, Maria; Havet, Frédéric; Reed, Bruce; Seymour, Paul (2008), "Bisimplicial vertices in even-hole-free graphs", Journal of Combinatorial Theory, Series B, 98 (6): 1119–1164, doi:10.1016/j.jctb.2007.12.006
  • Bienstock, Dan (1991), "On the complexity of testing for odd holes and induced odd paths", Discrete Mathematics, 90 (1): 85–92, doi:10.1016/0012-365X(91)90098-M
  • Chudnovsky, Maria; Kawarabayashi, Ken-ichi; Seymour, Paul (2004), "Detecting even holes", Journal of Graph Theory, 48 (2): 85–111, doi:10.1002/jgt.20040
  • Conforti, Michele; Cornuéjols, Gérard; Kapoor, Ajai; Vušković, Kristina (2002), "Even-hole-free graphs part I: Decomposition theorem", Journal of Graph Theory, 39 (1): 6–49, doi:10.1002/jgt.10006
  • Conforti, Michele; Cornuéjols, Gérard; Kapoor, Ajai; Vušković, Kristina (2002), "Even-hole-free graphs part II: Recognition algorithm", Journal of Graph Theory, 40 (4): 238–266, doi:10.1002/jgt.10045
  • da Silva, Murilo V.G.; Vušković, Kristina (2008), Decomposition of even-hole-free graphs with star cutsets and 2-joins
  • Chang, Hsien-Chih; Lu, Hsueh-I (2012), "A Faster Algorithm to Recognize Even-Hole-Free Graphs", SODA
  • Chang, Hsien-Chih; Lu, Hsueh-I (2015), "A Faster Algorithm to Recognize Even-Hole-Free Graphs", Journal of Combinatorial Theory, Series B, 113: 141–161, arXiv:1311.0358, doi:10.1016/j.jctb.2015.02.001
  • Vušković, Kristina (2010), "Even-hole-free graphs: a survey", Applicable Analysis and Discrete Mathematics, 4 (2): 219–240, doi:10.2298/AADM100812027V, JSTOR 43666110, MR 2724633
  • Lai, Kai-Yuan; Lu, Hsueh-I; Thorup, Mikkel (2020), "Three-in-a-Tree in Near Linear Time", STOC: 1279–1292, arXiv:1909.07446, doi:10.1145/3357713.3384235
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.