The NP-hard problem Material Consumption Scheduling and related problems have been thoroughly studied since the 1980's. Roughly speaking, the problem deals with scheduling jobs that consume non-renewable resources...
详细信息
The NP-hard problem Material Consumption Scheduling and related problems have been thoroughly studied since the 1980's. Roughly speaking, the problem deals with scheduling jobs that consume non-renewable resources-each job has individual resource demands. The goal is to minimize the makespan. We focus on the single-machine case without preemption: from time to time, the resources of the machine are (partially) replenished, thus allowing for meeting a necessary precondition for processing further jobs. We initiate a systematic exploration of the parameterized computational complexity landscape of Material Consumption Scheduling, providing parameterized tractability as well as intractability results. Doing so, we mainly investigate how parameters related to the resource supplies influence the problem's computationalcomplexity. This leads to a deepened understanding of this fundamental scheduling problem.
Multilayer graphs consist of several graphs, called layers, where the vertex set of all layers is the same but each layer has an individual edge set. They are motivated by real-world problems where entities (vertices)...
详细信息
Multilayer graphs consist of several graphs, called layers, where the vertex set of all layers is the same but each layer has an individual edge set. They are motivated by real-world problems where entities (vertices) are associated via multiple types of relationships (edges in different layers). We chart the border of computational (in)tractability for the class of subgraph detection problems on multilayer graphs, including fundamental problems such as maximum-cardinality matching, finding certain clique relaxations, or path problems. Mostly encountering hardness results, sometimes even for two or three layers, we can also spot some islands of computational tractability.
Shortlisting of candidates-selecting a group of "best" candidates-is a special case of multiwinner elections. We provide the first in-depth study of the computationalcomplexity of strategic voting for short...
详细信息
Shortlisting of candidates-selecting a group of "best" candidates-is a special case of multiwinner elections. We provide the first in-depth study of the computationalcomplexity of strategic voting for shortlisting based on the perhaps most basic voting rule in this scenario, l-Bloc (every voter approves l candidates). In particular, we investigate the influence of several different group evaluation functions (e.g., egalitarian versus utilitarian) and tie-breaking mechanisms modeling pessimistic and optimistic manipulators. Among other things, we conclude that in an egalitarian setting strategic voting may indeed be computationally intractable regardless of the tie-breaking rule. Altogether, we provide a fairly comprehensive picture of the computationalcomplexity landscape of this scenario.
We study the NP-hard Target Set Selection (TSS) problem occurring in social network analysis. Roughly speaking, given a graph where each vertex is associated with a threshold, in TSS the task is to select a minimum-si...
详细信息
We study the NP-hard Target Set Selection (TSS) problem occurring in social network analysis. Roughly speaking, given a graph where each vertex is associated with a threshold, in TSS the task is to select a minimum-size "target set'' such that all vertices of the graph get activated. Activation is a dynamic process. First, only the vertices in the target set are active. Then, a vertex becomes active if the number of its active neighbors exceeds its threshold, and so on. TSS models the spread of information, infections, and influence in networks. Complementing results on its polynomial-time approximability and extending results for its restriction to trees and bounded treewidth graphs, we classify the influence of the parameters "diameter'', "cluster editing number'', "vertex cover number'', and "eedback edge set number'' of the underlying graph on the problem's computationalcomplexity, revealing both tractable and intractable cases. For instance, even for diameter-two split graphs TSS remains W[2]-hard with respect to the parameter "size of the target set''. TSS can be efficiently solved on graphs with small feedback edge set number and also turns out to be fixed-parameter tractable when parameterized by the vertex cover number. Both results contrast known parameterized intractability results for the parameter "treewidth''. While these tractability results are relevant for sparse networks, we also show efficient fixed-parameter algorithms for the parameter "cluster editing number'', yielding tractability for certain dense networks.
The Nemhauser-Trotter local optimization theorem applies to the NP-hard VERTEX COVER problem and has applications in approximation as well as parameterized algorithmics. We generalize Nemhauser and Trotter's resul...
详细信息
The Nemhauser-Trotter local optimization theorem applies to the NP-hard VERTEX COVER problem and has applications in approximation as well as parameterized algorithmics. We generalize Nemhauser and Trotter's result to vertex deletion problems, introducing a novel algorithmic strategy based on purely combinatorial arguments (not referring to linear programming as the Nemhauser-Trotter result originally did). The essence of our strategy can be understood as a doubly iterative process of cutting away "easy parts" of the input instance, finally leaving a "hard core" whose size is (almost) linearly related to the cardinality of the solution set. We exhibit our approach using a generalization of VERTEX COVER, called BOUNDED-DEGREE VERTEX DELETION. For some fixed d >= 0, BOUNDED-DEGREE VERTEX DELETION asks to delete at most k vertices from a graph in order to transform it into a graph with maximum vertex degree at most d. VERTEX COVER is the special case of d = 0. Our generalization of the Nemhauser-Trotter-Theorem implies that BOUNDED-DEGREE VERTEX DELETION, parameterized by k, admits an O (k)-vertex problem kernel for d <= 1 and, for any epsilon > 0, an O(k(1+epsilon))-vertex problem kernel for d >= 2. Finally, we provide a W[2]-completeness result for BOUNDED-DEGREE VERTEX DELETION in case of unbounded d-values. (C) 2010 Elsevier Inc. All rights reserved.
We show that the parameterized problem PERFECT CODE belongs to W[1]. This result closes an old open question, because it was often conjectured that PERFECT CODE could be a natural problem having complexity degree inte...
详细信息
We show that the parameterized problem PERFECT CODE belongs to W[1]. This result closes an old open question, because it was often conjectured that PERFECT CODE could be a natural problem having complexity degree intermediate between W[1] and W[2]. This result also shows W[1]-membership of the parameterized problem WEIGHTED EXACT CNF SATISFIABILITY. (C) 2002 Elsevier Science B.V. All rights reserved.
A parameterizedcomputational problem is a set of pairs [x, k], where k is a distinguished item called ''parameter''. FPT is the class of fixed-parameter tractable problems: for any fixed value of k, t...
详细信息
A parameterizedcomputational problem is a set of pairs [x, k], where k is a distinguished item called ''parameter''. FPT is the class of fixed-parameter tractable problems: for any fixed value of k, they are solvable in time bounded by a polynomial of degree alpha, where alpha is a constant not dependent on the parameter. In order to deal with parameterized intractability, Downey and Fellows have introduced a hierarchy of classes W[1] subset of or equal to W[2] subset of or equal to ... containing likely intractable parameterized problems, and they have shown that such classes have many natural, complete languages. In this paper we analyze several variations of the halting problem for nondeterministic Turing machines with parameterized time, and we show that its parameterizedcomplexity strongly depends on some resources Like the number of tapes, head and internal states, and on the size of the alphabet. Notice that classical polynomial-time complexity fails in distinguishing such features. As byproducts, we show that parameterizedcomplexity is a useful tool for the study of the intrinsic power of some computational models, and we underline the different ''computational powers'' of some levels of the parameterized hierarchy.
暂无评论