Large Induced Subgraphs via Triangulations and CMSO
From MaRDI portal
Abstract: We obtain an algorithmic meta-theorem for the following optimization problem. Let phi be a Counting Monadic Second Order Logic (CMSO) formula and t be an integer. For a given graph G, the task is to maximize |X| subject to the following: there is a set of vertices F of G, containing X, such that the subgraph G[F] induced by F is of treewidth at most t, and structure (G[F],X) models phi. Some special cases of this optimization problem are the following generic examples. Each of these cases contains various problems as a special subcase: 1) "Maximum induced subgraph with at most l copies of cycles of length 0 modulo m", where for fixed nonnegative integers m and l, the task is to find a maximum induced subgraph of a given graph with at most l vertex-disjoint cycles of length 0 modulo m. 2) "Minimum Gamma-deletion", where for a fixed finite set of graphs Gamma containing a planar graph, the task is to find a maximum induced subgraph of a given graph containing no graph from Gamma as a minor. 3) "Independent Pi-packing", where for a fixed finite set of connected graphs Pi, the task is to find an induced subgraph G[F] of a given graph G with the maximum number of connected components, such that each connected component of G[F] is isomorphic to some graph from Pi. We give an algorithm solving the optimization problem on an n-vertex graph G in time O(#pmc n^{t+4} f(t,phi)), where #pmc is the number of all potential maximal cliques in G and f is a function depending of t and phi only. We also show how a similar running time can be obtained for the weighted version of the problem. Pipelined with known bounds on the number of potential maximal cliques, we deduce that our optimization problem can be solved in time O(1.7347^n) for arbitrary graphs, and in polynomial time for graph classes with polynomial number of minimal separators.
Recommendations
- Large induced subgraphs via triangulations and CMSO
- Large induced subgraphs with \(k\) vertices of almost maximum degree
- Large induced subgraph with restricted degrees in trees
- Large induced subgraphs with equated maximum degree
- Large induced degenerate subgraphs
- Large Nearly Regular Induced Subgraphs
- scientific article; zbMATH DE number 7650231
- Subexponential-time algorithms for finding large induced sparse subgraphs
- scientific article; zbMATH DE number 2084267
Cites work
- (Meta) Kernelization
- A Computing Procedure for Quantification Theory
- A linear algorithm for the group path problem on chordal graphs
- A measure \& conquer approach for the analysis of exact algorithms
- A partial k-arboretum of graphs with bounded treewidth
- Algorithmic meta-theorems
- Algorithms for maximum independent sets
- An Improved Exact Algorithm for Undirected Feedback Vertex Set
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- Bidimensionality and kernels
- Contraction obstructions for treewidth
- Deciding first-order properties of locally tree-decomposable structures
- Easy problems for tree-decomposable graphs
- Efficient reduction for path problems on circular-arc graphs
- Exact algorithm for the maximum induced planar subgraph problem
- Exact Algorithms for Maximum Independent Set
- Exact Algorithms for Treewidth and Minimum Fill-In
- Exact Computation of Maximum Induced Forest
- Exact exponential algorithms.
- Exponential time algorithms for the \textsc{minimum dominating set} problem on some graph classes
- Fast algorithms for max independent set
- Finding a Maximum Independent Set
- Finding a maximum induced matching in weakly chordal graphs
- Finding contractions and induced minors in chordal graphs via disjoint paths
- Finding induced trees
- GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
- Graph Classes: A Survey
- Graph minors. III. Planar tree-width
- Graph minors. V. Excluding a planar graph
- Graph structure and monadic second-order logic. A language-theoretic approach
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3420184 (Why is no real title available?)
- Independent packings in structured graphs
- Independent set in P₅-free graphs in polynomial time
- Induced matchings
- Induced matchings in asteroidal triple-free graphs
- Induced packing of odd cycles in planar graphs
- Listing all potential maximal cliques of a graph
- Logic, graphs, and algorithms
- Maximum r-regular induced subgraph problem: fast exponential algorithms and combinatorial bounds
- Minimal triangulations of graphs: a survey
- Minimum Fill-in on Circle and Circular-Arc Graphs
- Minimum weight feedback vertex sets in circle n-gon graphs and circle trapezoid graphs
- Minimum weight feedback vertex sets in circle graphs
- Monadic second-order evaluations on tree-decomposable graphs
- New results on induced matchings
- On cliques in graphs
- On the complexity of testing for odd holes and induced odd paths
- On the minimum feedback vertex set problem: Exact and enumeration algorithms
- On the presence of disjoint subgraphs of a specified type
- On treewidth and minimum fill-in of asteroidal triple-free graphs
- Quickly excluding a planar graph
- Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
- Robust algorithms for restricted domains
- Subexponential parameterized algorithm for minimum fill-in
- The Complexity of the Partial Order Dimension Problem
- The ellipsoid method and its consequences in combinatorial optimization
- The Erdős-Pósa property for long circuits
- The maximum k-colorable subgraph problem for chordal graphs
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The three-in-a-tree problem
- The Use of Linear Graphs in Gauss Elimination
- Treewidth and minimum fill-in: Grouping the minimal separators
- Treewidth and Pathwidth of Permutation Graphs
- Treewidth computation and extremal combinatorics
Cited in
(54)- iTri: index-based triangle listing in massive graphs
- Vertex deletion problems on chordal graphs
- Subexponential parameterized algorithms and kernelization on almost chordal graphs
- Subexponential-time algorithms for finding large induced sparse subgraphs
- Avoidable vertices and edges in graphs: existence, characterization, and applications
- Finding optimal triangulations parameterized by edge clique cover
- Structural parameterizations with modulator oblivion
- Summarized bit batch-based triangle listing in massive graphs
- On the tractability of optimization problems on \(H\)-graphs
- Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs
- 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
- Enumerating minimal connected dominating sets in graphs of bounded chordality
- On the number of minimal separators in graphs
- Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques
- Finding induced subgraphs via minimal triangulations
- On distance-\(d\) Independent Set and other problems in graphs with ``few minimal separators
- Largest chordal and interval subgraphs faster than \(2^n\)
- Solving graph problems via potential maximal cliques: an experimental evaluation of the Bouchitté-Todinca algorithm
- Reducing CMSO model checking to highly connected graphs
- A strongly-uniform slicewise polynomial-time algorithm for the embedded planar diameter improvement problem
- On the tractability of optimization problems on \(H\)-graphs
- On supergraphs satisfying CMSO properties
- An improvement of Reed's treewidth approximation
- scientific article; zbMATH DE number 7559431 (Why is no real title available?)
- On supergraphs satisfying CMSO properties
- scientific article; zbMATH DE number 7236457 (Why is no real title available?)
- Vertex deletion problems on chordal graphs
- Finding Large H-Colorable Subgraphs in Hereditary Graph Classes
- Large induced subgraphs via triangulations and CMSO
- scientific article; zbMATH DE number 7651174 (Why is no real title available?)
- scientific article; zbMATH DE number 7651188 (Why is no real title available?)
- On \(H\)-topological intersection graphs
- Structural parameterizations with modulator oblivion
- scientific article; zbMATH DE number 7764113 (Why is no real title available?)
- Treewidth versus clique number. II: Tree-independence number
- A meta-theorem for distributed certification
- New Width Parameters for Independent Set: One-Sided-Mim-Width and Neighbor-Depth
- An improved parameterized algorithm for treewidth
- Induced subgraphs of bounded treewidth and the container method
- Taming graphs with no large creatures and skinny ladders
- Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques
- Comparison of k-creature and t-critter
- Odd cycle transversal on P₅-free graphs in polynomial time
- Taming graphs with no large creatures and skinny ladders
- A polynomial bound on the number of minimal separators and potential maximal cliques in P₆-free graphs of bounded clique number
- Output-sensitive enumeration of potential maximal cliques in polynomial space
- Lower bounds on dynamic programming for maximum weight independent set
- Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity
- Tree decompositions meet induced matchings: beyond max weight independent set
- Tree decompositions meet induced matchings: beyond max weight independent set
- A polynomial delay algorithm generating all potential maximal cliques in triconnected planar graphs
- Sparse induced subgraphs in P₇-Free graphs of bounded clique number
- Large induced subgraphs with equated maximum degree
This page was built for publication: Large Induced Subgraphs via Triangulations and CMSO
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2954371)
