Explore the vast range of titles available.

Tashkinov-trees have been used as a tool for proving bounds on the chromatic index, and are becoming a fundamental tool for edge-coloring. Was its publication in a language different from English an obstacle for the accessibility of a clean and complete proof of Tashkinov’s fundamental theorem? Tashkinov’s original Russian paper offers a clear presentation of this theorem and its proof. The theorem itself has been well understood and successfully applied, but the proof is more difficult. It builds a truly amazing recursive machine, where the various cases necessitate a refined and polished analysis to fit into one another with surprising smoothness and accuracy. The difficulties were brilliantly unknotted by the author, deserving repeated attention. The present work is the result of reading, translating, reorganizing, rewriting, completing, shortcutting and annotating Tashkinov’s proof. It is essentially the same proof, though with non-negligible communicational differences; for instance, completing it where it appeared to be necessary and simplifying it when it appeared to be possible, while at the same time trying to adapt it to the habits and taste of the international graph theory community.

We study generators of metric spaces—sets of points with the property that every point of the space is uniquely determined by the distances from their elements. Such generators put a light on seemingly different kinds of problems in combinatorics that are not directly related to metric spaces. The two applications we present concern combinatorial search: problems on false coins known from the borderline of extremal combinatorics and information theory; and a problem known from combinatorial optimization—connected joins in graphs. We use results on the detection of false coins to approximate the metric dimension (minimum size of a generator for the metric space defined by the distances) of some particular graphs for which the problem was known and open. In the opposite direction, using metric generators, we show that the existence of connected joins in graphs can be solved in polynomial time, a problem asked in a survey paper of Frank. On the negative side we prove that the minimization of the number of components of a join is NP-hard. We further explore the metric dimension with some problems. The main problem we are led to is how to extend an isometry given on a metric generator of a metric space.

Given an undirected graph, are there k matchings whose union covers all of its nodes, that is, a matching-k-cover ? When k = 1 , the problem is equivalent to the existence of a perfect matching for which Tutte’s celebrated matching theorem (J. Lon. Math. Soc., 1947) provides a ‘good’ characterization. We prove here, when k is greater than one, a ‘good’ characterization à la Kőnig : for k ≥ 2 , there exist k matchings covering every node if and only if for every stable set S , we have | S | ≤ k · | N ( S ) | . Moreover, somewhat surprisingly, we use only techniques from bipartite matching in the proof, through a simple, polynomial algorithm. A different approach to matching-k-covers has been previously suggested by Wang et al. (Math. Prog., 2014), relying on general matching and using matroid union for matching-matroids, or the Edmonds-Gallai structure theorem. Our approach provides a simpler polynomial algorithm together with an elegant certificate of non-existence when appropriate. Further results, generalizations and interconnections between several problems are then deduced as consequences of the new minimax theorem, with surprisingly simple proofs (again using only the level of difficulty of bipartite matchings). One of the equivalent formulations leads to a solution of weighted minimization for non-negative edge-weights, while the edge-cardinality maximization of matching-2-covers turns out to be already NP-hard. We have arrived at this problem as the line graph special case of a model arising for manufacturing integrated circuits with the technology called ‘Directed Self Assembly’.

We provide a polynomial algorithm that determines for any given undirected graph $G=(V,E)$, positive integer $k$, and convex functions $f_v:\\mathbb{N}\\rightarrow\\mathbb{R}$ ($v\\in V$) a subgraph $H=(V,F)$ of $k$ edges that minimizes $\\sum_{v\\in V}f_v(d_H(v))$, where $d_H(v)$ is the degree of $v$ in $H$. The motivation and at the same time the main application of the results is the problem of finding a subset of $k$ vertices in a line graph that covers as many edges as possible. The latter problem generalizes the vertex cover problem for line graphs, which is in turn equivalent to the maximum matching problem in graphs. Improving paths or walks for factorization problems have to be completed by pairs of such walks for this problem. We provide several solutions leading to different variants of the problem and also show the limits of the methods by proving the NP-completeness of some direct extensions, in particular to all convex functions.

In this paper we provide characterizing properties of totally dual integral (TDI) systems, among others the following: a system of linear inequalities is TDI if and only if its coefficient vectors form a Hilbert basis, and there exists a test-set for the system’s dual integer programs where all test vectors have positive entries equal to 1. Reformulations of this provide relations between computational algebra and integer programming and they contain Applegate, Cook and McCormick’s sufficient condition for the TDI property and Sturmfels’ theorem relating toric initial ideals generated by square-free monomials to unimodular triangulations. We also study the theoretical and practical efficiency and limits of the characterizations of the TDI property presented here. In the particular case of set packing polyhedra our results correspond to endowing the weak perfect graph theorem with an additional, computationally interesting, geometric feature: the normal fan of the stable set polytope of a perfect graph can be refined into a regular triangulation consisting only of unimodular cones.

We give a new, strongly polynomial-time algorithm and improved analysis for the metric \\(s-t\\) path TSP. It finds a tour of cost less than 1.53 times the optimum of the subtour elimination LP, while known examples show that 1.5 is a lower bound for the integrality gap. A key new idea is the deletion of some edges of Christofides' trees, which is then accompanied by novel arguments of the analysis: edge-deletion disconnects the trees, which are then partly reconnected by `parity correction'. We show that the arising `connectivity correction' can be achieved for a minor extra cost. On the one hand this algorithm and analysis extend previous tools such as the best-of-many Christofides algorithm. On the other hand, powerful new tools are solicited, such as a flow problem for analyzing the reconnection cost, and the construction of a set of more and more restrictive spanning trees, each of which can still be found by the greedy algorithm. We show that these trees can replace the convex combination of spanning trees in the best-of-may Christofides algorithm. These new methods lead to improving the integrality ratio and approximation guarantee below 1.53, as it is already sketched in the preliminary shortened version of this article that appeared in FOCS 2016. The algorithm and analysis have been significantly simplified in the current article, and details of proofs and explanations have been added.

In this paper we are concerned with the so-called clique-colorations of a graph, that is, colorations of the vertices so that no maximal clique is monochromatic. On one hand, it is known to be NP-complete to decide whether a perfect graph is 2-clique-colorable, or whether a triangle-free graph is 3-clique-colorable; on the other hand, there is no example of a perfect graph where more than three colors would be necessary. We first exhibit some simple recursive methods to clique-color graphs and then relate the chromatic number, the domination number, and the maximum cardinality of a stable set to the clique-chromatic number. We show exact bounds and polynomial algorithms that find the clique-chromatic number for some classes of graphs and prove NP-completeness results for some others, trying to find the boundary between the two. For instance, while it is NP-complete to decide whether a graph of maximum degree 3 is 2-clique-colorable, K1,3-free graphs without an odd hole turn out to be always 2-clique-colorable by a polynomial algorithm. Finally, we show that \"almost\" all perfect graphs are 3-clique-colorable.

Given a finite family of squares in the plane, the packing problem asks for the maximum number \\(\\nu\\) of pairwise disjoint squares among them, while the hitting problem for the minimum number \\(\\tau\\) of points hitting all of them. Clearly, \\(\\tau \\ge \\nu\\). Both problems are known to be NP-hard, even for families of axis-parallel unit squares. The main results of this work provide the first non-trivial bounds for the \\(\\tau / \\nu\\) ratio for not necessarily axis-parallel squares. We establish an upper bound of \\(6\\) for unit squares and \\(10\\) for squares of varying sizes. The worst ratios we can provide with examples are \\(3\\) and \\(4\\), respectively. For comparison, in the axis-parallel case, the supremum of the considered ratio is in the interval \\([\\frac{3}{2},2]\\) for unit squares and \\([\\frac{3}{2},4]\\) for squares of varying sizes. The methods we introduced for the \\(\\tau/\\nu\\) ratio can also be used to relate the chromatic number \\(\\chi\\) and clique number \\(\\omega\\) of squares by bounding the \\(\\chi/\\omega\\) ratio by \\(6\\) for unit squares and \\(9\\) for squares of varying sizes. The \\(\\tau / \\nu\\) and \\(\\chi/\\omega\\) ratios have already been bounded before by a constant for \"fat\" objects, the fattest and simplest of which are disks and squares. However, while disks have received significant attention, specific bounds for squares have remained essentially unexplored. This work intends to fill this gap.

We consider the problem of minimizing the size of a family of sets such that every subset of {1,. . ., n} can be written as a disjoint union of at most k members of , where k and n are given numbers. This problem originates in a real-world application aiming at the diversity of industrial production. At the same time, the question of finding the minimum of || so that every subset of {1,. . ., n} is the union of two sets in was asked by Erdős and studied recently by Füredi and Katona without requiring the disjointness of the sets. A simple construction providing a feasible solution is conjectured to be optimal for this problem for all values of n and k and regardless of the disjointness requirement; we prove this conjecture in special cases including all (n, k) for which n≤3k holds, and some individual values of n and k.