Reconfiguration on nowhere dense graph classes (Q1658772): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
ReferenceBot (talk | contribs)
Changed an Item
 
(2 intermediate revisions by 2 users not shown)
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / arXiv ID
 
Property / arXiv ID: 1707.06775 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Recoloring graphs via tree decompositions / rank
 
Normal rank
Property / cites work
 
Property / cites work: The complexity of rerouting shortest paths / rank
 
Normal rank
Property / cites work
 
Property / cites work: Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration / rank
 
Normal rank
Property / cites work
 
Property / cites work: Token jumping in minor-closed classes / rank
 
Normal rank
Property / cites work
 
Property / cites work: Connectedness of the graph of vertex-colourings / rank
 
Normal rank
Property / cites work
 
Property / cites work: Mixing 3-colourings in bipartite graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Finding paths between 3-colorings / rank
 
Normal rank
Property / cites work
 
Property / cites work: Parameterized Algorithms / rank
 
Normal rank
Property / cites work
 
Property / cites work: Domination Problems in Nowhere-Dense Classes / rank
 
Normal rank
Property / cites work
 
Property / cites work: Graph Theory / rank
 
Normal rank
Property / cites work
 
Property / cites work: Fundamentals of parameterized complexity / rank
 
Normal rank
Property / cites work
 
Property / cites work: Kernelization and Sparseness: the case of Dominating Set / rank
 
Normal rank
Property / cites work
 
Property / cites work: Neighborhood complexity and kernelization for nowhere dense classes of graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Parametrized complexity theory. / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies / rank
 
Normal rank
Property / cites work
 
Property / cites work: Deciding First-Order Properties of Nowhere Dense Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: The \(k\)-dominating graph / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Complexity of Dominating Set Reconfiguration / rank
 
Normal rank
Property / cites work
 
Property / cites work: PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation / rank
 
Normal rank
Property / cites work
 
Property / cites work: Approximability of the Subset Sum Reconfiguration Problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the complexity of reconfiguration problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Reconfiguration of list edge-colorings in a graph / rank
 
Normal rank
Property / cites work
 
Property / cites work: Fixed-Parameter Tractability of Token Jumping on Planar Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Parameterized Complexity for Token Jumping on Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Shortest paths between shortest paths / rank
 
Normal rank
Property / cites work
 
Property / cites work: Complexity of independent set reconfigurability problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4607889 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Reconfiguration on sparse graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas / rank
 
Normal rank
Property / cites work
 
Property / cites work: Vertex Cover Reconfiguration and Beyond / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the parameterized complexity of reconfiguration problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Reconfiguration over Tree Decompositions / rank
 
Normal rank
Property / cites work
 
Property / cites work: First order properties on nowhere dense structures / rank
 
Normal rank
Property / cites work
 
Property / cites work: On nowhere dense graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Introduction to reconfiguration / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the number of types in sparse graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3194807 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The complexity of change / rank
 
Normal rank
Property / cites work
 
Property / cites work: Reconfiguration in bounded bandwidth and tree-depth / rank
 
Normal rank

Latest revision as of 07:59, 16 July 2024

scientific article
Language Label Description Also known as
English
Reconfiguration on nowhere dense graph classes
scientific article

    Statements

    Reconfiguration on nowhere dense graph classes (English)
    0 references
    0 references
    15 August 2018
    0 references
    Summary: Let \(\mathcal{Q}\) be a vertex subset problem on graphs. In a reconfiguration variant of \(\mathcal{Q}\) we are given a graph \(G\) and two feasible solutions \(S_s, S_t\subseteq V(G)\) of \(\mathcal{Q}\) with \(|S_s|=|S_t|=k\). The problem is to determine whether there exists a sequence \(S_1,\ldots,S_n\) of feasible solutions, where \(S_1=S_s\), \(S_n=S_t\), \(|S_i|\leq k\pm 1\), and each \(S_{i+1}\) results from \(S_i\), \(1\leq i<n\), by the addition or removal of a single vertex. We prove that for every nowhere dense class of graphs and for every integer \(r\geqslant 1\) there exists a polynomial \(p_r\) such that the reconfiguration variants of the distance-\(r\) independent set problem and the distance-\(r\) dominating set problem admit kernels of size \(p_r(k)\). If \(k\) is equal to the size of a minimum distance-\(r\) dominating set, then for any fixed \(\varepsilon>0\) we even obtain a kernel of almost linear size \(\mathcal O(k^{1+\varepsilon})\). We then prove that if a class \(\mathcal C\) is somewhere dense and closed under taking subgraphs, then for some value of \(r\geqslant 1\) the reconfiguration variants of the above problems on \(\mathcal C\) are \(\mathsf{W}[1]\)-hard (and in particular we cannot expect the existence of kernelization algorithms). Hence our results show that the limit of tractability for the reconfiguration variants of the distance-\(r\) independent set problem and distance-\(r\) dominating set problem on sub-graph closed graph classes lies exactly on the boundary between nowhere denseness and somewhere denseness.
    0 references
    reconfiguration
    0 references
    dominating set
    0 references
    independent set
    0 references
    sparse graph classes
    0 references
    nowhere dense graphs
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references