Search

This paper is concerned with designing algorithms for and analyzing the computational complexity of the partial vertex cover problem in trees. Graphs (and trees) are frequently used to model risk management in various systems. In particular, Caskurlu et al. in [4] have considered a system which essentially represents a tripartite graph. The goal in this model is to reduce the risk in the system below a predefined risk threshold level. It can be shown that the main goal in this risk management system can be formulated as a Partial Vertex Cover problem on bipartite graphs. In this paper, we focus on a special case of the partial vertex cover problem, when the input graph is a tree. We consider four possible versions of this setting, depending on whether or not, the vertices and edges are weighted. Two of these versions, where edges are assumed to be unweighted, are known to be polynomial-time solvable. However, the computational complexity of this problem with weighted edges, and possibly with weighted vertices, remained open. The main contribution of this paper is to resolve these questions by fully characterizing which variants of partial vertex cover remain NP-hard in trees, and which can be solved in polynomial time. In the paper, we propose two pseudo-polynomial DP-based algorithms for the most general case in which weights are present on both the edges and the vertices of the tree. One of these algorithms leads to a polynomial-time procedure, when weights are confined to the edges of the tree. The insights used in this algorithm are combined with additional scaling ideas to derive an FPTAS for the general case. A secondary contribution of this work is to propose a novel way of using centroid decompositions in trees, which could be useful in other settings as well. [ABSTRACT FROM AUTHOR]

A dominator coloring of a graph G is a proper vertex coloring with a domination property that each vertex dominates a color class. The minimum number of colors used in a dominator coloring of G is called dominator chromatic number of G and is denoted as χ d (G). Graphs with χ d (G) ≤ 3 have characterizations and such graphs can be recognized in polynomial time. However, for k ≥ 4 , deciding whether χ d (G) ≤ k is NP-hard. In this paper, we investigate the computational complexity of minimum q -dominator partization problem (Min- q -D-Partz). In Min- q -D-Partz, given a graph G , the objective is to find a vertex set S of minimum size such that χ d (G [ V ∖ S ]) ≤ q. We prove that Min- 2 -D-Partz is APX-complete and has a two-factor approximation algorithm. We also prove that Min- 3 -D-Partz cannot be approximated within any constant factor and can be approximated within a factor of O (log n). [ABSTRACT FROM AUTHOR]

For a simple, undirected, connected graph G , a function h : V (G) → { 0 , 1 , 2 } which satisfies the following conditions is called a weakly connected Roman dominating function (WCRDF) of G with weight h (V) = ∑ p ∈ V h (p). (C1). For all q ∈ V with h (q) = 0 there exists a vertex r such that (q , r) ∈ E and h (r) = 2 and (C2). The graph with vertex set V (G) and edge set { (p , z) : h (p) ≥ 1 or h (z) ≥ 1 or both } is connected. The problem of determining WCRDF of minimum weight is called minimum weakly connected Roman domination problem (MWCRDP). In this paper, we show that MWCRDP is polynomial time solvable for bounded treewidth graphs, threshold graphs and chain graphs. We design a 2 (1 +) (1 + ln (Δ − 1)) -approximation algorithm for the MWCRDP and show that the same cannot have (1 − δ) ln | V | ratio approximation algorithm for any δ > 0 unless P = N P. Next, we show that MWCRDP is APX-hard for graphs with Δ = 4. We also show that the domination and weakly connected Roman domination problems are not equivalent in computational complexity aspects. Finally, two different integer linear programming formulations for MWCRDP are proposed. [ABSTRACT FROM AUTHOR]

We consider the total weighted early work maximization problem on identical machines in parallel such that the weights are identical, or the due date is the same. First, we present an approach to solve the case with a fixed number of machines in pseudo-polynomial time. Then, we develop approximation algorithms for the two cases with identical weights and with a common due date. For the case with identical weights, furthermore, we show that the parallel-machine and a single-machine cases are strongly NP-hard and weakly NP-hard, respectively, even if the due date of each job is equal to the processing time multiplied by a constant. [ABSTRACT FROM AUTHOR]

For a simple, undirected, connected graph G , a function h : V (G) → { 0 , 1 , 2 , 3 } which satisfies the following conditions is called a total Roman {3}-dominating function (TR3DF) of G with weight h (V) = ∑ p ∈ V h (p) : (C1) For every vertex u ∈ V if h (u) = 0 , then u has m (m ≥ 1) neighbors such that whose sum is at least 3, and if h (u) = 1 , then u has n (n ≥ 1) neighbors such that whose sum is at least 2. (C2) The subgraph induced by the set of vertices labeled one, two or three has no isolated vertices. For a graph G , the smallest possible weight of a TR3DF of G denoted γ t { R 3 } (G) is known as the total Roman { 3 } -domination number of G. The problem of determining γ t { R 3 } (G) of a graph G is called minimum total Roman {3}-domination problem (MTR3DP). In this paper, we show that the problem of deciding if G has a TR3DF of weight at most l for chordal graphs is NP-complete. We also show that MTR3DP is polynomial time solvable for bounded treewidth graphs, chain graphs and threshold graphs. We design a 3 (ln (Δ − 0. 5) + 1. 5) -approximation algorithm for the MTR3DP and show that the same cannot have (1 − δ) ln | V | ratio approximation algorithm for any δ > 0 unless NP ⊆ DTIME (| V | O (log log | V |)). Next, we show that MTR3DP is APX-complete for graphs with Δ = 4. We also show that the domination and total Roman {3}-domination problems are not equivalent in computational complexity aspects. Finally, we present an integer linear programming formulation for MTR3DP. [ABSTRACT FROM AUTHOR]

We investigate the complexity of counting the number of integer points in tropical polytopes, and the complexity of calculating their volume. We study the tropical analogue of the outer parallel body and establish bounds for its volume. We deduce that there is no approximation algorithm of factor α = 2 poly (m , n) for the volume of a tropical polytope given by n for the volume of a tropical polytope given by n vertices in a space of dimension m , unless P = NP. Neither is there such an approximation algorithm for counting the number of integer points in tropical polytopes described by vertices. It follows that approximating these values for tropical polytopes is more difficult than for classical polytopes. Our proofs use a reduction from the problem of calculating the tropical rank. [ABSTRACT FROM AUTHOR]

In the past decades, there has been a burst of activity to simplify implementation of complex software systems. The solution framework in software engineering community for this problem is called component-based software design (CBSD), whereas in the modeling and simulation community it is called composability. Composability is a complex feature due to the challenges of creating components, selecting combinations of components, and integrating the selected components. In this paper, we address the challenge through the analysis of Component Selection (CS), the NP-complete process of selecting a minimal set of components to satisfy a set of objectives. Due to the computational complexity of CS, we consider approximation algorithms that make the component selection process practical. We define three variations of CS and present good approximation algorithms to find near optimal solutions. In spite of our creation of approximable variants of Component Selection, we prove that the general Component Selection problem is inapproximable. [ABSTRACT FROM AUTHOR]

We consider the problem of allocating a set of resources for performing a given collection of jobs. Each of the jobs has specific resource requirement for its execution. Each resource has specific start time, finish time and associated cost per unit usage. The objective is to execute the jobs while incurring minimum cost. The problem is NP-hard. We improve known four-approximation to a three-approximation algorithm. Our algorithm implies better approximation for two other related problems. [ABSTRACT FROM AUTHOR]

The Resource Allocation Problem with Time Dependent Penalties (RAPTP) is a variant of uncapacitated resource allocation problems generally referred as uncapacitated facility allocation problems or uncapacitated facility location problem (UFLP). Work done in this paper is motivated by the work of Du, Lu and Xu [7] in which authors considered facility location problems with submodular penalties and presented a 3-approximation primal dual algorithm. This paper considers that each unallocated demand point adds to penalty that increases as time passes and is thus represented by function x (t i , p i) where t i and p i are elapse time and priority of demand point d i . As this problem has been considered for emergency service allocation, all demand points should be allocated to some facility or resource within some stipulated time limit beyond which it may lose its purpose. Thus penalty incurred by a demand point is considered till that threshold value only. Thus it is assumed that penalty contribution by a demand point remains constant after a specified threshold value. By exploiting the properties of time dependent penalties, a 4-approximation primal-dual algorithm is proposed which is based on LP framework, and is the first constant-factor approximation algorithm for RAPTP. [ABSTRACT FROM AUTHOR]

Let P be a d-dimensional n-point set. A partition of P is called a Tverberg partition if the convex hulls of all sets in intersect in at least one point. We say that is t- tolerant if it remains a Tverberg partition after deleting any t points from P. Soberón and Strausz proved that there is always a t-tolerant Tverberg partition with ⌈n/(d + 1)(t + 1)⌉ sets. However, no nontrivial algorithms for computing or approximating such partitions have been presented so far. For d ≤ 2, we show that the Soberón-Strausz bound can be improved, and we show how the corresponding partitions can be found in polynomial time. For d ≥ 3, we give the first polynomial-time approximation algorithm by presenting a reduction to the regular Tverberg problem (with no tolerance). Finally, we show that it is coNP-complete to determine whether a given Tverberg partition is t-tolerant. [ABSTRACT FROM AUTHOR]

The firefighter problem models the situation where an infection, a computer virus, an idea or fire etc. is spreading through a network and the goal is to save as many as possible nodes of the network through targeted vaccinations. The number of nodes that can be vaccinated at a single time-step is typically one, or more generally O(l). In a non-standard model, the so called spreading model, the vaccinations also spread in contrast to the standard model. Our main results are concerned with general graphs in the spreading model. We provide a very simple exact 20(√n log n) -time algorithm. In the special case of trees, where the standard and spreading model are equivalent, our algorithm is substan-tially simpler than that exact subexponential algorithm for trees presented in Ref. 2. On the other hand, we show that the firefighter problem on weighted directed graphs in the spreading model cannot be approximated within a constant factor better than 1 -- 1/e unless NP C DTIME (nO(log log n)) We also present several results in the standard model. We provide approximation algorithms for planar graphs in case when at least two vaccinations can be performed at a time-step. We also derive trade-offs between approximation factors for polynomial-time solutions and the time complexity of exact or nearly exact solutions for instances of the firefighter problem for the so called directed layered graphs. [ABSTRACT FROM AUTHOR]