Search

In Graph Searching, a team of searchers aims at capturing an invisible fugitive moving arbitrarily fast in a graph. Equivalently, the searchers try to clear a contaminated network. The problem is to compute the minimum number of searchers required to accomplish this task. Several variants of Graph Searching have been studied mainly because of their close relationship with the pathwidth of a graph. In this paper, we study the complexity of the Exclusive Graph Searching variant. We show that the problem is NP-hard in planar graphs and it can be solved in linear-time in the class of cographs. We also show that monotone Exclusive Graph Searching is NP-complete in split graphs where Pathwidth is known to be solvable in polynomial time. Moreover, we prove that monotone Exclusive Graph Searching is in P in a subclass of star-like graphs where Pathwidth is known to be NP-hard. [ABSTRACT FROM AUTHOR]

In the mixed Chinese postman problem (MCPP), given a weighted mixed graph G (it may have both edges and arcs), our aim is to find a closed walk of minimum weight traversing each edge and arc at least once. The MCPP parameterized by the number of edges in G or the number of arcs in G is fixed-parameter tractable as proved by van Bevern et al. in 2014 and Gutin, Jones, and Sheng in 2014, respectively. Solving an open question of van Bevern et al., we show that somewhat unexpectedly the MCPP parameterized by the (undirected) treewidth of G is W[1]-hard. In fact, we prove that even the unweighted MCPP parameterized by the pathwidth of G is W[1]-hard. On the positive side, we show that MCPP parameterized by treedepth is fixed-parameter tractable (even with arbitrary integer weights). We are unaware of any widely studied graph parameters between pathwidth and treedepth and so our results provide a close characterization of the complexity of MCPP. [ABSTRACT FROM AUTHOR]

We consider a bicriterion generalization of the pathwidth problem: given integers k , l and a graph G , does there exist a path decomposition of G of width at most k and length (i.e., number of bags) at most l ? We provide a complete complexity classification of the problem in terms of k and l for general graphs. Contrary to the original pathwidth problem, which is fixed-parameter tractable with respect to k , the generalized problem is NP-complete for any fixed k ≥ 4 , and also for any fixed l ≥ 2 . On the other hand, we give a polynomial-time algorithm that constructs a minimum-length path decomposition of width at most k ≤ 3 for any disconnected input graph. As a by-product, we obtain an almost complete classification for connected graphs: the problem is NP-complete for any fixed k ≥ 5 , and polynomial for any k ≤ 3 . [ABSTRACT FROM AUTHOR]

We prove a general reduction theorem which allows us to extend bounds for certain graph parameters on cubic graphs to bounds for general graphs taking into account the individual vertex degrees. As applications, we give an algorithm for Max $$2$$ -CSP whose complexity matches the algorithm of Scott and Sorkin in the case of $$d$$ -regular graphs, $$d \le 5$$ , but is otherwise faster. It also improves on the previously fastest known algorithm in terms of the average degree, given by Golovnev and Kutzkov. Also from the general theorem, we derive a bound for the pathwidth of a general graph which equals that of Fomin et al. and Gaspers for graphs of degree at most $$6$$ , but is smaller otherwise, and use this to give an improved exponential-space algorithm for Max $$2$$ -CSP. Finally we use the general result to give a faster algorithm for Max $$2$$ -CSP on claw-free graphs. [ABSTRACT FROM AUTHOR]