• A (2 + ε)-Factor Approximation Algorithm for Split Vertex Deletion 

      Lokshtanov, Daniel; Misra, Pranabendu; Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket (Journal article; Peer reviewed, 2020)
      In the Split Vertex Deletion (SVD) problem, the input is an n-vertex undirected graph G and a weight function w: V(G) → ℕ, and the objective is to find a minimum weight subset S of vertices such that G-S is a split graph ...
    • An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL 

      Fomin, Fedor; Golovach, Petr; Stamoulis, Giannos; Thilikos, Dimitrios M. (Journal article; Peer reviewed, 2020)
      In general, a graph modification problem is defined by a graph modification operation ⊠ and a target graph property 𝒫. Typically, the modification operation ⊠ may be vertex removal, edge removal, edge contraction, or edge ...
    • Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes 

      Lima, Paloma T.; van Leeuwen, Erik Jan; van der Wegen, Marieke (Journal article; Peer reviewed, 2020)
      Given a vertex-colored graph, we say a path is a rainbow vertex path if all its internal vertices have distinct colors. The graph is rainbow vertex-connected if there is a rainbow vertex path between every pair of its ...
    • Approximation in (poly-) logarithmic space 

      Biswas, Arindam; Raman, Venkatesh; Saurabh, Saket (Journal article; Peer reviewed, 2020)
      We develop new approximation algorithms for classical graph and set problems in the RAM model under space constraints. As one of our main results, we devise an algorithm for d–Hitting Set that runs in time nO(d2+(d/ε)), ...
    • b-Coloring Parameterized by Clique-Width 

      Jaffke, Lars; Lima, Paloma Thome de; Lokshtanov, Daniel (Journal article; Peer reviewed, 2021)
      We provide a polynomial-time algorithm for b-Coloring on graphs of constant clique-width. This unifies and extends nearly all previously known polynomial-time results on graph classes, and answers open questions posed by ...
    • Bisection of Bounded Treewidth Graphs by Convolutions 

      Eiben, Eduard; Lokshtanov, Daniel; Mouawad, Amer E. (Journal article; Peer reviewed, 2019)
      In the Bisection problem, we are given as input an edge-weighted graph G. The task is to find a partition of V(G) into two parts A and B such that ||A| - |B|| <= 1 and the sum of the weights of the edges with one endpoint ...
    • Building large k-cores from sparse graphs 

      Fomin, Fedor; Sagunov, Danil; Simonov, Kirill (Journal article; Peer reviewed, 2020)
      A popular model to measure network stability is the k-core, that is the maximal induced subgraph in which every vertex has degree at least k. For example, k-cores are commonly used to model the unraveling phenomena in ...
    • Close Relatives of Feedback Vertex Set Without Single-Exponential Algorithms Parameterized by Treewidth 

      Bergougnoux, Benjamin; Bonnet, Édouard; Brettell, Nick; Kwon, O-Joung (Journal article; Peer reviewed, 2020)
      The Cut & Count technique and the rank-based approach have lead to single-exponential FPT algorithms parameterized by treewidth, that is, running in time 2^𝒪(tw)n^𝒪(1), for Feedback Vertex Set and connected versions of ...
    • Co-Degeneracy and Co-Treewidth: Using the Complement to Solve Dense Instances 

      Duarte, Gabriel; Oliveira, Mateus De Oliveira; Souza, Uéverton S. (Journal article; Peer reviewed, 2021)
      Clique-width and treewidth are two of the most important and useful graph parameters, and several problems can be solved efficiently when restricted to graphs of bounded clique-width or treewidth. Bounded treewidth implies ...
    • Coherence for Monoidal Groupoids in HoTT 

      Piceghello, Stefano (Journal article; Peer reviewed, 2020)
      We present a proof of coherence for monoidal groupoids in homotopy type theory. An important role in the formulation and in the proof of coherence is played by groupoids with a free monoidal structure; these can be represented ...
    • Complexity of the Steiner Network Problem with Respect to the Number of Terminals 

      Eiben, Eduard; Knop, Dusan; Panolan, Fahad; Suchý, Ondřej (Journal article; Peer reviewed, 2019)
      In the Directed Steiner Network problem we are given an arc-weighted digraph G, a set of terminals T subseteq V(G) with |T|=q, and an (unweighted) directed request graph R with V(R)=T. Our task is to output a subgraph H ...
    • Compressing permutation groups into grammars and polytopes. A graph embedding approach 

      Jaffke, Lars; De Oliveira Oliveira, Mateus; Tiwary, Hans Raj (Journal article; Peer reviewed, 2020)
      It can be shown that each permutation group G ⊑ 𝕊_n can be embedded, in a well defined sense, in a connected graph with O(n+|G|) vertices. Some groups, however, require much fewer vertices. For instance, 𝕊_n itself can ...
    • Connecting the Dots (with Minimum Crossings) 

      Agrawal, Akanksha; Guspiel, Grzegorz; Madathil, Jayakrishnan; Saurabh, Saket; Zehavi, Meirav (Journal article; Peer reviewed, 2019)
      We study a prototype Crossing Minimization problem, defined as follows. Let F be an infinite family of (possibly vertex-labeled) graphs. Then, given a set P of (possibly labeled) n points in the Euclidean plane, a collection ...
    • Diverse Collections in Matroids and Graphs 

      Fomin, Fedor; Golovach, Petr; Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket (Journal article; Peer reviewed, 2021)
      We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems, two from the theory of matroids and the third from graph theory. The input to the Weighted Diverse ...
    • Diverse Pairs of Matchings 

      Fomin, Fedor; Golovach, Petr; Jaffke, Lars; Philip, Geevarghese; Sagunov, Danil (Journal article; Peer reviewed, 2020)
      We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matchings problems which given a graph G and an integer k, ask whether G has two (maximum/perfect) matchings whose symmetric difference is at least k. Diverse ...
    • ETH Tight Algorithms for Geometric Intersection Graphs: Now in Polynomial Space 

      Fomin, Fedor; Golovach, Petr; Inamdar, Tanmay Nitin; Saurabh, Saket (Journal article; Peer reviewed, 2021)
      De Berg et al. in [SICOMP 2020] gave an algorithmic framework for subexponential algorithms on geometric graphs with tight (up to ETH) running times. This framework is based on dynamic programming on graphs of weighted ...
    • ETH-tight algorithms for long path and cycle on unit disk graphs 

      Fomin, Fedor; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav (Journal article; Peer reviewed, 2020)
      We present an algorithm for the extensively studied Long Path and Long Cycle problems on unit disk graphs that runs in time 2O(√k)(n + m). Under the Exponential Time Hypothesis, Long Path and Long Cycle on unit disk graphs ...
    • Exact and approximate digraph bandwidth 

      Jain, Pallavi; Kanesh, Lawqueen; Lochet, William; Saurabh, Saket; Sharma, Roohani (Journal article; Peer reviewed, 2019)
      In this paper, we introduce a directed variant of the classical Bandwidth problem and study it from the view-point of moderately exponential time algorithms, both exactly and approximately. Motivated by the definitions of ...
    • Fault tolerant subgraphs with applications in kernelization 

      Lochet, William; Lokshtanov, Daniel; Misra, Pranabendu; Saurabh, Saket; Sharma, Roohani; Zehavi, Meirav (Journal article; Peer reviewed, 2020)
      In the past decade, the design of fault tolerant data structures for networks has become a central topic of research. Particular attention has been given to the construction of a subgraph H of a given digraph D with as ...
    • Hierarchical clusterings of unweighted graphs 

      Høgemo, Svein; Paul, Christophe; Telle, Jan Arne (Journal article; Peer reviewed, 2020)
      We study the complexity of finding an optimal hierarchical clustering of an unweighted similarity graph under the recently introduced Dasgupta objective function. We introduce a proof technique, called the normalization ...