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

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Added link to MaRDI item.
links / mardi / namelinks / mardi / name
 

Revision as of 04:35, 1 February 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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references