Largest chordal and interval subgraphs faster than 2ⁿ

DOI10.1007/S00453-015-0054-2zbMATH Open1347.05236DBLPjournals/algorithmica/BliznetsFPV16arXiv1311.4055OpenAlexW2172016099WikidataQ59473710 ScholiaQ59473710MaRDI QIDQ329301FDOQ329301

Authors: Fedor V. Fomin, Michał Pilipczuk, Yngve Villanger, I. A. Bliznets 

Publication date: 21 October 2016

Published in: Algorithmica (Search for Journal in Brave)

Abstract: We prove that in an n-vertex graph, induced chordal and interval subgraphs with the maximum number of vertices can be found in time $O(2^{lambdan})$ for some $lambda<1$. These are the first algorithms breaking the trivial $2^n{n}^{O(1)}$ bound of the brute-force search for these problems.

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

Recommendations

• Largest Chordal and Interval Subgraphs Faster Than 2 n
• The size of chordal, interval and threshold subgraphs
• On the interval number of a chordal graph
• Listing Chordal Graphs and Interval Graphs
• On 2-Subcolourings of Chordal Graphs

zbMATH Keywords

interval graphschordal graphsexact exponential algorithmsmaximum induced \(\Pi\)-subgraph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Extremal problems in graph theory (05C35)

Cites Work

• Treewidth computation and extremal combinatorics
• Title not available (Why is that?)
• Graph Classes: A Survey
• Exact exponential algorithms.
• The node-deletion problem for hereditary properties is NP-complete
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The strong perfect graph theorem
• Recognizing Berge graphs
• Representation of a finite graph by a set of intervals on the real line
• Large Induced Subgraphs via Triangulations and CMSO
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• Algorithmic Aspects of Vertex Elimination on Graphs
• Finding induced subgraphs via minimal triangulations
• Iterative compression and exact algorithms
• On independent sets and bicliques in graphs
• Efficient exact algorithms through enumerating maximal independent sets and other techniques
• Largest Chordal and Interval Subgraphs Faster Than 2 n
• Exact algorithm for the maximum induced planar subgraph problem
• A Separator Theorem for Chordal Graphs
• Algorithms for maximum independent sets
• A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
• Finding a maximum induced degenerate subgraph faster than \(2^{n}\)
• Maximum \(r\)-regular induced subgraph problem: fast exponential algorithms and combinatorial bounds

Cited In (7)

• Largest Chordal and Interval Subgraphs Faster Than 2 n
• Enumeration of minimal tropical connected sets
• Subexponential-time algorithms for finding large induced sparse subgraphs
• Vertex deletion problems on chordal graphs
• Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
• Proximity Search for Maximal Subgraph Enumeration
• Listing Chordal Graphs and Interval Graphs

This page was built for publication: Largest chordal and interval subgraphs faster than \(2^n\)

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