Linear time algorithm for computing a small biclique in graphs without long induced paths

DOI10.1007/978-3-642-31155-0_13MaRDI QIDQ2904550zbMATH OpenOpenAlexFDO

Authors Aistis Atminas, Igor Razgon, Vadim Lozin

Publication date 14 August 2012

Published in Algorithm Theory – SWAT 2012 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Paths and cycles (05C38)

Abstract: Recently, Daligault, Rao and Thomass'e asked in [3] if every hereditary class which is well-quasi-ordered by the induced subgraph relation is of bounded clique-width. There are two reasons why this questions is interesting. First, it connects two seemingly unrelated notions. Second, if the question is answered affirmatively, this will have a strong algorithmic consequence. In particular, this will mean (through the use of Courcelle theorem [2]), that any problem definable in Monadic Second Order Logic can be solved in a polynomial time on any class well-quasi-ordered by the induced subgraph relation. In the present paper, we answer this question affirmatively for graphs without large bicliques. Thus the above algorithmic consequence is true, for example, for classes of graphs of bounded degree.

Recommendations

• The parameterized complexity of the \(k\)-biclique problem
• The parameterized complexity of \(k\)-biclique
• Exact exponential-time algorithms for finding bicliques
• Covering graphs with few complete bipartite subgraphs
• Covering Graphs with Few Complete Bipartite Subgraphs

Cited in

(22)

• The micro-world of cographs
• Vertex coloring of graphs with few obstructions
• Fine-grained parameterized complexity analysis of graph coloring problems
• Critical properties of bipartite permutation graphs
• Hereditary classes of graphs: a parametric approach
• Coloring graphs without short cycles and long induced paths
• Lower and upper bounds for long induced paths in 3-connected planar graphs
• Certifying coloring algorithms for graphs without long induced paths
• Finding cactus roots in polynomial time
• Labelled induced subgraphs and well-quasi-ordering
• Colouring square-free graphs without long induced paths
• The parameterized complexity of \(k\)-biclique
• Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs
• A Ramsey-type theorem for the matching number regarding connected graphs
• Exact exponential-time algorithms for finding bicliques
• Complexity of coloring graphs without paths and cycles
• Stable graphs of bounded twin-width
• scientific article; zbMATH DE number 7651161 (Why is no real title available?)
• Between clique-width and linear clique-width of bipartite graphs
• Simple linear time approximation algorithm for betweenness
• Long induced paths in graphs
• The Micro-world of Cographs

This page was built for publication: Linear time algorithm for computing a small biclique in graphs without long induced paths

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