Search for: All records

We prove that the tree independence number of every even-hole-free graph is at most polylogarithmic in its number of vertices. More explicitly, we prove that there exists a constant c > 0 such that for every integer n > 1 every n-vertex even-hole-free graph has a tree decomposition where each bag has stability (independence) number at most clog10 n. This implies that the Maximum Weight Independent Set problem, as well as several other natural algorithmic problems that are known to be NP-hard in general, can be solved in quasipolynomial time if the input graph is even-hole-free. The quasi-polynomial complexity will remain the same even if the exponent of the logarithm is reduced to 1 (which would be asymptotically best possible). 

Network telemetry systems have become hybrid combinations of state-of-the-art stream processors and modern programmable data-plane devices. However, the existing designs of such systems have not focused on ensuring that these systems are also deployable in practice, i.e., able to scale and deal with the dynamics in real-world traffic and query workloads. Unfortunately, efforts to scale these hybrid systems are hampered by severe constraints on available compute resources in the data plane (e.g., memory, ALUs). Similarly, the limited runtime programmability of existing hardware data-plane targets critically affects efforts to make these systems robust. This paper presents the design and implementation of DynaMap, a new hybrid telemetry system that is both robust and scalable. By planning for telemetry queries dynamically, DynaMap allows the remapping of stateful dataflow operators to data-plane registers at runtime. We model the problem of mapping dataflow operators to data-plane targets formally and develop a new heuristic algorithm for solving this problem. We implement our algorithm in prototype and demonstrate its feasibility with existing hardware targets based on Intel Tofino. Using traffic workloads from different real-world production networks, we show that our prototype of DynaMap improves performance on average by 1-2 orders of magnitude over state-of-the-art hybrid systems that use only static query planning. 

Given a graphGand an integerk, theInterval Vertex Deletion (IVD)problem asks whether there exists a subsetS⊆V(G) of size at mostksuch thatG-Sis an interval graph. This problem is known to beNP-complete (according to Yannakakis at STOC 1978). Originally in 2012, Cao and Marx showed thatIVDis fixed parameter tractable: they exhibited an algorithm with running time 10^kn^O(1). The existence of a polynomial kernel forIVDremained a well-known open problem in parameterized complexity. In this article, we settle this problem in the affirmative. 

Abstract A class of graphs admits the Erdős–Pósa property if for any graph , either has vertex‐disjoint “copies” of the graphs in , or there is a set of vertices that intersects all copies of the graphs in . For any graph class , it is natural to ask whether the family of obstructions to has the Erdős–Pósa property. In this paper, we prove that the family of obstructions to interval graphs—namely, the family of chordless cycles and asteroidal witnesses (AWs)—admits the Erdős–Pósa property. In turn, this yields an algorithm to decide whether a given graph has vertex‐disjoint AWs and chordless cycles, or there exists a set of vertices in that hits all AWs and chordless cycles.