A faster algorithm to recognize even-hole-free graphs

DOI10.1016/J.JCTB.2015.02.001MaRDI QIDQ2347846zbMATH OpenOpenAlexFDO

Authors Hsien-Chih Chang, Hsueh-I Lu

Publication date 10 June 2015

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.0358

zbMATH Keywords

2-joindiamondtrackerstar-cutsetbeetledecomposition-based detection algorithmeven holeextended clique tree

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We study the problem of determining whether an $n$-node graph $G$ has an even hole, i.e., an induced simple cycle consisting of an even number of nodes. Conforti, Cornu'ejols, Kapoor, and Vuv{s}kovi'c gave the first polynomial-time algorithm for the problem, which runs in $O(n^{40})$ time. Later, Chudnovsky, Kawarabayashi, and Seymour reduced the running time to $O(n^{31})$. The best previously known algorithm for the problem, due to da Silva and Vuv{s}kovi'c, runs in $O(n^{19})$ time. In this paper, we solve the problem in $O(n^{11})$ time. Moreover, if $G$ has even holes, our algorithm also outputs an even hole of $G$ in $O(n^{11})$ time.

Recommendations

• A faster algorithm to recognize even-hole-free graphs
• Even-hole-free graphs part II: Recognition algorithm
• On the structure of (pan, even hole)-free graphs
• Finding a shortest even hole in polynomial time
• Decomposition of even-hole-free graphs with star cutsets and 2-joins

Cites work

• scientific article; zbMATH DE number 3593613 (Why is no real title available?)
• scientific article; zbMATH DE number 1496606 (Why is no real title available?)
• scientific article; zbMATH DE number 7051285 (Why is no real title available?)
• A bound on the treewidth of planar even-hole-free graphs
• A faster algorithm to recognize even-hole-free graphs
• Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithms for Perfectly Contractile Graphs
• Algorithms for finding an induced cycle in planar graphs
• Bisimplicial vertices in even-hole-free graphs
• Combinatorial optimization with 2-joins
• Complexity of clique-coloring odd-hole-free graphs
• Compositions for perfect graphs
• Corrigendum to: On the complexity of testing for odd holes and induced odd paths
• Decomposing Berge graphs and detecting balanced skew partitions
• Decomposition of even-hole-free graphs with star cutsets and 2-joins
• Decomposition of odd-hole-free graphs by double star cutsets and 2-joins
• Detecting 2-joins faster
• Detecting even holes
• Detecting holes and antiholes in graphs
• Even and odd holes in cap-free graphs
• Even-hole-free graphs part II: Recognition algorithm
• Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
• Even-hole-free graphs. I: Decomposition theorem
• Even-hole-free graphs: A survey
• Finding a smallest odd hole in a claw-free graph using global structure
• Hole and antihole detection in graphs
• Odd Hole Recognition in Graphs of Bounded Clique Size
• On diameters and radii of bridged graphs
• On the complexity of testing for odd holes and induced odd paths
• Recognizing Berge graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Smallest odd holes in claw-free graphs (extended abstract)
• Star-cutsets and perfect graphs
• The NP-completeness column
• The strong perfect graph theorem
• The three-in-a-tree problem
• Triangulated neighborhoods in even-hole-free graphs
• \(K_{4}\)-free graphs with no odd hole: even pairs and the circular chromatic number
• \(K_{4}\)-free graphs with no odd holes

Cited in

(21)

• Decomposition of even-hole-free graphs with star cutsets and 2-joins
• On the structure and clique‐width of (4K1,C4,C6,C7)‐free graphs
• Finding a shortest even hole in polynomial time
• Structure and algorithms for (cap, even hole)-free graphs
• Triangulated neighborhoods in even-hole-free graphs
• FPT and kernelization algorithms for the induced tree problem
• Polyhedral properties of the induced cluster subgraphs
• Detecting holes and antiholes in graphs
• Detecting a long even hole
• A faster algorithm to recognize even-hole-free graphs
• Detecting even holes
• The impact of locality in the broadcast congested clique model
• Induced subgraphs and tree decompositions. I: Even-hole-free graphs of bounded degree
• A note on coloring \((4K_1, C_4, C_6)\)-free graphs with a \(C_7\)
• An \(O( n^{3})\)-time recognition algorithm for hhds-free graphs
• Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
• Odd Hole Recognition in Graphs of Bounded Clique Size
• Integer programming formulations for the \(k\)-in-a-tree problem in graphs
• On the structure of (pan, even hole)-free graphs
• Coloring \((4K_1,C_4,C_6)\)-free graphs
• Even-hole-free graphs part II: Recognition algorithm

Describes a project that uses

Uses Software

• Algorithm 447

This page was built for publication: A faster algorithm to recognize even-hole-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2347846)