Search

The length of a tree-decomposition of a graph is the maximum distance (in the graph) between two vertices of a same bag of the decomposition. The treelength of a graph is the minimum length among its tree-decompositions. Treelength of graphs has been studied for its algorithmic applications in classical metric problems such as Traveling Salesman Problem or metric dimension of graphs and also, in compact routing in the context of distributed computing. Deciding whether the treelength of a general graph is at most 2 is NP-complete (graphs of treelength one are precisely the chordal graphs), and it is known that the treelength of a graph cannot be approximated up to a factor less than 3 2 (the best known approximation algorithm for treelength has an approximation ratio of 3). However, nothing is known on the computational complexity of treelength in planar graphs, except that the treelength of any outerplanar graph is equal to the third of the size of a largest isometric cycle. This work initiates the study of treelength in planar graphs by considering the next natural subclass of planar graphs, namely the one of series–parallel graphs. We first fully describe the treelength of melon graphs (set of pairwise internally disjoint paths linking two vertices), showing that, even in such a restricted graph class, the expression of the treelength is not trivial. Then, we show that treelength can be approximated up to a factor 3 2 in series–parallel graphs. Our main result is a quadratic-time algorithm for deciding whether a series–parallel graph has treelength at most 2. Our latter result relies on a characterization of series–parallel graphs with treelength 2 in terms of an infinite family of forbidden isometric subgraphs. [ABSTRACT FROM AUTHOR]

In the Multi-Spreader Crane Scheduling Problem (MSCSP), containers with identical dimensions but variable weights are arranged along a grid. A multi-spreader crane is used to lift all the containers. The crane has m > 1 modes. When it is in the p th mode, the crane can remove p adjacent containers along the same row at the same time as long as the total weight of the containers does not exceed the loading capacity κ p. Such a lift takes h p minutes. It also takes c p , q minutes for the crane to switch from mode p to q when p ≠ q. The goal is to find a crane lift sequence so that the total time it takes to lift all the containers is minimized. This paper investigates the computational complexity of MSCSP. First, we establish a connection between greedy crane lift sequences and supersequences. We then prove that MSCSP is NP-hard when the crane has three or more modes by a reduction from a version of the Shortest Common Supersequence problem. Lastly, we investigate two problems that arise naturally when heuristics are used to solve MSCSP. We show that one can be solved using dynamic programming while the other remains computationally hard. We also provide an approximation algorithm that behaves nicely when the changeover times are not much larger than the lifting times of the crane. [ABSTRACT FROM AUTHOR]

In this paper the following selection problem is discussed. A set of n items is given and we wish to choose a subset of exactly p items of the minimum total cost. This problem is a special case of 0–1 knapsack in which all the item weights are equal to 1. Its deterministic version has an O ( n ) -time algorithm, which consists in choosing p items of the smallest costs. In this paper it is assumed that the item costs are uncertain. Two robust models, namely two-stage and recoverable ones, under discrete and interval uncertainty representations, are discussed. Several positive and negative complexity results for both of them are provided. [ABSTRACT FROM AUTHOR]

Graph burning is a model for the spread of social contagion. The burning number is a graph parameter associated with graph burning that measures the speed of the spread of contagion in a graph; the lower the burning number, the faster the contagion spreads. We prove that the corresponding graph decision problem is NP -complete when restricted to acyclic graphs with maximum degree three, spider graphs and path-forests. We provide polynomial time algorithms for finding the burning number of spider graphs and path-forests if the number of arms and components, respectively, are fixed. Finally, we describe a polynomial time approximation algorithm with approximation factor 3 for general graphs. [ABSTRACT FROM AUTHOR]

A total dominating set of an undirected graph G = ( V , E ) is a set S ⊆ V of vertices such that each vertex of G is adjacent to at least one vertex of S . A secure total dominating set of G is a set D ⊆ V of vertices such that D is a total dominating set of G and each vertex v ∈ V ∖ D is adjacent to at least one vertex u ∈ D with the property that the set ( D ∖ { u } ) ∪ { v } is a total dominating set of G . The secure total domination number γ s t ( G ) of G is the minimum cardinality of a secure total dominating set of G . We establish bounds on the secure total domination number. In particular, we show that every graph G with no isolated vertices satisfies γ s t ( G ) ≤ 2 α ( G ) , where α ( G ) is the independence number of G . Further, we study the problem of finding the secure total domination number. We show that the decision version of the problem is N P -complete for chordal bipartite graphs, planar bipartite graphs with arbitrary large girth and maximum degree 3, split graphs and graphs of separability at most 2. Finally, we show that the optimisation version of the problem can be approximated in polynomial time within a factor of c ln | V | for some constant c > 1 and cannot be approximated in polynomial time within a factor of c ′ ln | V | for some constant c ′ < 1 , unless P = N P . [ABSTRACT FROM AUTHOR]

Abstract: This paper is the first attempt to successfully design efficient approximation algorithms for the single-machine maximum lateness minimization problem when jobs have different release dates and tails (or delivery times) under the no idle time assumption (i.e., the schedule cannot contain any idle time between two consecutive jobs on the machine). Our work is motivated by interesting industrial applications to the production area (Chrétienne (2008) [3]). Our analysis shows that modifications of the classical algorithms of Potts and Schrage can lead to the same worst-case performance ratios obtained for the relaxed problem without the no idle time constraint. Then, we extend the result developed by Mastrolilli (2003) [13] for such a relaxed problem and we propose a polynomial time approximation scheme with efficient time complexity. [Copyright &y& Elsevier]

Abstract: Matching problems on bipartite graphs where the entities on one side may have different sizes are intimately related to scheduling problems with processing set restrictions. We survey the close relationship between these two problems, and give new approximation algorithms for the (NP-hard) variations of the problems in which the sizes of the jobs are restricted. Specifically, we give an approximation algorithm with an additive error of one when the sizes of the jobs are either 1 or 2, and generalise this to an approximation algorithm with an additive error of for the case where each job has a size taken from the set (for any constant integer ). We show that the above two problems become polynomial-time solvable if the processing sets are nested. [Copyright &y& Elsevier]

Abstract: We consider the problem of releasing multiple types of jobs to a facility over a fixed period. In the problem, each type of job has its own demand for the period and the daily capacity of the facility can fluctuate. The variability of each type is defined as the total absolute deviation between the number of jobs of the corresponding type released on consecutive days. The objective is to minimize the total variability over all types. We show that the problem is strongly NP-hard. In addition, we develop an approximation algorithm and analyze its approximability according to the level of fluctuation of the daily capacity. [Copyright &y& Elsevier]

Abstract: We show that testing if an undirected graph contains a bridgeless spanning cactus is NP-hard. As a consequence, the minimum spanning cactus problem (MSCP) on an undirected graph with 0–1 edge weights is NP-hard. For any subgraph of , we give polynomially testable necessary and sufficient conditions for to be extendable to a cactus in and the weighted version of this problem is shown to be NP-hard. A spanning tree is shown to be extendable to a cactus in if and only if it has at least one node of even degree. When is a spanning tree, we show that the weighted version can also be solved in polynomial time. Further, we give an algorithm for computing a minimum cost spanning tree with at least one vertex of even degree on a graph on nodes. Finally, we show that for a complete graph with edge-costs satisfying the triangle inequality, the MSCP is equivalent to a general class of optimization problems that properly includes the traveling salesman problem and they all have the same approximation hardness. [Copyright &y& Elsevier]

Abstract: This paper is aimed at investigating some computational aspects of different isoperimetric problems on weighted trees. In this regard, we consider different connectivity parameters called minimum normalized cuts/isoperimetric numbers defined through taking the minimum of the maximum or the mean of the normalized outgoing flows from a set of subdomains of vertices, where these subdomains constitute a partition/subpartition. We show that the decision problem for the case of taking -partitions and the maximum (called the max normalized cut problem NCP), and the other two decision problems for the mean version (referred to as IPP and NCP) are -complete problems for weighted trees. On the other hand, we show that the decision problem for the case of taking -subpartitions and the maximum (called the max isoperimetric problem IPP) can be solved in linear time for any weighted tree and any . On the basis of this fact, we provide polynomial time -approximation algorithms for all different versions of the th isoperimetric numbers considered. Moreover, for when the number of partitions/subpartitions, , is a fixed constant, we prove, as an extension of a result of Mohar (1989) for the case (usually referred to as the Cheeger constant), that the max and mean isoperimetric numbers of weighted trees, and their max minimum normalized cut can be computed in polynomial time. We also prove some hardness results for the case of simple unweighted graphs and trees. [Copyright &y& Elsevier]

Abstract: Using ideas and results from polynomial time approximation and exact computation we design approximation algorithms for several NP-hard combinatorial problems achieving ratios that cannot be achieved in polynomial time (unless a very unlikely complexity conjecture is confirmed) with worst-case complexity much lower (though super-polynomial) than that of an exact computation. We study in particular two paradigmatic problems, max independent set and min vertex cover. [Copyright &y& Elsevier]

Abstract: We study a new two-stage version of an – path problem, which we call adaptable robust connection path (ARCP). Given an undirected graph , two vertices and two integers , ARCP asks to find a set of minimum cardinality which connects and , such that for any ‘failure set’ with , the set of edges can be completed to a set which connects and by adding at most edges from . We show the problem is NP-hard, and there is no polynomial-time -approximation algorithm for the problem for unless P=NP. For we provide an exact polynomial algorithm, and for and arbitrary we provide a polynomial 2-approximation algorithm. A characterization of the feasible set is provided for and several links are established between ARCP and other combinatorial optimization problems, including a new combinatorial optimization problem, the minimum reduced cost cycle problem whose complexity is open. [Copyright &y& Elsevier]

Abstract: A polyhedral embedding in a surface is one in which any two faces have boundaries that are either disjoint or simply connected. In a cubic (3-regular) graph this is equivalent to the dual being a simple graph. In 1968, Grünbaum conjectured that every cubic graph with a polyhedral embedding in an orientable surface is 3-edge-colorable. For the sphere, this is equivalent to the Four-Color Theorem, but we have disproved the conjecture in the general form. In this paper we extend this result and show that if we restrict our attention to a class of cubic graphs with a polyhedral embedding in an orientable surface, then the computational complexity of the 3-edge-coloring problem and its approximation does not improve. [ABSTRACT FROM AUTHOR]

Abstract: We introduce two interdiction problems involving matchings, one dealing with edge removals and the other dealing with vertex removals. Given is an undirected graph with positive weights on its edges. In the edge interdiction problem, every edge of has a positive cost and the task is to remove a subset of the edges constrained to a given budget, such that the weight of a maximum matching in the resulting graph is minimized. The vertex interdiction problem is analogous to the edge interdiction problem, with the difference that vertices instead of edges are removed. Hardness results are presented for both problems under various restrictions on the weights, interdiction costs and graph classes. Furthermore, we study the approximability of the edge and vertex interdiction problem on different graph classes. Several approximation-hardness results are presented as well as two constant-factor approximations, one of them based on iterative rounding. A pseudo-polynomial algorithm for solving the edge interdiction problem on graphs with bounded treewidth is proposed which can easily be adapted to the vertex interdiction problem. The algorithm presents a general framework to apply dynamic programming for solving a large class of problems in graphs with bounded treewidth. Additionally, we present a method to transform pseudo-polynomial algorithms for the edge interdiction problem into fully polynomial approximation schemes, using a scaling and rounding technique. [ABSTRACT FROM AUTHOR]

Abstract: We study the following problem. Given two sequences and over a finite alphabet, find a repetition-free longest common subsequence of and . We show several algorithmic results, a computational complexity result, and we describe a preliminary experimental study based on the proposed algorithms. We also show that this problem is APX-hard. [Copyright &y& Elsevier]

Abstract: Consider the problem of computing a -approximation to the minimum volume axis-aligned ellipsoid (MVAE) enclosing a set of points in . We first provide an extension and improvement to algorithm proposed in Kumar and Yıldırım (2008) (the KY algorithm) for the MVAE problem. The main challenge of the MVAE problem is that there is no closed form solution in the line search step (beta). Therefore, the KY algorithm proposed a certain choice of beta that leads to their complexity and core set results in solving the MVAE problem. We further analyze the line search step to derive a new beta, relying on an analysis of up to the fourth order derivative. This choice of beta leads to the improved complexity and core set results. The second modification is given by incorporating “away steps” into the first one at each iteration, which obtains the same complexity and core set results as the first one. In addition, since the second modification uses the idea of “dropping points”, it has the potential to compute smaller core sets in practice. Some numerical results are given to show the efficiency of the modified algorithms. [Copyright &y& Elsevier]

Abstract: The objective of this study was to distinguish within a population of patients with and without breast cancer. The study was based on the University of Wisconsin''s dataset of 569 patients, of whom 212 were subsequently found to have breast cancer. A subset-conjunctive model, which is related to Logical Analysis of Data, is described to distinguish between the two groups of patients based on the results of a non-invasive procedure called Fine Needle Aspiration, which is often used by physicians before deciding on the need for a biopsy. We formulate the problem of inferring subset-conjunctive rules as a 0–1 integer program, show that it is NP-Hard, and prove that it admits no polynomial-time constant-ratio approximation algorithm. We examine the performance of a randomized algorithm, and of randomization using LP rounding. In both cases, the expected performance ratio is arbitrarily bad. We use a deterministic greedy algorithm to identify a Pareto-efficient set of subset-conjunctive rules; describe how the rules change with a re-weighting of the type-I and type-II errors; how the best rule changes with the subset size; and how much of a tradeoff is required between the two types of error as one selects a more stringent or more lax classification rule. An important aspect of the analysis is that we find a sequence of closely related efficient rules, which can be readily used in a clinical setting because they are simple and have the same structure as the rules currently used in clinical diagnosis. [Copyright &y& Elsevier]

A mixed hypergraph is a pair H=(V,E∪A), where V is the vertex set and E (A) the edge (the co-edge) set of H. A legal colouring of H gives the same (different) colour(s) to at least two vertices of any co-edge (of any edge). The upper chromatic number of H is the maximum number χ¯(H) of colours that can be used in a legal colouring. After giving a general upper bound to χ¯(H), we here consider the co-hypergraph S=(X,∅∪T), where T is a (v3,b2)-configuration T over X. We prove that computing χ¯(S) is NP-hard, but there exists a polynomial-time algorithm returning a colouring with &ges;5/6χ¯(S) colours. We also provide an example showing that this approximation factor is tight. [Copyright &y& Elsevier]

In this paper we propose a general algorithm for the asymmetric traveling salesman problem (ATSP) on a complete digraph on n nodes which computes a tour with cost no more than a pre-specified upper bound. A special case of this algorithm is shown to have complexity O(n2) and domination number at least ∑k=0n−2 (k!). Extending this result, we show that by investing O(nk) effort, for k&ges;2 and integer, it is possible to obtain a solution which is at least as good asθ=∑lower limit i=0, upper limit ⌊(n−2)/(k−1)⌋ (n−1−i(k−1))!/n−k−i(k−1)!−(n−k−1−i(k−1)))!+(z−2)!alternative tours, where z=n mod(k−1). Further, we present a patching algorithm for the ATSP and show that it has a domination number at least (n−2)!.Since the symmetric traveling salesman problem can be formulated as an ATSP, these algorithms are applicable in this case too. However, in this case the guaranteed lower bound on the domination number would be half that of the corresponding ATSP algorithm. [Copyright &y& Elsevier]