4 results
Now showing1 - 4 of 4
- Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Domination and cut problems on chordal graphs with bounded leafage(Springer, 2024-05); ; ; ; The leafage of a chordal graph G is the minimum integer ℓ such that G can be realized as an intersection graph of subtrees of a tree with ℓ leaves. We consider structural parameterization by the leafage of classical domination and cut problems on chordal graphs. Fomin, Golovach, and Raymond [ESA 2018, Algorithmica 2020] proved, among other things, that Dominating Set on chordal graphs admits an algorithm running in time 2O(ℓ2)·nO(1) . We present a conceptually much simpler algorithm that runs in time 2 O(ℓ)· nO(1) . We extend our approach to obtain similar results for Connected Dominating Set and Steiner Tree. We then consider the two classical cut problems MultiCut with Undeletable Terminals and Multiway Cut with Undeletable Terminals. We prove that the former is W[1]-hard when parameterized by the leafage and complement this result by presenting a simple nO(ℓ) -time algorithm. To our surprise, we find that Multiway Cut with Undeletable Terminals on chordal graphs can be solved, in contrast, in nO(1) -time.Publicationtype: Journal Article37 29 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Parameterized complexity of multicut in weighted trees(Elsevier, 2023-09-19); ; ; ; In the MULTICUT problem, given an undirected graph G, a set of pairs of vertices P, and a budget k, the goal is to determine if there is a set S of at most k edges such that for each (s,t)∈P, the graph G−S has no path from s to t. In this article we first study the parameterized complexity of a variant of this problem, where the input graph is edge-weighted with arbitrary weights and the goal is to find a solution of minimum weight. Since weights are arbitrarily large, the weight of the solution is not a good choice for a parameter. The weighted problem is non-trivial even on trees and we study this problem on trees parameterized by structural parameters like the number of leaves and the request degree of every vertex. The studied parameters naturally interpolate the known polynomial time and NP-hardness results for this problem. We also give an FPT algorithm for another variant called WEIGHTED MULTICUT, where given an edge-weighted tree, the goal is to find a solution of size at most k edges that minimizes the weight.Publicationtype: Journal Article27 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Metric dimension parameterized by feedback vertex set and other structural parameters(Society for Industrial & Applied Mathematics (SIAM), 2023); ; For a graph G, a subset S \subseteq V (G) is called a resolving set if for any two vertices u, v \in V (G), there exists a vertex w \in S such that d(w, u) \not= d(w, v). The Metric Dimension problem takes as input a graph G and a positive integer k, and asks whether there exists a resolving set of size at most k. This problem was introduced in the 1970s and is known to be NP-hard [M. R. Garey and D. S. Johnson, Computers and Intractability-A Guide to NP-Completeness, Freeman, San Francisco, 1979]. In the realm of parameterized complexity, Hartung and Nichterlein [28th Conference on Computational Complexity, IEEE, Piscataway, NJ, 2013, pp. 266-276] proved that the problem is W[2]-hard when parameterized by the natural parameter k. They also observed that it is fixed parameter tractable (FPT) when parameterized by the vertex cover number and asked about its complexity under smaller parameters, in particular, the feedback vertex set number. We answer this question by proving that Metric Dimension is W[1]-hard when parameterized by the combined parameter feedback vertex set number plus pathwidth. This also improves the result of Bonnet and Purohit [IPEC 2019] which states that the problem is W[1]-hard parameterized by the pathwidth. On the positive side, we show that Metric Dimension is FPT when parameterized by either the distance to cluster or the distance to cocluster, both of which are smaller parameters than the vertex cover number.Publicationtype: Journal Article38 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Domination and cut problems on chordal graphs with bounded leafage(Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, 2022-09); ; ; ; The leafage of a chordal graph G is the minimum integer ℓ such that G can be realized as an intersection graph of subtrees of a tree with ℓ leaves. We consider structural parameterization by the leafage of classical domination and cut problems on chordal graphs. Fomin, Golovach, and Raymond [ESA 2018, Algorithmica 2020] proved, among other things, that Dominating Set on chordal graphs admits an algorithm running in time 2O(ℓ2) · nO(1). We present a conceptually much simpler algorithm that runs in time 2O(ℓ)·nO(1). We extend our approach to obtain similar results for Connected Dominating Set and Steiner Tree. We then consider the two classical cut problems MultiCut with Undeletable Terminals and Multiway Cut with Undeletable Terminals. We prove that the former is W[1]-hard when parameterized by the leafage and complement this result by presenting a simple nO(ℓ)-time algorithm. To our surprise, we find that Multiway Cut with Undeletable Terminals on chordal graphs can be solved, in contrast, in nO(1)-time.Publicationtype: Conference PaperScopus© Citations 2 63 96