Reconfiguration over tree decompositions

DOI10.1007/978-3-319-13524-3_21MaRDI QIDQ2946023zbMATH OpenOpenAlexFDO

Authors Amer E. Mouawad, N. Nishimura, Venkatesh Raman, Marcin Wrochna

Publication date 15 September 2015

Published in Parameterized and Exact Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Logic in computer science (03B70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Abstract: A vertex-subset graph problem $Q$ defines which subsets of the vertices of an input graph are feasible solutions. The reconfiguration version of a vertex-subset problem $Q$ asks whether it is possible to transform one feasible solution for $Q$ into another in at most $ell$ steps, where each step is a vertex addition or deletion, and each intermediate set is also a feasible solution for $Q$ of size bounded by $k$. Motivated by recent results establishing W[1]-hardness of the reconfiguration versions of most vertex-subset problems parameterized by $ell$, we investigate the complexity of such problems restricted to graphs of bounded treewidth. We show that the reconfiguration versions of most vertex-subset problems remain PSPACE-complete on graphs of treewidth at most $t$ but are fixed-parameter tractable parameterized by $ell+t$ for all vertex-subset problems definable in monadic second-order logic (MSOL). To prove the latter result, we introduce a technique which allows us to circumvent cardinality constraints and define reconfiguration problems in MSOL.

Recommendations

• Reconfiguration in bounded bandwidth and tree-depth

Cited in

(19)

• Reconfiguration on nowhere dense graph classes
• Reconfiguration in bounded bandwidth and tree-depth
• On reconfigurability of target sets
• Parameterized complexity of independent set reconfiguration problems
• Using contracted solution graphs for solving reconfiguration problems
• Introduction to reconfiguration
• Rerouting shortest paths in planar graphs
• Computing the flip distance between triangulations
• Shortest reconfiguration of sliding tokens on subclasses of interval graphs
• Reconfiguration of cliques in a graph
• Shortest Reconfiguration of Sliding Tokens on a Caterpillar
• Sliding tokens on block graphs
• Linear-time algorithm for sliding tokens on trees
• Shortest reconfiguration paths in the solution space of Boolean formulas
• Algorithmic meta-theorems for combinatorial reconfiguration revisited
• Bipartite independent set reconfiguration: general and RNA-inspired parameterized algorithms
• Algorithmic meta-theorems for combinatorial reconfiguration revisited
• Some results on vertex separator reconfiguration
• Token sliding reconfiguration on DAGs

This page was built for publication: Reconfiguration over tree decompositions

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