Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach

DOI10.1007/978-3-642-22993-0_47MaRDI QIDQ3088068zbMATH OpenOpenAlexFDO

Authors Michał Pilipczuk

Publication date 17 August 2011

Published in Mathematical Foundations of Computer Science 2011 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60)

Abstract: We introduce a variant of modal logic, dubbed EXISTENTIAL COUNTING MODAL LOGIC (ECML), which captures a vast majority of problems known to be tractable in single exponential time when parameterized by treewidth. It appears that all these results can be subsumed by the theorem that model checking of ECML admits an algorithm with such complexity. We extend ECML by adding connectivity requirements and, using the Cut&Count technique introduced by Cygan et al. [4], prove that problems expressible in the extension are also tractable in single exponential time when parameterized by treewidth; however, using randomization. The need for navigationality of the introduced logic is justified by a negative result that two expository problems involving non-acyclic conditions, C_l VERTEX DELETION and GIRTH>l VERTEX DELETION for l>=5, do not admit such a robust algorithm unless Exponential Time Hypothesis fails.

Recommendations

• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Fixed-parameter tractability of treewidth and pathwidth
• Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth
• Parameterized and subexponential-time complexity of satisfiability problems and applications
• Parameterized and subexponential-time complexity of satisfiability problems and applications
• scientific article; zbMATH DE number 7650914
• Fixed-parameter tractability and characterizations of small special treewidth

Cited in

(35)

• The P3 infection time is W[1]-hard parameterized by the treewidth
• Subexponential parameterized algorithms and kernelization on almost chordal graphs
• Subexponential-time algorithms for finding large induced sparse subgraphs
• Hitting forbidden induced subgraphs on bounded treewidth graphs
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Hitting forbidden subgraphs in graphs of bounded treewidth
• Linear kernels for outbranching problems in sparse digraphs
• Parameterized complexity dichotomy for \((r, \ell)\)-\textsc{Vertex Deletion}
• scientific article; zbMATH DE number 7228418 (Why is no real title available?)
• Catalan structures and dynamic programming in \(H\)-minor-free graphs
• Lower bounds for dynamic programming on planar graphs of bounded cutwidth
• Hitting forbidden induced subgraphs on bounded treewidth graphs
• Parameterized complexity of fair vertex evaluation problems
• scientific article; zbMATH DE number 7204413 (Why is no real title available?)
• Contraction-bidimensionality of geometric intersection graphs
• Lower bounds for dynamic programming on planar graphs of bounded cutwidth
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Slightly superexponential parameterized problems
• Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs
• scientific article; zbMATH DE number 7651213 (Why is no real title available?)
• Close relatives of feedback vertex set without single-exponential algorithms parameterized by treewidth
• Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
• Cutting Barnette graphs perfectly is hard
• Twin-treewidth: a single-exponential logic-based approach
• Towards tight bounds for the graph homomorphism problem parameterized by cutwidth via asymptotic matrix parameters
• Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover
• Stretch-width
• Parameterized max min feedback vertex set
• Tight bounds for chordal/interval vertex deletion parameterized by treewidth
• Fine-grained meta-theorems for vertex integrity
• Degrees and gaps: tight complexity results of general factor problems parameterized by treewidth and cutwidth
• Tight (double) exponential bounds for identification problems: locating-dominating set and test cover
• Metric dimension and geodetic set parameterized by vertex cover
• First order logic on pathwidth revisited again
• Contraction bidimensionality of geometric intersection graphs

This page was built for publication: Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach

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