We study the complexity of deciding whether for two given feedback vertex sets of a graph there is a step-by-step transformation between them, such that for each feedback vertex set in the transformation, the next one...
详细信息
We study the complexity of deciding whether for two given feedback vertex sets of a graph there is a step-by-step transformation between them, such that for each feedback vertex set in the transformation, the next one is obtained by exchanging a single vertex. We give a classification of the complexity of this question for planar graphs in terms of the maximum degree. We show that for planar graphs of maximum degree at most three the problem is tractable because there always exists a transformation, while it is PSPACE-complete when the maximum degree is at most four. The positive side of the classification extends to K-3,K-3-minor-free graphs of maximum degree three. We then consider the Matroid Parity problem, which generalizes feedback vertex sets in graphs of maximum degree three as well as matchings and spanning trees in general graphs. Generalizing known results for the latter two we show that there always exists a transformation between any two non -maximum independent parity sets.(c) 2023 Elsevier B.V. All rights reserved.
We consider scheduling problems with uniform parallel machines to minimize the sum of the total (weighted) completion time and the total cost for usage of machines. A cost density function is given for each machine in...
详细信息
We consider scheduling problems with uniform parallel machines to minimize the sum of the total (weighted) completion time and the total cost for usage of machines. A cost density function is given for each machine in advance. Integrating the cost density function for the time period(s) when the machine is busy, one obtains the cost of using this machine in a schedule. We suggest the classification of the problems under consideration according to the type of the cost density functions. The notions of a simple cost density function and an almost concave cost density function are introduced. For these types of cost density functions, we investigate the properties of optimal schedules. Based on these properties, we develop two families of exact pseudo-polynomial DP algorithms. For the case of two uniform machines, we present an FPTAS. Besides, a polynomial-solvable case of the problem is considered.
The matroid parity (or matroid matching) problem, introduced as a common generalization of matching and matroid intersection problems, is so general that it requires an exponential number of oracle calls. Nevertheless...
详细信息
The matroid parity (or matroid matching) problem, introduced as a common generalization of matching and matroid intersection problems, is so general that it requires an exponential number of oracle calls. Nevertheless, Lov\'asz [Acta Sci. Math., 42 (1980), pp. 121-131] showed that this problem admits a min-max formula and a polynomialalgorithm for linearly represented matroids. Since then efficient algorithms have been developed for the linear matroid parity problem. In this paper, we present a combinatorial, deterministic, polynomial-time algorithm for the weighted linear matroid parity problem. The algorithm builds on a polynomial matrix formulation using Pfaffian and adopts a primal-dual approach based on the augmenting path algorithm of Gabow and Stallmann [Combinatorica, 6 (1986), pp. 123-150] for the unweighted problem.
The Hospitals/Residents problem (HR) is a many-to-one matching problem whose solution concept is stability. It is widely used in assignment systems such as assigning medical students (residents) to hospitals. To resol...
详细信息
The Hospitals/Residents problem (HR) is a many-to-one matching problem whose solution concept is stability. It is widely used in assignment systems such as assigning medical students (residents) to hospitals. To resolve imbalance in the number of residents assigned to hospitals, an extension called HR with regional caps (HRRC) was introduced. In this problem, a positive integer (called a regional cap) is associated with a subset of hospitals (called a region), and the total number of residents assigned to hospitals in a region must be at most its regional cap. Kamada and Kojima [1,2] defined strong stability for HRRC and demonstrated that a strongly stable matching does not necessarily exist. Recently, Aziz et al. [3] proved that the problem of determining if a strongly stable matching exists is NP-complete in general. In this paper, we refine Aziz et al.'s result by investigating the computational complexity of the problem in terms of the length of preference lists, the size of regions, and whether or not regions can overlap, and completely classify tractable and intractable cases.
A bipartite graph G = (A, B, E) is 7-t-convex for some family of graphs 7-t if there exists a graph H is an element of 7-t with V (H) = A such that the neighbours in A of each b is an element of B induce a connected s...
详细信息
A bipartite graph G = (A, B, E) is 7-t-convex for some family of graphs 7-t if there exists a graph H is an element of 7-t with V (H) = A such that the neighbours in A of each b is an element of B induce a connected subgraph of H. Many NP-complete problems are polynomial-time solvable for 7-t-convex graphs when 7-t is the set of paths. The underlying reason is that the class has bounded mim-width. We extend this result to families of 7-t-convex graphs where 7-t is the set of cycles, or 7-t is the set of trees with bounded maximum degree and a bounded number of vertices of degree at least 3. As a consequence, we strengthen many known results via one general and short proof. We also show that the mim-width of 7-t-convex graphs is unbounded if 7-t is the set of trees with arbitrarily large maximum degree or an arbitrarily large number of vertices of degree at least 3. (c) 2023 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).
A dynamic flow network consists of a directed graph, where nodes called sources represent locations of evacuees, and nodes called sinks represent locations of evacuation facilities. Each source and each sink are given...
详细信息
A dynamic flow network consists of a directed graph, where nodes called sources represent locations of evacuees, and nodes called sinks represent locations of evacuation facilities. Each source and each sink are given supply representing the number of evacuees and demand representing the maximum number of acceptable evacuees, respectively. Each edge is given capacity and transit time. . Here, the capacity of an edge bounds the rate at which evacuees can enter the edge per unit time, and the transit time represents the time which evacuees take to travel across the edge. The evacuation completion time is the minimum time at which each evacuee can arrive at one of the evacuation facilities. Given a dynamic flow network without sinks, once sinks are located on some nodes or edges, the evacuation completion time for this sink location is determined. We then consider the problem of locating sinks to minimize the evacuation completion time, called the sink location problem. . The problems have been given polynomial-time algorithms only for limited networks such as paths [1-3], cycles [1], and trees [4-6], but no polynomial-time algorithms are known for more complex network classes. In this paper, we prove that the 1-sink location problem can be solved in polynomial-time when an input network is a grid with uniform edge capacity and transit time.
A subset S of vertices of G is a total dominating set if, for any vertex v , there is a vertex in S adjacent to v . A total dominating set S is a secure total dominating set if, for any vertex v is not an element of S...
详细信息
A subset S of vertices of G is a total dominating set if, for any vertex v , there is a vertex in S adjacent to v . A total dominating set S is a secure total dominating set if, for any vertex v is not an element of S , there is a vertex u ES such that uv is an edge and (S \ {u}) U {v} is also a total dominating set. In this paper, we design an O(m)-timealgorithm for computing a minimum secure total dominating set in a proper interval graph, where m is the number of edges.
Computing Wasserstein barycenters is a fundamental geometric problem with widespread applications in machine learning, statistics, and computer graphics. However, it is unknown whether Wasserstein barycenters can be c...
详细信息
Computing Wasserstein barycenters is a fundamental geometric problem with widespread applications in machine learning, statistics, and computer graphics. However, it is unknown whether Wasserstein barycenters can be computed in polynomialtime, either exactly or to high precision (i.e., with polylog(1/ε) runtime dependence). This paper answers these questions in the affirmative for any fixed dimension. Our approach is to solve an exponential-size linear programming formulation by efficiently implementing the corresponding separation oracle using techniques from computational geometry.
The single-unit commitment problem (1UC) is the problem of finding a cost optimal schedule for a single generator given a time series of electricity prices subject to generation limits, minimum upand downtime and ramp...
详细信息
The single-unit commitment problem (1UC) is the problem of finding a cost optimal schedule for a single generator given a time series of electricity prices subject to generation limits, minimum upand downtime and ramping limits. In this paper we present two efficient dynamic programming algorithms. For each time step we keep track of a set of functions that represent the cost of optimal schedules until that time step. We show that we can combine a subset of these functions by only considering their minimum. We can construct this minimum either implicitly or explicitly. Experiments show both methods scale linear in the amount of time steps and result in a significant speedup compared to the state-of-the-art for piece-wise linear as well as quadratic generation cost. Therefore using these methods could lead to significant improvements for solving large scale unit commitment problems with Lagrangian relaxation or related methods that use 1UC as subproblem.
暂无评论