Subexponential parameterized algorithms and kernelization on almost chordal graphs
From MaRDI portal
Publication:2037110
Abstract: We study the algorithmic properties of the graph class Chordal-ke, that is, graphs that can be turned into a chordal graph by adding at most k edges or, equivalently, the class of graphs of fill-in at most k. We discover that a number of fundamental intractable optimization problems being parameterized by k admit subexponential algorithms on graphs from Chordal-ke. We identify a large class of optimization problems on Chordal-ke that admit algorithms with the typical running time 2^{O(sqrt{k}log k)}cdot n^{O(1)}. Examples of the problems from this class are finding an independent set of maximum weight, finding a feedback vertex set or an odd cycle transversal of minimum weight, or the problem of finding a maximum induced planar subgraph. On the other hand, we show that for some fundamental optimization problems, like finding an optimal graph coloring or finding a maximum clique, are FPT on Chordal-ke when parameterized by k but do not admit subexponential in k algorithms unless ETH fails. Besides subexponential time algorithms, the class of Chordal-ke graphs appears to be appealing from the perspective of kernelization (with parameter k). While it is possible to show that most of the weighted variants of optimization problems do not admit polynomial in k kernels on Chordal-ke graphs, this does not exclude the existence of Turing kernelization and kernelization for unweighted graphs. In particular, we construct a polynomial Turing kernel for Weighted Clique on Chordal-ke graphs. For (unweighted) Independent Set we design polynomial kernels on two interesting subclasses of Chordal-ke, namely, Interval-ke and Split-ke graphs.
Recommendations
- scientific article; zbMATH DE number 7053390
- Subexponential parameterized algorithm for minimum fill-in
- Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs
- Approximation and kernelization for chordal vertex deletion
- Faster parameterized algorithms for \textsc{Minimum Fill-in}
Cites work
- A characterisation of rigid circuit graphs
- A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary
- A Polynomial Kernel for Proper Interval Vertex Deletion
- Algorithmic Aspects of Vertex Elimination on Graphs
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- Algorithms on circular-arc graphs
- An application of simultaneous diophantine approximation in combinatorial optimization
- Approximation and kernelization for chordal vertex deletion
- Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques
- Chordal deletion is fixed-parameter tractable
- Cluster editing with locally bounded modifications
- Complexity classification of some edge modification problems
- Computing the Minimum Fill-In is NP-Complete
- Data reduction for graph coloring problems
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Efficient computation of representative families with applications in parameterized and exact algorithms
- Faster parameterized algorithms for \textsc{Minimum Fill-in}
- Feedback vertex set inspired kernel for chordal vertex deletion
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Fundamentals of parameterized complexity
- Geometric algorithms and combinatorial optimization.
- Graph Classes: A Survey
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1775386 (Why is no real title available?)
- scientific article; zbMATH DE number 3420184 (Why is no real title available?)
- Interval Completion Is Fixed Parameter Tractable
- Interval deletion is fixed-parameter tractable
- Interval vertex deletion admits a polynomial kernel
- Kernelization Lower Bounds by Cross-Composition
- Kernelization. Theory of parameterized preprocessing
- Large Induced Subgraphs via Triangulations and CMSO
- Linear recognition of almost interval graphs
- Minimal triangulations of graphs: a survey
- Minimum fill-in: inapproximability and almost tight lower bounds
- New Approximation Techniques for Some Linear Ordering Problems
- On chromatic number of graphs and set-systems
- On the complexity of k-SAT
- Parameterized algorithms
- Parameterized coloring problems on chordal graphs
- Parameterized complexity of vertex colouring
- Polynomial kernels for proper interval completion and related problems
- Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
- Representation of a finite graph by a set of intervals on the real line
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Smallest-last ordering and clustering and graph coloring algorithms
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Sparsity. Graphs, structures, and algorithms
- Subexponential parameterized algorithm for {\textsc{Interval Completion}}
- Subexponential parameterized algorithm for minimum fill-in
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The splittance of a graph
- The Use of Linear Graphs in Gauss Elimination
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- Vertex Coloring of Comparability+ke and –ke Graphs
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Which problems have strongly exponential complexity?
Cited in
(9)- Sublinear-time algorithms for approximating graph parameters
- Structural parameterizations with modulator oblivion
- Approximating the \textsc{Sparsest} \(k\)-\textsc{Subgraph} in chordal graphs
- Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs
- Subexponential parameterized algorithms for graphs of polynomial growth
- Fair allocation algorithms for indivisible items under structured conflict constraints
- Treewidth versus clique number. II: Tree-independence number
- Computing tree decompositions with small independence number
- Multicut problems in embedded graphs: the dependency of complexity on the demand pattern
This page was built for publication: Subexponential parameterized algorithms and kernelization on almost chordal graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2037110)
