Subexponential parameterized algorithms and kernelization on almost chordal graphs

DOI10.1007/S00453-021-00822-XzbMATH Open1467.05254arXiv2002.08226OpenAlexW3082325482MaRDI QIDQ2037110FDOQ2037110

Authors: Fedor V. Fomin, Petr A. Golovach 

Publication date: 30 June 2021

Published in: Algorithmica (Search for Journal in Brave)

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.

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

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}

zbMATH Keywords

chordal graphscliqueindependent setparameterized complexitycoloringkernelizationstructural parameterizationsubexponential algorithmsfill-in

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)

Cites Work

• Fundamentals of parameterized complexity
• Title not available (Why is that?)
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Title not available (Why is that?)
• Graph Classes: A Survey
• Cluster editing with locally bounded modifications
• Geometric algorithms and combinatorial optimization.
• Which problems have strongly exponential complexity?
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Smallest-last ordering and clustering and graph coloring algorithms
• Algorithms on circular-arc graphs
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Parameterized algorithms
• On the complexity of \(k\)-SAT
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Representation of a finite graph by a set of intervals on the real line
• Kernelization Lower Bounds by Cross-Composition
• Large Induced Subgraphs via Triangulations and CMSO
• Sparsity. Graphs, structures, and algorithms
• Minimal triangulations of graphs: a survey
• The splittance of a graph
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• 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
• An application of simultaneous diophantine approximation in combinatorial optimization
• Parameterized complexity of vertex colouring
• Computing the Minimum Fill-In is NP-Complete
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Title not available (Why is that?)
• Complexity classification of some edge modification problems
• Parameterized coloring problems on chordal graphs
• Chordal deletion is fixed-parameter tractable
• The Use of Linear Graphs in Gauss Elimination
• On chromatic number of graphs and set-systems
• Data reduction for graph coloring problems
• Interval deletion is fixed-parameter tractable
• Subexponential parameterized algorithm for minimum fill-in
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• A characterisation of rigid circuit graphs
• Interval Completion Is Fixed Parameter Tractable
• Polynomial kernels for proper interval completion and related problems
• New Approximation Techniques for Some Linear Ordering Problems
• Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
• Linear recognition of almost interval graphs
• A Polynomial Kernel for Proper Interval Vertex Deletion
• Faster parameterized algorithms for \textsc{Minimum Fill-in}
• Efficient computation of representative families with applications in parameterized and exact algorithms
• Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Approximation and kernelization for chordal vertex deletion
• Feedback vertex set inspired kernel for chordal vertex deletion
• Kernelization. Theory of parameterized preprocessing
• Vertex Coloring of Comparability+ke and –ke Graphs
• Title not available (Why is that?)
• Subexponential parameterized algorithm for {\textsc{Interval Completion}}
• Minimum fill-in: inapproximability and almost tight lower bounds
• A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary
• Interval vertex deletion admits a polynomial kernel

Cited In (7)

• Approximating the \textsc{Sparsest} \(k\)-\textsc{Subgraph} in chordal graphs
• Treewidth versus clique number. II: Tree-independence number
• Subexponential parameterized algorithms for graphs of polynomial growth
• Fair allocation algorithms for indivisible items under structured conflict constraints
• Structural parameterizations with modulator oblivion
• Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs
• Sublinear-time algorithms for approximating graph parameters

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)