The weighted stable matching problem

We study the stable matching problem in non-bipartite graphs with incomplete but strict preference lists, where the edges have weights and the goal is to compute a stable matching of minimum or maximum weight. This problem is known to be NP-hard in general. Our contribution is two fold: a polyhedral characterization and an approximation algorithm. Previously Chen et al. have shown that the stable matching polytope is integral if and only if the subgraph obtained after running phase one of Irving's algorithm is bipartite. We improve upon this result by showing that there are instances where this subgraph might not be bipartite but one can further eliminate some edges and arrive at a bipartite subgraph. Our elimination procedure ensures that the set of stable matchings remains the same, and thus the stable matching polytope of the final subgraph contains the incidence vectors of all stable matchings of our original graph. This allows us to characterize a larger class of instances for which the weighted stable matching problem is polynomial-time solvable. We also show that our edge elimination procedure is best possible, meaning that if the subgraph we arrive at is not bipartite, then there is no bipartite subgraph that has the same set of stable matchings as the original graph. We complement these results with a 2-approximation algorithm for the minimum weight stable matching problem for instances where each agent has at most two possible partners in any stable matching. This is the first approximation result for any class of instances with general weights.

New Graph Algorithms via Polyhedral Techniques

Jakub Tarnawski

In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. Somewhat surprisingly, similar polyhedral techniques can be harnessed in the two seemingly disparate settings. In the first part of the thesis we address a benchmark problem in combinatorial optimization: the asymmetric traveling salesman problem (ATSP). It consists in finding the shortest tour that visits all vertices of a given directed graph with weights on edges. Due to its NP-hardness, the theoretical study of algorithms for ATSP has focused on approximation algorithms: ones that are provably both efficient and give solutions competitive with the optimum. Specifically, a rho-approximation algorithm for ATSP is one that runs in polynomial time and always outputs a tour that is at most rho times longer than the shortest tour. Finding such an approximation algorithm with rho bounded (i.e., a constant factor) had been a long-standing open problem. In this thesis, we give such an algorithm. Our approximation guarantee is analyzed with respect to the standard linear programming relaxation, and thus our result also confirms the conjectured constant integrality gap of that relaxation. Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics due to Svensson. In particular, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. This reduction takes advantage of a laminar family of vertex sets that arises from the linear programming relaxation. In the second part of the thesis we address the perfect matching problem. The first polynomial-time algorithm for it, given by Edmonds in 1965, is historically associated with the introduction of the class P and our notion that polynomial-time'' means efficient''. That algorithm is sequential and deterministic. We have also known since the 1980s that the matching problem has efficient parallel algorithms if the use of randomness is allowed. Formally, it is in the class RNC, i.e., it has randomized algorithms that use polynomially many processors and run in polylogarithmic time. However, we do not know if randomness is necessary - that is, whether the matching problem is in the class NC. In this thesis we show that the matching problem is in quasi-NC. That is, we give a deterministic parallel algorithm that runs in O(log^3 n) time on n^{O(log^2 n)} processors. The result is obtained by a derandomization of the Isolation Lemma for perfect matchings, which was introduced in the classic paper by Mulmuley, Vazirani and Vazirani to obtain an RNC algorithm. Our proof extends the framework of Fenner, Gurjar and Thierauf, who proved the analogous result in the special case of bipartite graphs. Compared to that setting, several new ingredients are needed due to the significantly more complex structure of perfect matchings in general graphs. In particular, our proof heavily relies on the laminar structure of the faces of the perfect matching polytope.

EPFL2019

Generalized vertex coloring problems using split graphs

Tinaz Ekim

Graph theory experienced a remarkable increase of interest among the scientific community during the last decades. The vertex coloring problem (Min Coloring) deserves a particular attention rince it has been able to capture a wide variety of applications. For mathematicians, it is interesting for an additional reason: it is extremely hard to solve it in an efficient way. In this thesis, we introduce several problems generalizing the usual vertex coloring problem, and hence, extending its application domain. We say that a graph is (p, k)-colorable if its vertex set can be partitioned into p cliques and k stable sets. Then, for a given p (respectively k), one may ask the following questions: how to choose p cliques (respectively k stable sets) to be removed from the graph such that the number of stable sets (respectively cliques) partitioning the remaining vertices is minimized? These are called (p, k)-coloring problems. We also introduce Min Split-coloring which is, given a graph G, the problem of minimizing k such that G is (k, k)-colorable. Along the saine line, given a graph G, the objective of the problem Min Cocoloring is to minimize p + k such that G is (p, k)-colorable. All these problems, called together generalized coloring problems, are obviously at least as difficult as Min Coloring. The purpose of this dissertation is to study generalized coloring problems in nome restricted classes of graphs in order to bring a new insight on the relative difficulties of these problems. To this end, we detect in a more precise way the limits between NP-hard and polynomially solvable problems. Chapter 1 introduces generalized coloring problems by emphasizing nome preliminary results which will guide the questions to handle in the following chapters. Chapter 2 exposes the first clans of graphs, namely cacti, where Min Split-coloring is shown to be polynomially solvable. We also observe that generalized coloring problems can be polynomially solved in triangulated graphs. The main result of Chapter 3 is a new characterization of cographs: it is equivalent to say that G is a cograph, and to state that, for every subgraph G' ⊆ G, G' is (p, k)-colorable if and only if G' [V \ K] is (p – 1, k)-colorable, where K induces a maximum clique of G'. This result implies simple combinatorial algorithme to solve all generalized coloring problems; the one for Min Cocoloring improves the best time complexity known so far. In Chapter 4, we handle the recognition of polar graphs which can be seen as a particular (p, k)-coloring, where p cliques are independent (i.e., not linked at all) and k stable sets form a complete k-partite graph. It is known that the recognition of polar graphs is NP-complete. Here, we determine the first clans of graphs, namely cographs, where the polar graphs can be recognized in polynomial time, more precisely in time O(n log n). We also give a characterization by forbidden subgraphs. In the came manner, we characterize monopolar cographs, i.e., cographs admitting a polar partition with at most one clique or at most one stable set. Chapter 5 is devoted to generalized coloring problems in line graphs. Here, we detect the first classes of graphs, namely line graphs of trees, line graphs of bipartite graphs and line graphs of line-perfect graphs, where generalized coloring problems diverge in terms of NP-hardness. In Chapter 6 we study the approximability of generalized coloring problems in line graphs, in comparability graphs and in general graphs. We derive approximation algorithms with a performance guarantee using both the standard approximation ratio and the differential approximation ratio. We show that both Min Split-coloring and Min Cocoloring are at least as hard as Min Coloring to approximate from the standard approximation ratio point of view, whereas, they admit a polynomial time differential approximation scheme and Min Coloring only a constant differential approximation ratio. We also show that Min Cocoloring reduces to Min Split-coloring in all classes of graphs closed under addition of disjoint cliques and under join of a complete k-partite graph. In Chapter 7, we handle two different applications of Min Split-coloring in permutation graphs. They give birth to a new problem, called Min Threshold-coloring, that we study in the came spirit as the other generalized coloring problems. In the last chapter, we present several open questions arising from this thesis.

EPFL2006

On the computational complexity of periodic scheduling

Thomas Rothvoss

In periodic scheduling jobs arrive regularly and have to be executed on one or several machines or processors. An enormous amount of literature has been published on this topic, e.g. the founding work of Liu & Layland [LL73] is among the top cited computer science papers, according to Citeseer database. The majority of these papers is mainly concerned about practical applications and several important theoretical questions remained unsolved. Let S be a set of periodic tasks, where each task τ ∈ S releases a job of running time c(τ) and relative deadline d(τ) at each integer multiple of its period p(τ). In the single-processor scheduling one considers rules like Earliest-Deadline-First (EDF) or Rate-monotonic (RM) scheduling, that determine the order, in which the jobs have to be processed. The principal question here is to predict, whether such a schedule is feasible, i.e. whether all jobs are finished before their individual deadlines. It was well-known that to validate the feasibility of an EDF-schedule, one has to evaluate the condition But the complexity status of this test remained unknown, despite of many heuristic approaches in the literature. We prove that testing this condition is coNP-hard even in special cases, answering an open question of Baruah & Pruhs [BP09]. For a static-priority schedule of implicit-deadline tasks, i.e. d(τ) = p(τ), it is known that the jobs of a task τ will meet their deadlines if and only if there exists a fix-point r ∈ [0,p(τ)] of the equation where the sum ranges over all tasks with priority higher than τ . We settle the complexity status of this problem by proving its NP-hardness, even if one asks for modest approximations. Both results are achieved by bridging the more practically oriented area of Real-time scheduling and the field of algorithmic number theory. In fact, the intractability follows by a chain of reductions to simultaneous Diophantine approximation (SDA), which is a classical problem in the geometry of numbers and deals with finding a small denominator Q ∈ {1,…,N}, that yields a good approximation to a given vector of rational numbers α ∈ Qn, i.e. maxi=1,…,n |Qαi - ⎡Qαi⎦| ≤ ε. We strengthen existing hardness results for SDA such that they admit intractability results also for a directed version, where the goal is to find a Q ∈ {1,…,N} with maxi=1,…,n(⎡Qαi⎤ - Qαi) ≤ ε. We show that this problem remains NP-hard if one asks for an approximation that may exceed the bound N by a factor of nO(1/loglogn) and the error bound ε by 2nO(1). As an application we are able to answer an open question of Conforti et al. [CSW08] negatively by obtaining NP-hardness for the problem of optimizing a linear function over a mixing set {(s,y ∈ R≥0 × Zn | s + aiyi ≥ bi ∀i = 1,…, n}. Furthermore we obtain that, regardless to the used ‖ · ‖p-norm, the problem of finding a shortest positive vector in a lattice is not approximable within a factor of nO(1/loglogn), unless NP = P. For scheduling constrained-deadline tasks (i.e. d(τ) ≤ p(τ)) with a static-priority policy one possibly needs machines, which are a factor f > 1 faster than it is needed for the EDF policy. Baruah & Burns [BB08] sandwiched this factor between 1.5 and 2. We pinpoint this value to f = 1/Ω ≈ 1.76 by characterizing the properties of task systems, which attain this value. Here, Ω ≈ 0.56 is a well known constant from complex calculus, defined as real root of x · ex = 1. We further consider a multiprocessor setting, where a given set of tasks has to be assigned to machines, such that each partition is RM-schedulable and the number of occupied processors is minimized. For the popular case that the tasks are equipped with implicit-deadlines, i.e. d(τ) = p(τ), we develop new algorithms as well as intractability results: We state an asymptotic PTAS under resource augmentation. This is achieved by two concepts: First we derive that using a merging and clustering procedure, the instance can be modified, such that the utilization of tasks is lowerbounded by a constant, without excluding near-optimal solutions. Secondly, we introduce a relaxed notion of feasibility, which yields a drastic reduction of complexity and admits to compute solutions via dynamic programming. We introduce a simple First-Fit-like heuristic and obtain that this algorithm behaves nearly optimal on average, by proving that the expected waste is upperbounded by O(n3/4(log n)3/8), if the instance of n tasks is generated randomly. Here, we assume that the utilization values c(τ)/p(τ) of the tasks are drawn uniformly at random from [0, 1]. We state a new approximation algorithm with a running time of O(n3), which can be sketched as follows: Create a graph with the tasks being the nodes and insert edges, if both incident tasks can be scheduled together on a processor. Then define suitable vertex costs and compute a min-cost matching, where the costs are the sum of edge costs plus the vertex costs of not covered nodes. From such a matching solution we can then extract a feasible multiprocessor schedule. The approximation ratio of this algorithm can be proven to tend to 3/2, improving over the previously best known ratio of 7/4 [BLOS95]. We consider a column-based linear programming relaxation for this multiprocessor scheduling problem and derive that the asymptotic integrality gap is located between 4/3 ≈ 1.33 and 1 + ln(2) ≈ 1.69. We disprove the existence of an asymptotic FPTAS, which yields that the problem is strictly harder to approximate than its special case of Bin Packing.

EPFL2009