We study the problem of determining the spanning tree congestion of a graph. We present some sharp contrasts in the parameterized complexity of this problem. First, we show that on apex-minor-free graphs, a general cl...
详细信息
We study the problem of determining the spanning tree congestion of a graph. We present some sharp contrasts in the parameterized complexity of this problem. First, we show that on apex-minor-free graphs, a general class of graphs containing planar graphs, graphs of bounded treewidth, and graphs of bounded genus, the problem to determine whether a given graph has spanning tree congestion at most k can be solved in linear time for every fixed k. We also show that for every fixed k and d the problem is solvable in linear time for graphs of degree at most d. In contrast, if we allow only one vertex of unbounded degree, the problem immediately becomes NP-complete for any fixed ka parts per thousand yen8. Moreover, the hardness result holds for graphs excluding the complete graph on 6 vertices as a minor. We also observe that for ka parts per thousand currency sign3 the problem becomes polynomially time solvable.
A tournament is a directed graph T such that every pair of vertices is connected by an arc. A feedback vertex set is a set S of vertices in T such that T - S is acyclic. In this article we consider the FEEDBACK VERTEX...
详细信息
ISBN:
(纸本)9783959770019
A tournament is a directed graph T such that every pair of vertices is connected by an arc. A feedback vertex set is a set S of vertices in T such that T - S is acyclic. In this article we consider the FEEDBACK VERTEX SET problem in tournaments. Here the input is a tournament T and an integer k, and the task is to determine whether T has a feedback vertex set of size at most k. We give a new algorithm for FEEDBACK VERTEX SET IN TOURNAMENTS. The running time of our algorithm is upper-bounded by O(1.6181(k) + n(O(1))) and by O(1.466(n)). Thus our algorithm simultaneously improves over the fastest known parameterized algorithm for the problem by Dom et al. running in time O(2(k)k(O(1)) + n(O(1))), and the fastest known exact exponential-time algorithm by Gaspers and Mnich with running time O(1.674(n)). On the way to proving our main result we prove a strengthening of a special case of a graph partitioning theorem due to Bollobas and Scott. In particular we show that the vertices of any undirected m-edge graph of maximum degree d can be colored white or black in such a way that for each of the two colors, the number of edges with both endpoints of that color is between m/4 - d/2 and m/4+d/2.
A circle graph is the intersection graph of a set of chords in a circle. Keil [Discrete Applied Mathematics, 42(1):51-63, 1993] proved that Dominating Set, Connected Dominating Set, and Total Dominating Set are NP-com...
详细信息
ISBN:
(纸本)9783642346118;9783642346101
A circle graph is the intersection graph of a set of chords in a circle. Keil [Discrete Applied Mathematics, 42(1):51-63, 1993] proved that Dominating Set, Connected Dominating Set, and Total Dominating Set are NP-complete in circle graphs. To the best of our knowledge, nothing was known about the parameterized complexity of these problems in circle graphs. In this paper we prove the following results, which contribute in this direction: Dominating Set, Independent Dominating Set, Connected Dominating Set, Total Dominating Set, and Acyclic Dominating Set are W[1]-hard in circle graphs, parameterized by the size of the solution. Whereas both Connected Dominating Set and Acyclic Dominating Set are W[1]-hard in circle graphs, it turns out that Connected Acyclic Dominating Set is polynomial-time solvable in circle graphs. If T is a given tree, deciding whether a circle graph has a dominating set isomorphic to T is NP-complete when T is in the input, and FPT when parameterized by vertical bar V(T)vertical bar. We prove that the FPT algorithm is subexponential.
We show that checking if a given hypergraph has an automorphism that moves exactly k vertices is fixed parameter tractable, using k and additionally either the maximum hyperedge size or the maximum color class size as...
详细信息
ISBN:
(纸本)9783959770286
We show that checking if a given hypergraph has an automorphism that moves exactly k vertices is fixed parameter tractable, using k and additionally either the maximum hyperedge size or the maximum color class size as parameters. In particular, it suffices to use k as parameter if the hyperedge size is at most polylogarithmic in the size of the given hypergraph. As a building block for our algorithms, we generalize Schweitzer's FPT algorithm [ESA 2011] that, given two graphs on the same vertex set and a parameter k, decides whether there is an isomorphism between the two graphs that moves at most k vertices. We extend this result to hypergraphs, using the maximum hyperedge size as a second parameter. Another key component of our algorithm is an orbit-shrinking technique that preserves permutations that move few points and that may be of independent interest. Applying it to a suitable subgroup of the automorphism group allows us to switch from bounded hyperedge size to bounded color classes in the exactly-k case.
A matching is a subset of edges in a graph G that do not share an endpoint. A matching M is a P-matching if the subgraph of G induced by the endpoints of the edges of M satisfies property P. For example, if the proper...
详细信息
ISBN:
(纸本)9783031433795;9783031433801
A matching is a subset of edges in a graph G that do not share an endpoint. A matching M is a P-matching if the subgraph of G induced by the endpoints of the edges of M satisfies property P. For example, if the property P is that of being a matching, being acyclic, or being disconnected, then we obtain an induced matching, an acyclic matching, and a disconnected matching, respectively. In this paper, we analyze the problems of the computation of these matchings from the viewpoint of parameterized Complexity with respect to the parameter treewidth.
We study the parameterized complexity of two families of problems: the bounded length disjoint paths problem anti the bounded length cut problem. From Menger's theorem both problems are equivalent (and computation...
详细信息
ISBN:
(纸本)9783642112683
We study the parameterized complexity of two families of problems: the bounded length disjoint paths problem anti the bounded length cut problem. From Menger's theorem both problems are equivalent (and computationally easy) in the unbounded case for single source, single target;paths. However, in the bounded case, they are combinatorially distinct and are both NP-hard, even to approximate. Our results indicate that a more refined landscape appears when we study these problems with respect to their parameterized complexity. For this, we consider several parameterizations (with respect to the maximum length of paths, the number k of paths or the size of a cut, and the treewidth of the input graph) of all variants of both problems (edge/vertex-disjoint paths or cuts, directed/undirected). We provide FPT-algorithms (for all variants) when parameterized by both A: and I and hardness results when the parameter is only one of A: and I. Our results indicate that the bounded length disjoint-path variants are structurally harder than their bounded length cut counterparts. Also, it appears that the edge variants are harder than their vertex-disjoint counterparts when parameterized by the treewidth of the input graph.
We study the STEINER TREE problem, in which a set of terminal vertices needs to be connected in the cheapest possible way in an edge-weighted graph. This problem has been extensively studied from the viewpoint of appr...
详细信息
ISBN:
(纸本)9783959770620
We study the STEINER TREE problem, in which a set of terminal vertices needs to be connected in the cheapest possible way in an edge-weighted graph. This problem has been extensively studied from the viewpoint of approximation and also parametrization. In particular, on one hand STEINER TREE is known to be APX-hard, and W[2]-hard on the other, if parameterized by the number of non-terminals (Steiner vertices) in the optimum solution. In contrast to this we give an efficient parameterized approximation scheme (EPAS), which circumvents both hardness results. Moreover, our methods imply the existence of a polynomial size approximate kernelization scheme (PSAKS) for the considered parameter. We further study the parameterized approximability of other variants of STEINER TREE, such as DIRECTED STEINER TREE and STEINER FOREST. For neither of these an EPAS is likely to exist for the studied parameter: for STEINER FOREST an easy observation shows that the problem is APX-hard, even if the input graph contains no Steiner vertices. For DIRECTED STEINER TREE we prove that computing a constant approximation for this parameter is W[1]-hard. Nevertheless, we show that an EPAS exists for UNWEIGHTED DIRECTED STEINER TREE. Also we prove that there is an EPAS and a PSAKS for STEINER FOREST if in addition to the number of Steiner vertices, the number of connected components of an optimal solution is considered to be a parameter.
The width measure treedepth, also known as vertex ranking, centered coloring and elimination tree height, is a well-established notion which has recently seen a resurgence of interest. We present an algorithm which-gi...
详细信息
ISBN:
(纸本)9783662439487
The width measure treedepth, also known as vertex ranking, centered coloring and elimination tree height, is a well-established notion which has recently seen a resurgence of interest. We present an algorithm which-given as input an n-vertex graph, a tree decomposition of width w, and an integer t-decides whether the input graph has treedepth at most t in time 2(O(wt)) . n. We use this to construct further algorithms which do not require a tree decomposition as part of their input: A simple algorithm which decides treedepth in linear time for a fixed t, thus answering an open question posed by Ossona de Mendez and Nesetril as to whether such an algorithm exists, a fast algorithm with running time 2(O(t2)) . n and an algorithm for chordal graphs with running time 2(O(t log t)) . n.
The d-bounded-degree vertex deletion problem, to delete at most k vertices in a given graph to make the maximum degree of the remaining graph at most d, finds applications in computational biology, social network anal...
详细信息
ISBN:
(纸本)9783319426341;9783319426334
The d-bounded-degree vertex deletion problem, to delete at most k vertices in a given graph to make the maximum degree of the remaining graph at most d, finds applications in computational biology, social network analysis and some others. It can be regarded as a special case of the (d + 2)-hitting set problem and generates the famous vertex cover problem. The d-bounded-degree vertex deletion problem is NP-hard for each fixed d >= 0. In terms of parameterized complexity, the problem parameterized by k is W[2]-hard for unbounded d and fixed-parameter tractable for each fixed d >= 0. Previously, (randomized) parameterized algorithms for this problem with running time bound O*((d + 1)(k)) are only known for d <= 2. In this paper, we give a uniform parameterized algorithm deterministically solving this problem in O*((d + 1)(k)) time for each d >= 3. Note that it is an open problem whether the d ' -hitting set problem can be solved in O*((d ' - 1)(k)) time for d ' >= 3. Our result answers this challenging open problem affirmatively for a special case. Furthermore, our algorithm also gets a running time bound of O*(3.0645(k)) for the case that d = 2, improving the previous deterministic bound of O*(3.24(k)).
Golovach, Paulusma and Song (Inf. Comput. 2014) asked to determine the parameterized complexity of the following problems parameterized by k: (1) Given a graph G, a clique modulator D (a clique modulator is a set of v...
详细信息
ISBN:
(纸本)9783959771405
Golovach, Paulusma and Song (Inf. Comput. 2014) asked to determine the parameterized complexity of the following problems parameterized by k: (1) Given a graph G, a clique modulator D (a clique modulator is a set of vertices, whose removal results in a clique) of size k for G, and a list L(v) of colors for every v epsilon V (G), decide whether G has a proper list coloring;(2) Given a graph G, a clique modulator D of size k for G, and a pre-coloring lambda(P) : X -> Q for X subset of V (G), decide whether lambda(P) can be extended to a proper coloring of G using only colors from Q. For Problem 1 we design an O* (2(k))-time randomized algorithm and for Problem 2 we obtain a kernel with at most 3k vertices. Banik et al. (IWOCA 2019) proved the following problem is fixed-parameter tractable and asked whether it admits a polynomial kernel: Given a graph G, an integer k, and a list L(v) of exactly n - k colors for every v epsilon V (G), decide whether there is a proper list coloring for G. We obtain a kernel with O(k(2)) vertices and colors and a compression to a variation of the problem with O(k) vertices and O(k(2)) colors.
暂无评论