Pathfinding in Self-Deleting Graphs

Several variants of pathfinding with restrictions on vertices and edges have been studied.

Wojciechowski et al. [21] introduced a problem called Optional Choice Reachability, where we are given a graph together with a set $S$ of pairs of edges, and we are asked to find an $s$-$t$ path that contains at most one edge from each pair in $S$. They showed that this problem is NP-complete even on directed acyclic graphs (DAGs) of pathwidth 2 and FPT parameterized by $|S|$.

The vertex analogue of this problem, where we are given a set of pairs of vertices and we are required to use at most one of them from each pair was introduced by Krause et al. [19]. On the one hand, the problem is NP-hard even for DAGs [13], even if the set of pairs has a specific structure, such as overlapping [17] or ordered [18]. On the other hand, it is polynomial time solvable, if the structure is well-parenthesized [17], halving [17], or nested [9], or in other special cases [24]. Notably, Bodlaender et al. [3] studied the problem from parameterized perspective on undirected graphs, showing that it is W[1]-hard w.r.t. vertex cover number of the input graph $G$, but FPT w.r.t. vertex cover number of graph $H$ or treewidth of graph $G\cup H$, where graph $H$ has an edge for each forbidden pair. Moreover, it does not admit polynomial kernel w.r.t. vertex cover number of graph $G\cup H$, unless $\mathrm{𝖭𝖯}\subseteq \mathrm{𝖼𝗈𝖭𝖯}{/}_{\mathrm{poly}}$ [3].

Szeider [20] studied the problem of finding a path where for each vertex, only certain combinations of incoming and outgoing edges are permitted. He provides a dichotomy between the cases which are NP-hard and cases which are linear time solvable, based on the structure of permitted combinations. In the variant where the cost of each arc depends on previously traversed arcs, introduced by Kirby and Potts [16], the shortest walk can be found in polynomial time [2, 25], but finding the shortest path is NP-hard and hard to approximate [22]. In the variant with exclusive-disjunction arc pairs conflicts, introduced by Cerulli et al. [6], we are given pairs of arcs and we have to pay a penalty if the path contains either none of the arcs or both of them. The goal is to find a path minimizing the sum of length of edges and the penalties paid. They show that the problem is NP-hard and provide heuristics.

In Section 3, we consider the (classical) complexity of (Shortest) Self-Deleting $s$-$t$-path. Our first result is that Self-Deleting $s$-$t$-path is NP-hard even on a very restricted graph class, namely outerplanar bipartite graphs of maximum degree 3. Moreover, as we show in Corollary 3.4, the result holds even when the self-deleting graph deletes at most one edge for each vertex (i.e., $|f(v)|\le 1$ for all $v$). Next, we show a separation between Self-Deleting $s$-$t$-path and Shortest Self-Deleting $s$-$t$-path: namely, on cactus graphs the former problem can be solved in linear time, whereas the latter is NP-hard (Theorems 3.10 and 3.11 respectively).

In Section 4, we turn our attention to parameterized complexity. Firstly, we consider the parameterization of Shortest Self-Deleting $s$-$t$-path by solution size, and in Theorem 4.3 we show that it is $𝖶[\mathrm{𝟣}]$-complete. For most structural parameters, Self-Deleting $s$-$t$-path turns out to be para-NP-hard or $𝖶[\mathrm{𝟣}]$-complete. For an overview of our results on parameterizations by structural parameters, see Figure 1.

In order to make the problem tractable, we consider the case of bounded deletion set size (i.e. we parameterize the problem by $\mu ={\max }_{v\in V}|f(v)|$). Although this parameterization alone does not make the problem tractable (in particular, we show that Shortest Self-Deleting $s$-$t$-path is para-NP-hard parameterized by $\mu$), it turns out that the parameterization by $\mu$ and $k$ (the number of vertices of the sought path) leads to an FPT algorithm. This result allows us to obtain several FPT algorithms for parameterizations by $\mu$ and structural parameters, such as vertex cover number, vertex integrity and treedepth. Using the results of Dvořák et al. [12] on the number of edges in traceable graphs with dense structure, we obtain FPT algorithms for several dense parameters and $\mu$, such as neighborhood diversity, shrub-depth, modular-width, and size of maximum induced matching. For an overview of our results about parameterizations by structural parameters and $\mu$, refer to Figure 2.

Lastly, in Section 5, we consider kernelizing the problem. We show that, under standard parameterized complexity assumptions, Self-Deleting $s$-$t$-path does not admit a polynomial kernel parameterized by $\mu$ and vertex cover number even on $2$-outerplanar graphs. On the positive side, we obtain a linear kernel for the parameterization by feedback edge number and linear kernel for the parameterization by vertex cover number on outerplanar graphs. Moreover, while Self-Deleting $s$-$t$-path does not admit a classical kernel parameterized by $\mu$ on cliques, we obtain a linear Turing kernel on cliques parameterized by $\mu$.

We use standard notations, terminology, and definitions of graph theory, refer to Diestel [11] for those. Unless explicitly stated, we consider simple undirected graphs. We denote a $v_1$–$v_k$ walk (or path) in a graph by the sequence $(v_1,e_1,v_2,\mathrm{\dots },e_{k-1},v_k)$ of vertices $v_i$ and edges $e_i$, where $e_i=\{v_i,v_{i+1}\}$. For brevity, we may sometimes omit the edges and write just the sequence of vertices. We denote by $\mathrm{cc}(G)$ the number of connected components of a graph $G$. A graph is a cactus if every edge lies on at most one cycle. A graph is a block graph if every vertex-$2$-connected component is a clique. A $2\times \mathrm{\ell }$ grid for some positive integer $\mathrm{\ell }$ is a ladder. The class of cographs is the minimal class of graphs containing the one-vertex graph and closed under complete joins and disjoint unions of two graphs.

A self-deleting graph is an ordered pair $(G,f)$, where $G=(V,E)$ is an undirected graph and $f$ is a function $f:V\to 2^E$. We write $G$ instead of $(G,f)$ if $f$ is clear from the context. The function $f$ is called the deletion function. Let $(G,f)$ be a self-deleting graph. A path or walk $(v_1,e_1,v_2,e_2,\mathrm{\dots },e_{k-1},v_k)$ in $G$ is $f$-conforming if for every $j\le i$ we have $e_i\notin f(v_j)$. We denote ${\mu }_f={\max }_{v\in V}|f(v)|$ and $|f|={\sum }_{v\in V}|f(v)|$. If $f$ is clear from the context, we omit the lower index and write just $\mu$. Central to our paper are the two decision problems Self-Deleting $s$-$t$-path and Shortest Self-Deleting $s$-$t$-path. In Self-Deleting $s$-$t$-path we are given a self-deleting graph $(G,f)$ and two vertices $s,t\in V(G)$ and the task is to decide if there is an $f$-conforming $s$-$t$ path in $G$. In Shortest Self-Deleting $s$-$t$-path we are in addition given a positive integer $k$ and the task is to decide if there is an $f$-conforming $s$-$t$ path in $G$ on at most $k$ vertices.

We assume that $\mu \ge 1$ as otherwise the problems are trivial. Moreover, if $\mu$ appears in the base of an exponential or in a logarithm, $\mu$ should be replaced by $\max \{\mu ,2\}$ in order to avoid degenerate cases. We stick to writing $\mu$ for the sake of readability.

We assume the reader is familiar with parameterized complexity. For definitions and comprehensive overview, refer to the monograph of Cygan et al. [10]. In our work we consider the following structural parameters: bandwidth ($\mathrm{bw}$), distance to clique ($\mathrm{dtc}$), vertex cover number ($\mathrm{vcn}$), domination number ($\gamma$), maximum induced matching ($\mathrm{mim}$), neighborhood diversity ($\mathrm{nd}$), diameter ($\mathrm{diam}$), cluster vertex deletion number ($\mathrm{cvdn}$), feedback vertex set number ($\mathrm{fvsn}$), distance to linear forest ($\mathrm{dtlf}$), vertex integrity ($\mathrm{vi}$), feedback edge number ($\mathrm{fen}$), treedepth ($\mathrm{td}$), distance to cograph ($\mathrm{dtcog}$), modular-width ($\mathrm{mw}$), and shrub-depth ($\mathrm{sd}$). Formal definitions of all the parameters can be found in the full version of this paper.

Exponential Time Hypothesis (ETH), introduced by Impagliazzo, Paturi and Zane [14, 15] asserts, roughly speaking, that there is no algorithm for $3$Sat in time $2^{o(n^{\prime })}$, where $n^{\prime }$ is the number of variables of the input formula. In fact, even $2^{o(n^{\prime }+m^{\prime })}$ algorithm is ruled out by using the Sparsification Lemma [15], where $m^{\prime }$ is the number of clauses of the input formula. We also utilize the result of Chen, Huang, Kanj, and Xia [7, 8] that there is no $g(k)n^{o(k)}$ algorithm for (Multicolored) Clique for any computable function $g$ unless ETH fails.

Statements where proofs or details are omitted due to space constraints are marked with $\star$. The omitted material is available in the full version of this paper.

Use Construction 3.1 with the following modification. Replace the vertex $T_x$ (resp. $F_x$) by a path on $|f(T_x)|$ (resp. $|f(F_x)|$) vertices and delete one edge of the original set $f(v)$ on each vertex of the path to obtain $|f(v)|\le 1$. $◀$

Since the resulting graph of Construction 3.1 is a subgraph of a ladder of size $O(n^{\prime }+m^{\prime })$, it is straightforward to obtain the following corollary:

We can also easily obtain hardness on cliques by adding all non-existent incident edges to the deletion set of every vertex. However, as we will see later, we cannot hope to upper bound $\mu$ by a constant in cliques and preserve NP-hardness (˜4.21 and 5.3).

Corollaries 3.7 and 3.8 show that even if we allow a slight generalization of trees, the problem becomes NP-hard. One particular non-trivial case that allows for a polynomial-time algorithm is the class of cactus graphs. We show that when restricted to cactus graphs, Self-Deleting $s$-$t$-path becomes polynomial-time solvable (Theorem 3.10). Interestingly, deciding an existence of an $f$-conforming path is easy, however Shortest Self-Deleting $s$-$t$-path remains NP-hard even in cactus graphs (Theorem 3.11). Note that in cactus graphs each edge lies on at most $1$ cycle, whereas the graph resulting from Construction 3.1 has each edge on at most $2$ cycles so the problem becomes NP-hard in this case.

Consider the block-cut tree of $G$ and note that we can only restrict ourselves to the part of $G$ that contains the $s$-$t$ path in the block-cut tree of $G$. This part consists of cycles and bridges. In each cycle we have two options to choose from. Each choice possibly forbids some choices in the future. This can be encoded as an implication of the type if we choose this path, then we cannot choose some other path in the future. We can thus reduce the problem to $2$Sat. Details can be found in the full version of this paper. $◀$

We provide a polynomial reduction from Independent Set. For each vertex we introduce one cycle on the designated $s$-$t$-path (in the block-cut tree). One of the paths corresponds to taking the vertex and the other to not taking it. Inclusion of a vertex forbids inclusion of any of its neighbors by deleting an edge of the appropriate path. Crucially, the inclusion path is shorter, so the desired length of the path forces an appropriate number of vertices to be included in the independent set. $◀$

We provide an OR-cross-composition of $3$Sat into Self-Deleting $s$-$t$-path parameterized by $\mathrm{vcn}$ and $\mu$. The idea is to use Construction 3.1 for a formula with all $O(n^3)$ clauses with auxiliary skip edges that allow to pass a clause for free. Before $s$ we prepend selector vertices for $\tau$ instances that will delete appropriate skip edges and thus modify the rest of the graph to look like the reduction for the given formula. Details can be found in the full version of this paper. $◀$