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

DOI10.1007/978-3-642-31155-0_13zbMATH Open1357.68077arXiv1410.3260OpenAlexW1492318137MaRDI QIDQ2904550FDOQ2904550

Authors: Aistis Atminas, Igor Razgon, Vadim Lozin 

Publication date: 14 August 2012

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

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.

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

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

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)

Cited In (22)

• The micro-world of cographs
• Fine-grained parameterized complexity analysis of graph coloring problems
• Vertex coloring of graphs with few obstructions
• Critical properties of bipartite permutation graphs
• Coloring graphs without short cycles and long induced paths
• Hereditary classes of graphs: a parametric approach
• Certifying coloring algorithms for graphs without long induced paths
• Lower and upper bounds for long induced paths in 3-connected planar graphs
• 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
• Stable graphs of bounded twin-width
• Complexity of coloring graphs without paths and cycles
• Title not available (Why is that?)
• Between clique-width and linear clique-width of bipartite graphs
• Simple linear time approximation algorithm for betweenness
• The Micro-world of Cographs
• Long induced paths in graphs

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)