Large Induced Subgraphs via Triangulations and CMSO

DOI10.1137/140964801zbMath1357.05144DBLPjournals/siamcomp/FominTV15arXiv1309.1559OpenAlexW1968041356WikidataQ60488392 ScholiaQ60488392MaRDI QIDQ2954371

Fedor V. Fomin, Yngve Villanger, Ioan Todinca

Publication date: 13 January 2017

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

treewidthgraph algorithmsminimal triangulationspotential maximal cliquesCMSO

Mathematics Subject Classification ID

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

Related Items (37)

Enumerating minimal connected dominating sets in graphs of bounded chordality ⋮ An Improvement of Reed’s Treewidth Approximation ⋮ On Distance-d Independent Set and Other Problems in Graphs with “few” Minimal Separators ⋮ Largest chordal and interval subgraphs faster than \(2^n\) ⋮ Finding optimal triangulations parameterized by edge clique cover ⋮ Structural parameterizations with modulator oblivion ⋮ Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem ⋮ Finding a maximum minimal separator: graph classes and fixed-parameter tractability ⋮ iTri: index-based triangle listing in massive graphs ⋮ Summarized bit batch-based triangle listing in massive graphs ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ On the tractability of optimization problems on \(H\)-graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Solving Graph Problems via Potential Maximal Cliques ⋮ Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs ⋮ Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques ⋮ Algorithms parameterized by vertex cover and modular width, through potential maximal cliques ⋮ Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes ⋮ A meta-theorem for distributed certification ⋮ Unnamed Item ⋮ New Width Parameters for Independent Set: One-Sided-Mim-Width and Neighbor-Depth ⋮ An improved parameterized algorithm for treewidth ⋮ Vertex deletion problems on chordal graphs ⋮ Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity ⋮ On \(H\)-topological intersection graphs ⋮ Subexponential parameterized algorithms and kernelization on almost chordal graphs ⋮ Subexponential-time algorithms for finding large induced sparse subgraphs ⋮ Unnamed Item ⋮ On the Number of Minimal Separators in Graphs ⋮ Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques ⋮ Avoidable vertices and edges in graphs: existence, characterization, and applications ⋮ Vertex Deletion Problems on Chordal Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact exponential algorithms.
• The three-in-a-tree problem
• Monadic second-order evaluations on tree-decomposable graphs
• A linear algorithm for the group path problem on chordal graphs
• Induced packing of odd cycles in planar graphs
• Graph minors. III. Planar tree-width
• Efficient reduction for path problems on circular-arc graphs
• Minimal triangulations of graphs: a survey
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• Minimum weight feedback vertex sets in circle graphs
• Finding induced trees
• Graph minors. V. Excluding a planar graph
• The maximum k-colorable subgraph problem for chordal graphs
• The ellipsoid method and its consequences in combinatorial optimization
• On the complexity of testing for odd holes and induced odd paths
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Induced matchings
• A partial k-arboretum of graphs with bounded treewidth
• Quickly excluding a planar graph
• On treewidth and minimum fill-in of asteroidal triple-free graphs
• Induced matchings in asteroidal triple-free graphs
• Listing all potential maximal cliques of a graph
• Finding a maximum induced matching in weakly chordal graphs
• New results on induced matchings
• Contraction obstructions for treewidth
• Treewidth computation and extremal combinatorics
• Fast algorithms for max independent set
• The Erdős-Pósa property for long circuits
• Independent packings in structured graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• An Improved Exact Algorithm for Undirected Feedback Vertex Set
• Exact Algorithms for Maximum Independent Set
• MINIMUM WEIGHT FEEDBACK VERTEX SETS IN CIRCLE n-GON GRAPHS AND CIRCLE TRAPEZOID GRAPHS
• Exponential time algorithms for the minimum dominating set problem on some graph classes
• Exact Algorithm for the Maximum Induced Planar Subgraph Problem
• Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths
• Deciding first-order properties of locally tree-decomposable structures
• The Use of Linear Graphs in Gauss Elimination
• Easy problems for tree-decomposable graphs
• A measure & conquer approach for the analysis of exact algorithms
• Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
• Exact Algorithms for Treewidth and Minimum Fill-In
• The Complexity of the Partial Order Dimension Problem
• Algorithms for maximum independent sets
• On the presence of disjoint subgraphs of a specified type
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Finding a Maximum Independent Set
• Minimum Fill-in on Circle and Circular-Arc Graphs
• Graph Classes: A Survey
• Robust algorithms for restricted domains
• Treewidth and Pathwidth of Permutation Graphs
• Maximum $r$-Regular Induced Subgraph Problem: Fast Exponential Algorithms and Combinatorial Bounds
• (Meta) Kernelization
• GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
• Independent Set in P₅-Free Graphs in Polynomial Time
• Subexponential Parameterized Algorithm for Minimum Fill-In
• Bidimensionality and Geometric Graphs
• A Computing Procedure for Quantification Theory
• Exact Computation of Maximum Induced Forest
• On cliques in graphs

This page was built for publication: Large Induced Subgraphs via Triangulations and CMSO