We study the NP-complete MINIMUM SHARED EDGES (MSE) problem, defined as follows. Given an undirected graph, a source and a sink vertex, and two integers p and kappa, we ask whether there are p paths in the graph conne...
详细信息
We study the NP-complete MINIMUM SHARED EDGES (MSE) problem, defined as follows. Given an undirected graph, a source and a sink vertex, and two integers p and kappa, we ask whether there are p paths in the graph connecting the source with the sink and sharing at most k edges. Herein, an edge is shared if it appears in at least two paths. On the positive side, we show that MSE is fixed-parameter tractable with respect to p. On the negative side, we show that MSE is W[1]-hard when parameterized by the treewidth of the input graph and the number k of shared edges combined, and that MSE does not admit a polynomial-size kernel with respect to p (unless NP subset of coNP / poly). (C) 2019 Elsevier Inc. All rights reserved.
The sports elimination problem asks whether a team participating in a competition still has a chance to win, given the current standings and the remaining matches to be played among the teams. This problem can be view...
详细信息
The sports elimination problem asks whether a team participating in a competition still has a chance to win, given the current standings and the remaining matches to be played among the teams. This problem can be viewed as a graph labelling problem, where arcs receive labels that contribute to the score of both endpoints of the arc, and the aim is to label the arcs in a way that each vertex obtains a score not exceeding its capacity. We investigate the complexity of this problem in detail, using a multivariate approach to examine how various parameters of the input graph (such-as the maximum degree, the feedback vertex/edge number, and different width parameters) influence the computational tractability. We obtain several efficient algorithms, as well as certain hardness results. (C) 2015 Elsevier B.V. All rights reserved.
In the SHIFT BRIBERY problem, we are given an election, a preferred candidate p, and a budget. The goal is to ensure p's victory by shifting p higher in some voters' preference orders. However, each such shift...
详细信息
In the SHIFT BRIBERY problem, we are given an election, a preferred candidate p, and a budget. The goal is to ensure p's victory by shifting p higher in some voters' preference orders. However, each such shift request comes at a price and we must not exceed the given budget. We study the parameterized computational complexity of SHIFT BRIBERY for a number of parameters and several classes of price functions: For the number of affected voters, SHIFT BRIBERY is W[2]-hard for Borda, Maximin, and Copeland. For the number of positions by which p is shifted in total, the problem is fixed-parameter tractable for Borda and Maximin, and is W[1] -hard for Copeland. For the budget, the results depend on the price function class. Finally, SHIFT BRIBERY tends to be tractable when parameterized by the number of voters, but the results for the number of candidates are more enigmatic. (C) 2016 Elsevier Inc. All rights reserved.
The NP-hard RAINBOW SUBGRAPH problem, motivated from bioinformatics, is to find in an edge-colored graph a subgraph that contains each edge color exactly once and has at most k vertices. We examine the parameterized c...
详细信息
The NP-hard RAINBOW SUBGRAPH problem, motivated from bioinformatics, is to find in an edge-colored graph a subgraph that contains each edge color exactly once and has at most k vertices. We examine the parameterized complexity of RAINBOW SUBGRAPH for paths, trees, and general graphs. We show that RAINBOW SUBGRAPH is W[1-algorithms-08-00060"> 1]-hard with respect to the parameter k and also with respect to the dual parameter l := n - k where n is the number of vertices. Hence, we examine parameter combinations and show, for example, a polynomial-size problem kernel for the combined parameter l and "maximum number of colors incident with any vertex". Additionally, we show APX-hardness even if the input graph is a properly edge-colored path in which every color occurs at most twice.
The NP-hard 2-CLUB problem is, given an undirected graph G = (V, E) and l is an element of N, to decide whether there is a vertex set S subset of V of size at least l such that the induced subgraph G[S] has diameter a...
详细信息
The NP-hard 2-CLUB problem is, given an undirected graph G = (V, E) and l is an element of N, to decide whether there is a vertex set S subset of V of size at least l such that the induced subgraph G[S] has diameter at most two. We make progress towards a systematic classification of the complexity of 2-CLUB with respect to a hierarchy of prominent structural graph parameters. First, we present the following tight NP-hardness results: 2-CLUB is NP-hard on graphs that become bipartite by deleting one vertex, on graphs that can be covered by three cliques, and on graphs with domination number two and diameter three. Then, we consider the parameter h-index of the input graph. The study of this parameter is motivated by real-world instances and the fact that 2-CLUB is fixed-parameter tractable when parameterized by the larger parameter maximum degree. We present an algorithm that solves 2-CLUB in vertical bar V vertical bar(f(k)) time with k being the h-index of G. By showing W[1]-hardness for this parameter, we provide evidence that the above algorithm cannot be improved to a fixed-parameter algorithm. Furthermore, the reduction used for this hardness result can be modified to show that 2-CLUB is NP-hard if the input graph has constant degeneracy. Finally, we show that 2-CLUB is fixed-parameter tractable when parameterized by distance to cographs. (c) 2014 Elsevier B.V. All rights reserved.
暂无评论