In this paper, we prove that, given a clique-width k-expression of an n-vertex graph, Hamiltonian Cycle can be solved in time nO(k) This improves the naive algorithm that runs in time nO(k2) by Espelage et al. (Graph-...
详细信息
In this paper, we prove that, given a clique-width k-expression of an n-vertex graph, Hamiltonian Cycle can be solved in time nO(k) This improves the naive algorithm that runs in time nO(k2) by Espelage et al. (Graph-theoretic concepts in computer science, vol 2204. Springer, Berlin, 2001), and it also matches with the lower bound result by Fomin et al. that, unless the Exponential Time Hypothesis fails, there is no algorithm running in time no(k) (Fomin et al. in SIAM J Comput 43:1541-1563, 2014). We present a technique of representative sets using two-edge colored multigraphs on k vertices. The essential idea is that, for a two-edge colored multigraph, the existence of an Eulerian trail that uses edges with different colors alternately can be determined by two information: the number of colored edges incident with each vertex, and the connectedness of the multigraph. With this idea, we avoid the bottleneck of the naive algorithm, which stores all the possible multigraphs on k vertices with at most n edges.
The Terrain Guarding problem is a well-known variant of the famous Art Gallery problem. Only second to Art Gallery, it is the most well-studied visibility problem in Discrete and Computational Geometry, which has also...
详细信息
The Terrain Guarding problem is a well-known variant of the famous Art Gallery problem. Only second to Art Gallery, it is the most well-studied visibility problem in Discrete and Computational Geometry, which has also attracted attention from the viewpoint of Parameterized complexity. In this paper, we focus on the parameterized complexity of Terrain Guarding (both discrete and continuous) with respect to two natural parameters. First we show that, when parameterized by the number r of reflex vertices in the input terrain, the problem has a polynomial kernel. We also show that, when parameterized by the number c of minima in the terrain, Discrete Orthogonal Terrain Guarding has an xp algorithm.
In the (s, d)-spy game over a graph G, k guards and one spy occupy some vertices of G and, at each turn, the spy may move with speed s(along at most sedges) and each guard may move along one edge. The spy and the guar...
详细信息
In the (s, d)-spy game over a graph G, k guards and one spy occupy some vertices of G and, at each turn, the spy may move with speed s(along at most sedges) and each guard may move along one edge. The spy and the guards may occupy the same vertices. The spy wins if she reaches a vertex at distance more than the surveilling distance d from every guard. This game was introduced by Cohen et al. (2016) [15] and is related to two wellstudied games: Cops and Robber game and Eternal Dominating game. The guard number gns,d(G) is the minimum number of guards such that the guards have a winning strategy (of controlling the spy) in the graph G. In 2018, it was proved that deciding if the spy has a winning strategy is NP-hard for every speed s >= 2and distance d >= 0. In this paper, we initiate the investigation of the guard number in grids and in graph products. We obtain a strict upper bound on the strong product of two general graphs and obtain examples with King grids that match this bound and other examples for which the guard number is smaller. We also obtain the exact value of the guard number in the lexicographical product of two general graphs for any distance d >= 2. From the algorithmic point of view, we prove a positive result: if the number k of guards is fixed, the spy game is solvable in polynomial xp time O(n(3k+2)) for every speed s >= 2and distance d = 0. In other words, the spy game is xp when parameterized by the number of guards. This xp algorithm is used to obtain an FPT algorithm on the P-4-fewness of the graph. As a negative result, we prove that the spy game is W[2]-hard even in bipartite graphs when parameterized by the number of guards, for every speed s >= 2and distance d >= 0, extending the hardness result of Cohen et al. in 2018. (c) 2022 Elsevier B.V. All rights reserved.
Mim-width and sim-width are among the most powerful graph width parameters, with sim-width more powerful than mim-width, which is in turn more powerful than clique-width. While several NP-hard graph problems become tr...
详细信息
Mim-width and sim-width are among the most powerful graph width parameters, with sim-width more powerful than mim-width, which is in turn more powerful than clique-width. While several NP-hard graph problems become tractable for graph classes whose mim-width is bounded and quickly computable, no algorithmic applications of boundedness of sim-width are known. In Kang et al. (2017) [32], it is asked whether INDEPENDENT SET and 3-COLOURING are NP-complete on graphs of sim-width at most 1. We observe that, for each k is an element of N, LISTk-COLOURING is polynomial-time solvable for graph classes whose sim-width is bounded and quickly computable. Moreover, we show that if the same holds for INDEPENDENT SET, then INDEPENDENT H-PACKING is polynomial-time solvable for graph classes whose sim-width is bounded and quickly computable. This problem is a common generalisation of INDEPENDENT SET, INDUCED MATCHING, DISSOCIATION SET and k -*** also make progress toward classifying the mim-width of (H1, H2)-free graphs in the case H1 is complete or edgeless. Our results solve some open problems in Brettell et al. (2022) [6].(c) 2023 Elsevier B.V. All rights reserved.
In the (s, d)-spy game over a graph G, k guards and one spy occupy some vertices of G and, at each turn, the spy may move with speed s (along at most s edges) and each guard may move along one edge. The spy and the gu...
详细信息
ISBN:
(纸本)9783030895433;9783030895426
In the (s, d)-spy game over a graph G, k guards and one spy occupy some vertices of G and, at each turn, the spy may move with speed s (along at most s edges) and each guard may move along one edge. The spy and the guards may occupy the same vertices. The spy wins if she reaches a vertex at distance more than the surveilling distance d from every guard. This game was introduced by Cohen et al. in 2016 and is related to two well-studied games: Cops and robber game and Eternal Dominating game. The guard number gn(s,d)(G) is the minimum number of guards such that the guards have a winning strategy (of controlling the spy) in the graph G. In 2018, it was proved that deciding if the spy has a winning strategy is NP-hard for every speed s >= 2 and distance d >= 0. In this paper, we initiate the investigation of the guard number in grids and in graph products. We obtain a strict upper bound on the strong product of two general graphs and obtain examples with King grids that match this bound and other examples for which the guard number is smaller. We also obtain the exact value of the guard number in the lexicographical product of two general graphs for any distance d >= 2. From the algorithmic point of view, we prove a positive result: if the number k of guards is fixed, the spy game is solvable in polynomial xp time O(n(3k+2)) for every speed s >= 2 and distance d >= 0. This xp algorithm is used to obtain an FPT algorithm on the P-4-fewness of the graph. As a negative result, we prove that the spy game is W[2]-hard even in bipartite graphs when parameterized by the number of guards, for every speed s >= 2 and distance d >= 0, extending the hardness result of Cohen et al. in 2016.
Belmonte and Vatshelle (TCS 2013) used mim-width, a graph width parameter bounded on interval graphs and permutation graphs, to explain existing algorithms for many domination-type problems on those graph classes. We ...
详细信息
Belmonte and Vatshelle (TCS 2013) used mim-width, a graph width parameter bounded on interval graphs and permutation graphs, to explain existing algorithms for many domination-type problems on those graph classes. We investigate new graph classes of bounded mim-width, strictly extending interval graphs and permutation graphs. The graphs K-t boxed minus K-t and K-t boxed minus S-t are graphs obtained from the disjoint union of two cliques of size t, and one clique of size t and one independent set of size t respectively, by adding a perfect matching. We prove that: interval graphs are (K-3 boxed minus S-3)-free chordal graphs;and (K-t boxed minus S-t)-free chordal graphs have mim-width at most t - 1, permutation graphs are (K-3 boxed minus K-3)-free co-comparability graphs;and (K-t boxed minus K-t)-free co-comparability graphs have mim-width at most t - 1, chordal graphs and co-comparability graphs have unbounded mim-width in general. We obtain several algorithmic consequences;for instance, while MINIMUM DOMINATING SET is NP-complete on chordal graphs, it can be solved in time n(O)(t) on (K-t boxed minus S-t)-free chordal graphs. The third statement strengthens a result of Belmonte and Vatshelle stating that either those classes do not have constant mim-width or a decomposition with constant mim-width cannot be computed in polynomial time unless P = NP. We generalize these ideas to bigger graph classes. We introduce a new width parameter sim-width, of stronger modeling power than mim-width, by making a small change in the definition of mim-width. We prove that chordal graphs and co-comparability graphs have sim-width at most 1. We investigate a way to bound mim-width for graphs of bounded sim-width by excluding K-t boxed minus K-t and K-t boxed minus S-t as induced minors or induced subgraphs, and give algorithmic consequences. Lastly, we show that circle graphs have unbounded sim-width, and thus also unbounded mim-width. (C) 2017 Elsevier B.V. All rights reserved.
暂无评论