Welcome !
This is a weekly seminar for invited talks on parameterized complexity for people based in India, who are working in parameterized complexity and related areas. Follow the page for regular updates on upcoming and previous talks.
When & Where: 8:30pm IST every Tuesday on Zoom (session details to be communicated via email) .
Date: 15th June, 2021
Speaker: Niels Grüttemeier
PhD Student
Philipps University of Marburg.
Title of the talk: On the Parameterized Complexity of Polytree Learning.
Abstract: A Bayesian network is a directed acyclic graph that represents statistical dependencies between variables of a joint probability distribution. A fundamental task in data science is to learn a Bayesian network from observed data. Polytree Learning is the problem of learning an optimal Bayesian network that fulfills the additional property that its underlying undirected graph is a forest. In this talk, I give an introduction into the computational problem of Bayesian Network Structure Learning and the more restricted Polytree Learning. I give an overview about the motivation of these problems and present recent results on the parameterized complexity of Polytree Learning.
Date: 8th June, 2021
Speaker: Yixin Cao
Assistant Professor
Hong Kong Polytechnic University.
Title of the talk: Improved Kernels for Edge Modification Problems.
Abstract: In an edge modification problem, we are asked to modify at most k edges to a given graph to make the graph satisfy a certain property. Depending on the operations allowed, we have the completion problems and the edge deletion problems. A great amount of efforts have been devoted to understanding the kernelization complexity of these problems. We revisit several well-studied edge modification problems, and develop improved kernels for them:
a 2 k-vertex kernel for the cluster edge deletion problem,
a 3 k2-vertex kernel for the trivially perfect completion problem,
a 5 k1.5-vertex kernel for the split completion problem and the split edge deletion problem, and
a 5 k1.5-vertex kernel for the pseudo-split completion problem and the pseudo-split edge deletion problem.
Moreover, our kernels for split completion and pseudo-split completion have only O(k2.5) edges. Our results also include a 2 k-vertex kernel for the strong triadic closure problem, which is related to cluster edge deletion, and a polynomial-time algorithm for the pseudo-split edge editing problem.
Date: 1st June, 2021
Speaker: Raghavendra Rao B. V.
Associate Professor
Indian Institute of Technology Madras, India.
Title of the talk: Parameterised Counting in Logspace.
Abstract: Logarithmic space bounded complexity classes such as L and NL play a central role in space bounded computation. The study of counting versions of these complexity classes has led to several interesting insights into the structure of computational problems such as computing the determinant and counting paths in directed acyclic graphs. Though parameterised complexity theory was initiated roughly three decades ago by Downey and Fellows, a satisfactory study of parameterised logarithmic space bounded computation was developed only in the last decade by Elberfeld, Stockhusen, and Tantau (IPEC 2013, Algorithmica 2015).
In this talk, we will see a new framework for parameterised counting in logspace, inspired by the parameterised space bounded models developed by Elberfeld, Stockhusen and Tantau (IPEC 2013, Algorithmica 2015). We will introduce counting versions of all four operators introduced by Elberfeld, Stockhusen and Tantau (IPEC 2013, Algorithmica 2015) and discuss several natural complete problems for the resulting classes: counting of paths in digraphs, counting first-order models for formulas, and counting graph homomorphisms. Furthermore, we show that the complexity of a parameterised variant of the determinant function for (0,1)-matrices is #para_beta_tail L-hard and can be written as the difference of two functions in #para_beta_tail L. These problems exhibit the richness of the introduced counting classes. We will conclude with several interesting open questions and research directions.
This is joint work with Anselm Haak, Arne Meier, and Om Prakash.
Date: 25th May, 2021
Speaker: Nidhi Purohit
PhD Candidate
University of Bergen.
Title of the talk: Parameterized Complexity of Categorical Clustering with Size Constraints .
Abstract: Capacitated Clustering is a generalization of Categorical Clustering, where the size of each cluster should be within a given interval. In Capacitated Clustering: we are given a matrix A with m rows and n columns over a binary alphabet, integers k, p, q and budget B. The goal is to partition A into k clusters such that the median objective of the clustering in the Hamming norm is at most B, and the sizes of the clusters are at least p and at most q, respectively. Fomin et al. [ICALP, 2018] showed that Categorical clustering is FPT when parameterized by B. We generalize their result and observe that the cluster's size constraints do not affect the problem's parameterized complexity. We give an algorithm showing that the Capacitated clustering is FPT parameterized by B and the alphabet size. We also give the kernels for several other variants of Categorical Clustering where the cluster's sizes satisfy certain balance properties.
Joint work with Fedor V. Fomin and Petr A. Golovach.
Date: 18th May, 2021
Speaker: Marc Roth
Postdoctoral Junior Research Fellow
Merton College, Oxford University.
Title of the talk: Parameterized Counting and Cayley Graph Expanders. (slides)
Abstract: We study the problem #EdgeSub(P) of counting k-edge subgraphs satisfying a given graph property P in a large host graph G. Our goal is to understand its parameterized and fine-grained complexity, depending on P. Building upon the breakthrough result of Curticapean, Dell and Marx (STOC 17), we express the number of k-edge subgraphs that satisfy P as a finite linear combination of graph homomorphism counts and derive the complexity of computing this number by studying its coefficients.
Our approach relies on novel constructions of low-degree Cayley graph expanders of p-groups, which might be of independent interest. The properties of those expanders allow us to analyse the coefficients in the aforementioned linear combinations over the field GF(p) which gives us significantly more control over their cancellation behaviour. Our main result is an exhaustive complexity classification of #EdgeSub(P) for minor-closed properties: If there is a constant upper bound on the size of every induced matching in graphs satisfying P, or if P is trivially true, then #EdgeSub(P) is fixed-parameter tractable (when parameterized by k). Otherwise, #EdgeSub(P) is #W[1]-hard and no significant improvement over the brute-force algorithm is possible, unless ETH fails.
This is joint work with Norbert Peyerimhoff, Johannes Schmitt, Jakob Stix, Alina Vdovina and Philip Wellnitz.
Date: 11th May, 2021
Speaker: Lars Jaffke
Postdoctoral Researcher
University of Bergen.
Title of the talk: b-Coloring Parameterized by Clique-Width. (slides)
Abstract: A b-coloring of a graph is a proper vertex-coloring in which every color class contains a vertex that has a neighbor in all the remaining color classes. This notion was introduced by Irving and Manlove [Discret. Appl. Math., 1999] to analyze the worst-case behaviour of a heuristic for graph coloring. The b-Coloring problem, in which we are given a graph G and an integer k and the question is whether G has a b-coloring with k colors, has since received considerable attention in the algorithms community. We provide a polynomial-time algorithm for b-Coloring on graphs of constant clique-width; which unifies and extends nearly all previously known polynomial-time results on graph classes, and answers open questions posed by Campos and Silva [Algorithmica, 2018] and Bonomo et al. [Graphs Combin., 2009]. This constitutes the first result concerning structural parameterizations of the b-Coloring problem. We additionally show that it is FPT when parameterized by the vertex cover number on general graphs, and on chordal graphs when parameterized by the number of colors. We observe that our algorithm for graphs of bounded clique-width can be adapted to solve the related Fall Coloring problem within the same runtime bound. The running times of the clique-width based algorithms for b-Coloring and Fall Coloring are tight under the Exponential Time Hypothesis.
This is joint work with Paloma T. Lima and Daniel Lokshtanov.
Date: 4th May, 2021
Speaker: Nikolaos Melissinos
PhD Student
LAMSADE, Paris-Dauphine University.
Title of the talk: Digraph Coloring and Distance to Acyclicity. (slides)
Abstract: In k-Digraph Coloring we are given a digraph and are asked to partition its vertices into at most k sets, so that each set induces a DAG. This well-known problem is NP-hard, as it generalizes (undirected) k-Coloring, but becomes trivial if the input digraph is acyclic. This poses the natural parameterized complexity question what happens when the input is “almost” acyclic. In this paper we study this question using parameters that measure the input’s distance to acyclicity in either the directed or the undirected sense.
It is already known that, for all k ≥ 2, k-Digraph Coloring is NP- hard on digraphs of DFVS at most k + 4. We strengthen this result to show that, for all k ≥ 2, k-Digraph Coloring is NP-hard for DFVS exactly k. Refining our reduction we obtain two further consequences: (i) for all k ≥ 2, k-Digraph Coloring is NP-hard for graphs of feedback arc set (FAS) at most k^2; interestingly, this leads to a dichotomy, as we show that the problem is FPT by k if FAS is at most k^2 − 1; (ii) k-Digraph Coloring is NP-hard for graphs of DFVS k, even if the maximum degree ∆ is at most 4k − 1; we show that this is also almost tight, as the problem becomes FPT for DFVS k and ∆ ≤ 4k − 3.
We then consider parameters that measure the distance from acyclicity of the underlying graph. We show that k-Digraph Coloring admits an FPT algorithm parameterized by treewidth, whose parameter dependence is (tw!)k^tw. Then, we pose the question of whether the tw! factor can be eliminated. Our main contribution in this part is to settle this question in the negative and show that our algorithm is essentially optimal, even for the much more restricted parameter treedepth and for k = 2. Specifically, we show that an FPT algorithm solving 2-Digraph Coloring with dependence td^{o(td)} would contradict the ETH.
Date: 20th April, 2021
Speaker: Lawqueen Kanesh
Postdoctoral Fellow
National University of Singapore.
Title of the talk: An FPT Algorithm for Elimination Distance to Bounded Degree Graphs. (slides)
Abstract: In the literature on parameterized graph problems, there has been an increased effort in recent years aimed at exploring novel notions of graph edit-distance that are more powerful than the size of a modulator to a specific graph class. In this line of research, Bulian and Dawar [Algorithmica, 2016] introduced the notion of elimination distance and showed that deciding whether a given graph has elimination distance at most k to any minor-closed class of graphs is fixed-parameter tractable parameterized by k [Algorithmica, 2017]. They showed that Graph Isomorphism parameterized by the elimination distance to bounded degree graphs is fixed-parameter tractable and asked whether determining the elimination distance to the class of bounded degree graphs is fixed-parameter tractable. Recently, Lindermayr et al. [MFCS 2020] obtained a fixed-parameter algorithm for this problem in the special case where the input is restricted to K5-minor free graphs. We answer the question of Bulian and Dawar in the affirmative for general graphs. In fact, we give a more general result capturing elimination distance to any graph class characterized by a finite set of graphs as forbidden induced subgraphs.
This is a joint work with Akanksha Agrawal, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh and appeared in STACS, 2021.
Date: 13th April, 2021
Speaker: William Lochet
Postdoctoral Fellow
University of Bergen.
Title of the talk: Exploiting Dense Structures in Parameterized Complexity. (slides)
Abstract: Over the past few decades, the study of dense structures (mainly graphs) from the perspective of approximation algorithms has become a wide area of research. In particular, properties of random samples have been successfully deployed to design approximation schemes for a number of fundamental problems on dense structures [Arora et al.~FOCS 1995, Goldreich et al.~FOCS 1996, Giotis and Guruswami SODA 2006, Karpinksi and Schudy~STOC 2009]. Recently, we initiated the study of this class of graphs from the perspective of parameterized complexity. In particular, we obtain linear vertex kernels for Edge-Disjoint Paths, Edge Odd Cycle Transversal, Minimum Bisection, d-Way Cut}, Multiway Cut and Multicut on everywhere dense graphs. In fact, these kernels are obtained by designing a polynomial-time algorithm when the corresponding parameter is at most Ω(n). Additionally, we obtain a cubic kernel for Vertex-Disjoint Paths on everywhere dense graphs. In this talk, we will first see how the properties of random samples can be used to design a subexponential-time algorithm and a linear kernel for the Edge Odd Cycle Transversal problem. Then we will see, using a much more structural approach, how to obtain a linear kernel for the Edge-Disjoint Paths problem.
This is based on a joint work with Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi which appeared in STACS 2021.
Date: 6th April, 2021
Speaker: Shaohua Li
PhD Student
University of Warsaw.
Title of the talk: Cluster Editing parameterized above modification-disjoint P3-packings. (slides)
Abstract: Given a graph G=(V,E) and an integer k, the CLUSTER EDITING problem asks whether we can transform G into a union of vertex-disjoint cliques by at most k modifications (edge deletions or insertions). In this paper, we study the following variant of CLUSTER EDITING. We are given a graph G=(V,E), a packing ℋ of modification-disjoint induced P3s (no pair of P3s in ℋ share an edge or non-edge) and an integer~ℓ. The task is to decide whether G can be transformed into a union of vertex-disjoint cliques by at most ℓ+|ℋ| modifications (edge deletions or insertions). We show that this problem is NP-hard even when ℓ=0 (in which case the problem asks to turn G into a disjoint union of cliques by performing exactly one edge deletion or insertion per element of ℋ). This answers negatively a question of van Bevern, Froese, and Komusiewicz (CSR 2016, ToCS 2018), repeated by Komusiewicz at Shonan meeting no. 144 in March 2019. We then initiate the study to find the largest integer c such that the problem remains tractable when restricting to packings such that each vertex is in at most c packed P3s. Van Bevern et al. showed that the case c = 1 is fixed-parameter tractable with respect to ℓ and we show that the case c = 2 is solvable in |V|2ℓ + O(1) time.
Date: 30th March, 2021
Speaker: Ignasi Sau
Chargé de Recherche CNRS (Junior Researcher), HDR
LIRMM, Montpellier, France.
Title of the talk: Kernelization of Maximum Minimal Vertex Cover (slides)
Abstract: In the Maximum Minimal Vertex Cover (MMVC) problem, we are given a graph G and a positive integer k, and the objective is to decide whether G contains a minimal vertex cover of size at least k. This problem has been considered in several articles in the last years. In this talk we focus on its kernelization, which had been almost unexplored so far. We show that MMVC does not admit polynomial kernels parameterized by the size of a minimum vertex cover or of a maximum matching, unless NP ⊆ coNP/poly. Motivated by a question of Boria et al. [Discret. Appl. Math. 2015] about the existence of subquadratic kernels for MMVC parameterized by k, we rule out their existence unless P=NP, if we restrict the kernelization algorithms to apply only a type of natural reduction rules that we call "large optimal preserving rules''. In particular, these rules contain the typical reduction rules to obtain linear kernels for Vertex Cover. On the positive side, we provide subquadratic kernels on H-free graphs for several graphs H, such as the bull, the paw, or the complete graphs, by making use of the Erdös-Hajnal property in order to find an appropriate decomposition.
Joint work with Júlio Araújo, Marin Bougeret, and Victor A. Campos.
Date: 23rd March, 2021
Speaker: Jan Marcinkowski
PhD Student
University of Wrocław.
Title of the talk: To Close Is Easier Than To Open: Dual Parameterization To k-Median.
Abstract: In the classic k-Median problem we are asked to choose k Facilities out of the possible set F and assign clients to them minimising the sum of distances between clients and their respective facilities. Recently we were studying a Capacitated variant of this problem, where each facility can only serve a limited number of clients. Capacitated k-Median is notoriously difficult to approximate, with the best known ratio of log k. In the seminar talk I will outline results from our two papers on this subject: A constant-factor approximation algorithm for Capacitated k-Median that runs in time parameterised by k; A (1+ε)-approximation algorithm for the regular (Uncapacitated) k-Median that runs in time parameterised by |F|-k; and a reduction showing that such an (1+ε)-approximation cannot exist for the Capacitated problem (conditional on Gap-ETH).
The work had been conducted (in sub-arrangements) together with Marek Adamczyk, Jarosław Byrka, Szymon Dudycz, Syed Mohammad Meesum, Pasin Manurangsi, and Michał Włodarczyk (who just gave a talk in this seminar two weeks before).
Date: 16th March, 2021
Speaker: Siddharth Gupta
Postdoctoral Scholar
Ben-Gurion University, Israel.
Title of the talk: Parameterized Complexity of Finding Subgraphs with Hereditary Properties on Hereditary Graph Classes. (slides)
Abstract: We investigate the parameterized complexity of finding subgraphs with hereditary properties on graphs belonging to a hereditary graph class. Given a graph G, a non-trivial hereditary property Π and an integer parameter k, the general problem P(G,Π,k) asks whether there exists k vertices of G that induce a subgraph satisfying property Π. This problem, P(G,Π,k) has been proved to be NP-Complete by Lewis and Yannakakis. The parameterized complexity of this problem is shown to be W[1]-complete by Khot and Raman, if Π includes all trivial graphs but not all complete graphs and vice versa; and is fixed-parameter tractable (FPT), otherwise. As the problem is W[1]-complete on general graphs when Π includes all trivial graphs but not all complete graphs and vice versa, it is natural to further investigate the problem on restricted graph classes.
Motivated by this line of research, we study the problem on graphs which also belong to a hereditary graph class and establish a framework which settles the parameterized complexity of the problem for various hereditary graph classes. In particular, we show that:
P(G,Π,k) is solvable in polynomial time when the graph G is co-bipartite and Π is the property of being planar, bipartite or triangle-free (or vice-versa).
P(G,Π,k) is FPT when the graph G is planar, bipartite or triangle-free and Π is the property of being planar, bipartite or triangle-free, or graph G is co-bipartite and Π is the property of being co-bipartite.
P(G,Π,k) is W[1]-complete when the graph G is C4-free, K1,4-free or a unit disk graph and Π is the property of being either planar or bipartite.
Date: 9th March, 2021
Speaker: Michal Wlodarczyk
Postdoctoral Fellow
Eindhoven University of Technology, Netherlands.
Title of the talk: Vertex Deletion Parameterized by Elimination Distance and Even Less.
Abstract: We study the parameterized complexity of various classic vertex deletion problems such as Odd cycle transversal, Vertex planarization, and Chordal vertex deletion under hybrid parameterizations. Existing FPT algorithms for these problems either focus on the parameterization by solution size, detecting solutions of size k in time f(k)*n^O(1), or width parameterizations, finding arbitrarily large optimal solutions in time f(w)*n^O(1) for some width measure w like treewidth. We unify these lines of research by presenting FPT algorithms for parameterizations that can simultaneously be arbitrarily much smaller than the solution size and the treewidth.
We consider two classes of parameterizations which are relaxations of either treedepth or treewidth. They are related to graph decompositions in which subgraphs that belong to a target class H (e.g., bipartite or planar) are considered simple. First, we present a framework for computing approximately optimal decompositions for miscellaneous classes H. Namely, if the cost of an optimal decomposition is k, we show how to find a decomposition of cost k^O(1) in time f(k)*n^O(1). Secondly, we exploit the constructed decompositions for solving vertex-deletion problems under the new parameterizations.
Joint work with Bart M. P. Jansen and Jari J. H. de Kroon.
Date: 2nd March, 2021
Speaker: Sanjukta Roy
Postdoctoral Fellow
TU Wien, Vienna.
Title of the talk: Gerrymandering on graphs: Computational complexity and parameterized algorithms. (slides)
Abstract: Partitioning a region into districts to favor a particular candidate or a party is commonly known as gerrymandering. In this paper, we investigate the gerrymandering problem in graph theoretic setting as proposed by Cohen-Zemach et al. [AAMAS 2018]. Our contribution is two-fold, conceptual and computational. We first resolve the open question posed by Ito et al. [AAMAS 2019] about the computational complexity of the problem when the input graph is a path. Next, we propose a generalization of their model.
The problem is known to be NPC even if k=2, m=2, and G is either a complete bipartite graph (in fact K_{2,n}) or a complete graph. This means that in search for FPT algorithms we need to either focus on the parameter n, or subclasses of forest. Circumventing these intractable results, we give a deterministic and a randomized algorithms for the problem on paths running in times 2.619^k (n+m)^{O(1)} and 2^k (n+m)^{O(1)}, respectively. Additionally, we prove that the problem on general graphs is solvable in time 2^n (n+m)^{O(1)}. Our algorithmic results use sophisticated technical tools such as representative set family and Fast Fourier transform based polynomial multiplication, and their (possibly first) application to problems arising in social choice theory and/or game theory may be of independent interest to the community.
This is a joint work with Sushmita Gupta, Pallavi Jain, Fahad Panolan, and Saket Saurabh.
Date: 23rd February, 2021
Speaker: Pallavi Jain
Assistant Professor
Indian Institute of Technology Jodhpur, Jodhpur.
Title of the talk: Committee Selection Problem: Recent Advancements. (slides)
Abstract: The committee selection problem is a problem in social choice theory in which voter's preferences or votes over the candidates need to be aggregated to choose a committee. There are many rules in the literature to aggregate these preferences. Most of the rules are NP-hard and have been studied in the realm of parameterized complexity. In this talk, we will briefly discuss some voting rules and also some recent advancements in this field, both from conceptual as well as algorithmic point of view.
Date: 16th February, 2021
Speaker: Petr Golovach
Research Professor
University of Bergen.
Title of the talk: Parameterized Enumeration Kernels with Applications to Matching Cut Enumeration. (slides)
Abstract: An enumeration kernel as defined by Creignou et al. [Theory Comput. Syst. 2017] for a parameterized enumeration problem consists of an algorithm that transforms each instance into one whose size is bounded by the parameter plus a solution-lifting algorithm that efficiently enumerates all solutions from the set of the solutions of the kernel. We propose to consider two new versions of enumeration kernels by asking that the solutions of the original instance can be enumerated in polynomial time or with polynomial delay from the kernel solutions. Using the NP-hard Matching Cut problem parameterized by structural parameters such as the vertex cover number or the cyclomatic number of the input graph, we show that the new enumeration kernels present a useful notion of data reduction for enumeration problems which allows to compactly represent the set of feasible solutions.
This is joint work with Christian Komusiewicz, Dieter Kratsch, and Van Bang Le.
Date: 9th February, 2021
Speaker: Danil Sagunov
PhD Student
Steklov Institute of Mathematics, St. Petersburg.
Title of the talk: Algorithmic Extensions of Dirac's Theorem. (slides)
Abstract: The Dirac's Theorem states that every n-vertex 2-connected graph contains a cycle twice as long as its minimum degree. This bound is tight and the corresponding cycle can be found in polynomial time following Dirac's original proof. Moreover, the problem of finding a cycle whose length is at least (2+eps) times minimum degree is NP-hard for any constant eps>0. We study the problem of finding a cycle slightly longer than the bound of the Dirac's theorem in a 2-connected graph, i.e. a cycle of length at least twice its minimum degree plus k. Using several known and new methods and constructions, we show that this problem is solvable in FPT time with single-exponential dependence on k. Interestingly, for obtaining such an algorithm, we design algorithms for several related parameterized problems. Prior to this work, parameterized complexity of some of them was questioned and remained unresolved in the literature. Apart from that, the proof builds on a new graph-theoretical result that is interesting on its own.
In this talk, we will discuss the main points of the central result of this work, its main constructions and ideas, and directions of the future research.
This is joint work with Fedor V. Fomin, Petr A. Golovach, and Kirill Simonov.
Date: 2nd February, 2021
Speaker: Fedor Fomin
Professor
University of Bergen.
Title of the talk: Paths, Cycles, and Beyond. (slides)
Abstract: This talk will be about old and new parameterized algorithms for finding long paths and cycles in graphs. In particular, we discuss problems of finding paths and cycles whose lengths are beyond some “trivial” bounds.
Date: 26th January, 2021
Speaker: Łukasz Bożyk
PhD Student
University of Warsaw.
Title of the talk: Vertex deletion into bipartite permutation graphs. (slides)
Abstract: A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines, one on each. A bipartite permutation graph is a permutation graph which is bipartite. We study the parameterized complexity of the bipartite permutation vertex deletion problem, which asks, for a given n-vertex graph, whether we can remove at most k vertices to obtain a bipartite permutation graph. This problem is NP-complete by the classical result of Lewis and Yannakakis. We analyze the structure of the so-called almost bipartite permutation graphs which may contain holes (large induced cycles) in contrast to bipartite permutation graphs and exploit the structural properties of the shortest hole in such graphs. We use it to obtain an algorithm for the bipartite permutation vertex deletion problem with running time O(9^k⋅n^9), and also give a polynomial-time 9-approximation algorithm.
Joint work with Jan Derbisz, Tomasz Krawczyk, Jana Novotná, and Karolina Okrasa.
Date: 19th January, 2021
Speaker: Marcin Pilipczuk
Assistant Professor
University of Warsaw.
Title of the talk: Solving hard cut problems via flow augmentation. (slides)
Abstract: We present a new technique for designing FPT algorithms for graph cut problems in undirected graphs, which we call flow augmentation. Our technique is applicable to problems that can be phrased as a search for an (edge) (s,t)-cut of cardinality at most k in an undirected graph G with designated terminals s and t.
More precisely, we consider problems where an (unknown) solution is a set Z⊆E(G) of size at most k such that (1) in G−Z, s and t are in distinct connected components, (2) every edge of Z connects two distinct connected components of G−Z, and (3) if we define the set Z_{s,t}⊆Z as these edges e∈Z for which there exists an (s,t)-path P_e with E(P_e)∩Z={e}, then Z_{s,t} separates s from t. We prove that in this scenario one can in randomized time k^{O(1)}(|V(G)|+|E(G)|) add a number of edges to the graph so that with 2^{−O(k log k)} probability no added edge connects two components of G−Z and Z_{s,t} becomes a minimum cut between s and t.
We apply our method to obtain a randomized FPT algorithm for a notorious "hard nut" graph cut problem we call Coupled Min-Cut. This problem emerges out of the study of FPT algorithms for Min CSP problems, and was unamenable to other techniques for parameterized algorithms in graph cut problems, such as Randomized Contractions, Treewidth Reduction or Shadow Removal.
To demonstrate the power of the approach, we consider more generally Min SAT(Γ), parameterized by the solution cost. We show that every problem Min SAT(Γ) is either (1) FPT, (2) W[1]-hard, or (3) able to express the soft constraint (u→v), and thereby also the min-cut problem in directed graphs. All the W[1]-hard cases were known or immediate, and the main new result is an FPT algorithm for a generalization of Coupled Min-Cut.
Joint work with Eun Jung Kim, Stefan Kratsch, and Magnus Wahlström.
Date: 8th December, 2020
Speaker: Amer Mouawad
Assistant Professor
American University of Beirut.
Title of the talk: On girth and the parameterized complexity of token sliding and token jumping (slides)
Abstract: In the token jumping problem we are given a graph G and two independent sets S and T of G, each of size k > 0. If we view each independent set as a collection of tokens placed on a subset of the vertices of G, then the token jumping problem asks for a sequence of independent sets which transforms S to T by individual token jumps which maintain the independence of the sets. This problem is known to be PSPACE-complete on very restricted graph classes, e.g., planar bounded-degree graphs and graphs of bounded pathwidth. A closely related problem is the token sliding problem, where instead of allowing a token to jump to any vertex of the graph we require that a token slides along an edge of the graph. Token sliding is also known to be PSPACE-complete on the aforementioned graph classes. In this talk, we investigate the parameterized complexity of both problems on several graph classes, focusing on the effect of excluding certain cycles from the input graph.
Joint work with Valentin Bartier, Nicolas Bousquet, Clement Dallard, and Kyle Lomer.
Date: 1st December, 2020
Speaker: Saket Saurabh
Professor,
Institute of Mathematical Sciences, Chennai & University of Bergen, Norway.
Title of the talk: FPT Approximation for FPT Problems (slides)
Abstract: In this talk we will see FPT approximation for some well known problems such as Directed Feedback Vertex Set and Multicut. In particular, we will give factor 2 approximation for these problems running in time c^k poly( n).
Date: 24th November, 2020
Speaker: Prafullkumar Tale
Postdoctoral Fellow
CISPA Helmholtz Center for Information Security, Saarbrücken.
Title of the talk: On the Parameterized Approximability of Contraction to Classes of Chordal Graphs (slides)
Abstract: Parameterized Complexity of editing to a family of graphs by contracting k edges has recently gained substantial scientific attention, and several new results have been obtained. Some important families of graphs, namely the subfamilies of chordal graphs, in the context of edge contractions, have proven to be significantly more difficult than one might expect. In this work, we study the F-Contraction problem, where F is a subfamily of chordal graphs, in the realm of parameterized approximation. More specifically, we obtain parameterized approximation results about Clique Contraction, Split Contraction, and Chordal Contraction. We find it interesting that three closely related problems have different behavior with respect to FPT-approximation.
This is a joint work with Spoorthy Gunda, Pallavi Jain, Daniel Lokshtanov and Saket Saurabh.
Date: 17th November, 2020
Speaker: Daniel Lokshtanov
Associate Professor
University of California Santa Barbara.
Title of the talk: Independent Set on P_k-Free Graphs in Quasi-Polynomial time, and Beyond (slides)
Abstract: We present an algorithm that takes as input a graph G with weights on the vertices, and computes a maximum weight independent set S of G. If the input graph G excludes a path P_k on k vertices as an induced subgraph, the algorithm runs in quasi-polynomial time. Hence, for every fixed k our algorithm runs in quasi-polynomial time. In fact, our algorithm can be generalized to output a maximum weight induced subgraph of bounded treewidth satisfying some MSO properties. This resolved several open questions in the area that have been around for a couple of decades.
Date: 10th November, 2020
Speaker: Diptapriyo Majumdar
Postdoctoral Research Assistant
Royal Holloway, University of London.
Title of the talk: p-Edge/Vertex-Connected Vertex Cover: Parameterized and Approximation Algorithms (slides)
Abstract: We introduce two natural generalizations of Connected Vertex Cover problem: p-Edge-Connected Vertex Cover and p-Vertex-Connected Vertex Cover where p >= 2 is a fixed integer. Similar to the Connected Vertex Cover problem, both are FPT by an O*(2^{O(k^2)})-time algorithm, but do not admit polynomial kernels unless NP \subseteq coNP/poly. But, we prove that we can do better for p-Edge-Connected Vertex Cover by providing an O*(2^{O(pk)})-time FPT algorithm by using dynamic programming over representative sets. In addition, we prove that for every fixed 0 < epsilon < 1, both the problems admit (1 + epsilon)-approximate kernels of polynomial size. We use the existence of p-edge/vertex-connected spanning subgraph for our approximate kernel results. Finally, we provide a polynomial time 2(p+1)-factor approximation algorithm for p-Edge-Connected Vertex Cover problem.
This is based on a joint work with Carl Einarson, Gregory Gutin, Bart Jansen, and Magnus Wahlstrom.
Date: 3rd November, 2020
Speaker: Ashwin Jacob
PhD Student
Institute of Mathematical Sciences, Chennai.
Title: Parameterized Complexity of Deletion to Scattered Graph Classes (slides)
Abstract: Graph-modification problems, where we add/delete a small number of vertices/edges to make the given graph to belong to a simpler graph class, is a well-studied optimization problem in all algorithmic paradigms including classical, approximation and parameterized complexity. Specifically, graph-deletion problems, where one needs to delete at most $k$ vertices to place it in a given non-trivial hereditary (closed under induced subgraphs) graph class, captures several well-studied problems including VERTEX COVER, FEEDBACK VERTEX SET, ODD CYCLE TRANSVERSAL, CLUSTER VERTEX DELETION AND CHORDAL VERTEX DELETION.
In this paper, we initiate a study of a natural variation of the problem of deletion to scattered graph classes where we need to delete at most $k$ vertices so that in the resulting graph, each connected component belongs to one of a constant number of graph classes. A simple hitting set based approach is no longer feasible even if each of the graph classes is characterized by finite forbidden sets. As our main result, we show that this problem (in the case where each graph class has a finite forbidden set) is fixed-parameter tractable by a $O^*(2^{k^{\OO(1)}})$ algorithm.
In the simpler case when there are two graph classes with finite forbidden sets to get to, and if one of the forbidden sets has a path, then we show that the problem has a singly exponential algorithm and a polynomial sized kernel. We also design an efficient FPT algorithm for the special case when one of the graph classes has an infinite forbidden set. Specifically, we give a $O^*(4^k)$ algorithm to determine whether $k$ vertices can be deleted from a given graph so that in the resulting graph, each connected component is a tree (sparsest connected graph) or a clique (the densest connected graph).
Date: 27th October, 2020
Speaker: Gopinath Mishra
PhD Student
Indian Statistical Institute, Kolkata.
Title: Parameterized Query Complexity of Hitting Set Using Stability of Sunflowers (slides)
Abstract: In this paper, we show the existence of an optimal fixed parameter tractable algorithm for the $d$-Hitting-Set problem with a subset query oracle access. We consider both the parameterized decision and optimization versions of the $d$-Hitting-Set problem. More specifically, the GPIS oracle access, introduced by Dell et al.[SODA’20] and Bishnu et al.[ArXiv’19], that we consider, is a generalization to hypergraphs of an oracle known as BIS (Bipartite Independent Set) introduced by Beame et al.[ITCS’19 and TALG’20]. The query oracle considered is as follows: GPIS oracle takes as an input $d$ pairwise disjoint non-empty subsets $A_1, \ldots, A_d$ of vertices in a hypergraph $\mathcal{H}$ and answers whether there is a hyperedge in $\mathcal{H}$ with exactly one vertex in each set $A_i$, where $i \in [d]$. For $d=2$, the GPIS oracle is nothing but BIS. We use color coding and queries to the oracles to generate subsamples from the hypergraph, that retain some structural properties of the original hypergraph. We use the stability of the sunflowers in a non-trivial way to do so. We also show via a matching lower bound that our FPT algorithm is tight. Apart from the results on $d$-Hitting-Set which is our main focus, we also study the query complexity of the parameterized decision and optimization versions of $d$-Packing in hypergraphs and Max-Cut in graphs.
This is joint work with Arijit Bishnu, Arijit Ghosh, Sudeshna Kolay, Gopinath Mishra, Saket Saurabh.
Date: 20th October, 2020
Speaker: Roohani Sharma
Postdoctoral Fellow
Max Planck Institute for Informatics, Saarbrücken.
Title of the talk: Quick Separation in Chordal and Split Graphs (slides)
Abstract: We study two classical cut problems, namely MULTICUT and MULTIWAY CUT on chordal graphs and split graphs. In the MULTICUT problem, the input is a graph G, a collection of p terminal pairs (s_i, t_i), i \in {1,...,p}, and a positive integer k and the goal is to decide if there exists a vertex subset S of size at most k that does not pick the vertices from the terminal pairs such that for every vertex pair (s_i,t_i), s_i and t_i are in two different connected components of G-S. In UNRESTRICTED MULTICUT, the solution S can possibly pick the vertices in the terminal pairs. An important special case of the MULTICUT problem is the MULTIWAY CUT problem, where instead of terminal pairs, one is given a set T of terminal vertices, and the goal is to separate every pair of distinct vertices in T \times T.
The fixed parameter tractability of these problems was a long-standing open problem and has been resolved fairly recently. MULTICUT and MULTIWAY CUT now admit algorithms with running times 2^{O(k^3)} n^{O(1)} and 2^k n^{O(1)}, respectively, where n is the number of vertices in the input graph. However, the kernelization complexity of both these problems is not fully resolved: while MULTICUT cannot admit a polynomial kernel when the parameter is k, under reasonable complexity assumptions, it is a well known open problem to construct a polynomial kernel for MULTIWAY CUT parameterized by k. On the other hand, in a breakthrough paper [J. ACM 2020], it was shown that the problems admit randomized kernels of size O(k^{p+1}) and O(k^{|\sqrt{2p}| +1}) respectively. Towards designing faster FPT algorithms and better polynomial kernels for the above mentioned problems, we study them on chordal and split graphs. In particular we obtain the following results.
(1) MULTICUT on chordal graphs admits a polynomial kernel with O(k^3 p^7) vertices.
(2) MULTIWAY CUT on chordal graphs admits a polynomial kernel with O(k^{13}) vertices.
(3) MULTICUT on chordal graphs can be solved in time min {O(2^{k} . (k^3+p) . (n+m)), 2^{O(p log k)} . (n+m) + p (n+m)}, where n and m are the number of vertices and edges in the input graph. Hence, MULTICUT on chordal graphs parameterized by the number of terminals is in XP.
(4) MULTICUT on split graphs can be solved in time min {O(1.2738^k + kn+p(n+m), O(2^p . p . (n+m))}.
(5) UNRESTRICTED MULTICUT on split graphs can be solved in time O(4^p . p . (n+m)).
Date: 13th October, 2020
Speaker: Pratibha Choudhary
PhD Student,
Indian Institute of Technology Jodhpur, Jodhpur.
Title of the talk: Tracking Paths: A Quadratic Kernel (slides)
Abstract: Given a graph G, terminal vertices s and t, and an integer k, the TRACKING PATHS problem asks if there exists at most k vertices in G, which if marked as trackers would ensure that a unique sequence of trackers is encountered in each s-t path. One restricted version of the problem is where we aim to distinguish between only the shortest s-t paths in a graph. Both TRACKING PATHS and TRACKING SHORTEST PATHS are known to be NP-hard. Further, both these problems are known to admit FPT algorithms as shown in recent work. In this talk we improve upon the known FPT result for TRACKING PATHS by showing the existence of a quadratic kernel i.e. O(k^2), where k is the size of the desired tracking set. This is done by studying some specific subgraph structures, and showing a lower bound for the number of trackers required in these subgraphs, if they are found to be existing in the input graph.
This is joint work with Venkatesh Raman.
Date: 6th October, 2020
Speaker: Sujoy Bhore
Postdoctoral Fellow,
Université libre de Bruxelles (ULB), Belgium.
Title of the talk: Parameterized Study of Steiner Tree on Unit Disk Graphs (slides)
Abstract: In this talk, we are interested in the Steiner tree problem on unit disk graphs. Given a $n$ vertex unit disk graph $G$, a subset $R\subseteq V(G)$ of $t$ vertices and a positive integer $k$, the objective is to decide if there exists a tree $T$ in $G$ that spans over all vertices of $R$ and uses at most $k$ vertices from $V\setminus R$. The vertices of $R$ are referred to as terminals and the vertices of $V(G)\setminus R$ as Steiner vertices. First, we show that the problem is NP-hard. Next, we prove that the Steiner tree problem on unit disk graphs can be solved in $n^{O(\sqrt{t+k})}$ time. We also show that the Steiner tree problem on unit disk graphs parameterized by $k$ has an FPT algorithm with running time $2^{O(k)}n^{O(1)}$. In fact, the algorithms are designed for a more general class of graphs, called clique-grid graphs [Fomin et al., DCG'19]. We mention that the algorithmic results can be made to work for the Steiner tree problem on disk graphs with bounded aspect ratio. Finally, we prove that the Steiner tree problem on disk graphs parameterized by $k$ is W[1]-hard.
This is joint work with Paz Carmi, Sudeshna Kolay, Meirav Zehavi.
Date: 29th September, 2020
Speaker: Neeldhara Misra
Assistant Professor,
Indian Institute of Technology Gandhinagar, Gandhinagar.
Title of the talk: On the complexity of Winner Verification and Candidate Winner for Multiwinner Voting Rules
Abstract: The Chamberlin-Courant and Monroe rules are fundamental and well-studied rules in the literature of multi-winner elections. The problem of determining if there exists a committee of size k that has a Chamberlin-Courant (respectively, Monroe) dissatisfaction score of at most r is known to be NP-complete. In this talk, we will survey some results known about the complexity of winner determination for these rules with a special emphasis on parameterized approaches. Then, we will also consider the following natural problems: a) given a committee S of size k as input, is it an optimal k-sized committee?, and b) given a candidate c and a committee size k, does there exist an optimal k-sized committee that contains c? We will explore some recent progress on these questions as well.
A part of what will be presented in this talk is based on joint work with Chinmay Sonar and Palash Dey and appeared in IJCAI 2020.
Date: 22nd September, 2020
Speaker: Fahad Panolan
Assistant Professor,
Indian Institute of Technology Hyderabad, Hyderabad.
Title of the talk: Hitting topological minors is FPT (slides)
Abstract: In the Topological Minor Deletion (TM-Deletion) problem, the input consists of an undirected graph G, a family of undirected graphs F, and an integer k. The task is to determine whether G contains a set S of vertices of size at most k, such that the graph G-S contains no graph from F as a topological minor. We give an algorithm for TM-Deletion with running time f(h,k) poly(|V(G)|), where h is the maximum size of a graph in F, and f is a computable function of h and k. This is the first fixed-parameter tractable algorithm (FPT) for the problem.
This is joint work with Fedor V. Fomin, Daniel Lokshtanov, Saker Saurabh, and Meirav Zehavi.
Date: 14th September, 2020
Speaker: Pranabendu Misra
Postdoctoral Fellow
Max Planck Institute for Informatics, Saarbrucken.
Title of the talk: On the Complexity of Recovering Incidence Matrices (slides)
Abstract: The incidence matrix of a graph is a fundamental object naturally appearing in many applications, involving graphs such as social networks, communication networks, or transportation networks. Often, the data collected about the incidence relations can have some slight noise. In this paper, we initiate the study of the computational complexity of recovering incidence matrices of graphs from a binary matrix: given a binary matrix $M$ which can be written as the superposition of two binary matrices $L$ and $S$, where $S$ is the incidence matrix of a graph from a specified graph class, and $L$ is a matrix $(i)$ of small rank or, $(ii)$ of small (Hamming) weight. Further, identify all those graphs whose incidence matrices form part of such a superposition. Here, $L$ represents the noise in the input matrix $M$. Another motivation for this problem comes from the Matroid Minors project of Geelen, Gerards and Whittle, where perturbed graphic and co-graphic matroids play a prominent role. There, it is expected that a perturbed binary matroid (or its dual) is presented as $L+S$ where $L$ is a low rank matrix and $S$ is the incidence matrix of a graph. Here, we address the complexity of constructing such a decomposition.
When $L$ is of small rank, we show that the problem is {\sf NP}-complete, but it can be decided in time $(mn)^{O(r)}$, where $m,n$ are dimensions of $M$ and $r$ is an upper-bound on the rank of $L$. When $L$ is of small weight, then the problem is solvable in polynomial time $(mn)^{O(1)}$. Furthermore, in many applications it is desirable to have the list of all possible solutions for further analysis. We show that our algorithms naturally extend to enumeration algorithms for the above two problems with delay $(mn)^{O(r)}$ and $(mn)^{O(1)}$, respectively, between consecutive outputs.
Date: 7th September, 2020
Speaker: Michael Lampis
Assistant Professor,
LAMSADE, Université Paris Dauphine, Paris.
Title of the talk: Grundy Distinguishes Treewidth from Pathwidth (slides)
Abstract: In this talk we are interested in the "price of generality" associated with the transition from pathwidth to treewidth. Recall that graphs of treewidth at most k form a strict superset of graphs of pathwidth at most k. As a result, it is natural to expect some problems which are tractable parameterized by pathwidth to become intractable parameterized by treewidth (this is the "price" of the added generality of treewidth). Which are these problems? So far, the same question has been posed for many other pairs of prominent structural parameters, such as treewidth vs. clique-width, pathwidth vs. tree-depth, and tree-depth vs. vertex cover. For each such pair, several natural problems are known which give examples of this complexity transition. The only exception is, to the best of our knowledge, the transition from pathwidth to treewidth, where essentially all known problem seem to have the same complexity for both parameters. Our main goal in this talk is to give the first natural example of a problem that is FPT parameterized by pathwidth but W[1]-hard parameterized by treewidth. This problem is Grundy Coloring, the problem of ordering the vertices of a graph in a way that maximizes the number of colors used by the greedy First-Fit Coloring heuristic.
Joint work with Rémy Belmonte, Eun Jung Kim, Valia Mitsou, and Yota Otachi, to appear in ESA 2020. Full version available at https://arxiv.org/abs/2008.07425
Date: 31st August, 2020
Speaker: Vibha Sahlot
Postdoctoral Researcher,
Institute of Mathematical Sciences, Chennai.
Title of the talk: Structural Parameterizations with Modulator Oblivion (slides)
Abstract: It is known that Vertex Cover is polynomial time solvable in the class of chordal graphs. We consider this problem in a graph that has at most $k$ vertices whose deletion results in a chordal graph, when parameterized by $k$. While this investigation fits naturally into the recent trend of what are called 'structural parameterizations', here we assume that the deletion set is not given.
One method to solve them is to compute a $k$-sized or an approximate ($f(k)$ sized, for a function $f$) chordal vertex deletion set and then use the structural properties of the graph to design an algorithm. This method leads to at least $k^{O(k)}.n^{O(1)}$ running time when we use the known parameterized or approximation algorithms for finding a $k$-sized chordal deletion set on an $n$ vertex graph.
However in this talk, we will see a $2^{O(k)}n^{O(1)}$ time algorithm for Vertex Cover parameterized by the size of chordal vertex deletion set when the chordal deletion set is not given as a part of the input.
Date: 24th August, 2020
Speaker: Christophe Paul
Researcher (directeur de recherche, DR1) at the CNRS,
Centre National de la Recherche Scientifique, LIRMM, Montpellier.
Title of the talk: A linear fixed parameter tractable algorithm for connected pathwidth. (slides)
Abstract: The graph parameter of pathwidth can be seen as a measure of the topological resemblance of a graph to a path. A popular definition of pathwidth is given in terms of node search where we are given a system of tunnels (represented by a graph) that is contaminated by some infectious substance and we are looking for a search strategy that, at each step, either places a searcher on a vertex or removes a searcher from a vertex and where an edge is cleaned when both endpoints are simultaneously occupied by searchers. It was proved that the minimum number of searchers required for a successful cleaning strategy is equal to the pathwidth of the graph plus one. Two desired characteristics for a cleaning strategy is to be monotone (no recontamination occurs) and connected (clean territories always remain connected). Under these two demands, the number of searchers is equivalent to a variant of pathwidth called connected pathwidth. We prove that connected pathwidth is fixed parameter tractable, in particular we design a 2^{O(k^2)}·n time algorithm that checks whether the connected pathwidth of G is at most k. This resolves an open question by [Dereniowski, Osula, and Rzążewski, Finding small-width connected path decompositions in polynomial time. Theor. Comput. Sci., 794:85–100, 2019 ]. For our algorithm, we enrich the typical sequence technique that is able to deal with the connectivity demand. Typical sequences have been introduced in [Bodlaender and Kloks. Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms, 21(2):358–402, 1996 ] for the design of linear parameterized algorithms for treewidth and pathwidth. While this technique has been later applied to other parameters, none of its advancements was able to deal with the connectivity demand, as it is a “global” demand that concerns an unbounded number of parts of the graph of unbounded size. The proposed extension is based on an encoding of the connectivity property that is quite versatile and may be adapted so to deliver linear parameterized algorithms for the connected variants of other width parameters as well. An immediate consequence of our result is a 2^{O(k^2)}·n time algorithm for the monotone and connected version of the edge search number.
Date: 17th August, 2020
Speaker: Saket Saurabh
Professor,
Institute of Mathematical Sciences, Chennai & University of Bergen, Norway.
Title of the talk: Picking Random Vertices. (slides)
Abstract: We survey some recent graph algorithms that are based on picking a vertex at random and declaring it to be a part of the solution. This simple idea has been deployed to obtain state-of-the-art parameterized, exact exponential time, and approximation algorithms for a number of problems, such as Feedback Vertex Set and 3-Hitting Set. We will also discuss a recent 2-approximation algorithm for Feedback Vertex Set in Tournaments that is based on picking a vertex at random and declaring it to /not/ be part of the solution.
Date: 10th August, 2020
Speaker: Meirav Zehavi
Assistant Professor,
Ben-Gurion University of the Negev, Israel.
Title of the talk: Parameterized Analysis, Graph Minors and Planar Disjoint Paths. (slides)
Abstract: Parameterized Analysis leads both to deeper understanding of intractability results and to practical solutions for many NP-hard problems. Informally speaking, Parameterized Analysis is a mathematical paradigm to answer the following fundamental question: What makes an NP-hard problem hard? Specifically, how do different parameters (being formal quantifications of structure) of an NP-hard problem relate to its inherent difficulty? Can we exploit these relations algorithmically, and to which extent? Over the past three decades, Parameterized Analysis has grown to be a mature field of outstandingly broad scope with significant impact from both theoretical and practical perspectives on computation.
In this talk, I will first give a brief introduction of the field of Parameterized Analysis and to the Graph Minors theory as its origin. Additionally, I will zoom into a specific result, namely, the first single-exponential time parameterized algorithm for the Disjoint Paths problem on planar graphs. An efficient algorithm for the Disjoint Paths problem in general, and on "almost planar" graphs in particular, is a critical part in the quest for the establishment of an Efficient Graph Minors Theory. As the Graph Minors Theory is the origin of Parameterized Analysis and ubiquitous in the design of parameterized algorithms, making this theory efficient is a holy grail in the field.
Date: 3rd August, 2020
Speaker: Philipp Zschoche
PhD Student,
TU Berlin, Germany.
Title of the talk: Computing Maximum Matchings in Temporal Graphs. (slides)
Abstract: Temporal graphs are graphs whose topology is subject to discrete changes over time. Given a static underlying graph G, a temporal graph is represented by assigning a set of integer time-labels to every edge e of G, indicating the discrete time steps at which e is active. We introduce and study the computational complexity of a natural temporal extension of the classical graph problem Matching, taking into account the dynamic nature of temporal graphs. In our problem, Temporal Matching, we are looking for k time-labeled edges (simply time edges) (e,t) such that no vertex is matched more than once within any time window of ∆ consecutive time slots, where the natural number ∆ is given. In this talk, we first show that Temporal Matching is NP-hard even if G is a path and ∆=2. Then, we show that Temporal Matching is fixed-parameter tractable when parameterized by k, or the combined parameter ∆ and the vertex cover number of G.
This is based on joint work with George B. Mertzios, Hendrik Molter, Rolf Niedermeier, and Viktor Zamaraev.
Date: 27th July, 2020
Speaker: Mathieu Mari
PhD Student,
École Normale Supérieure, Paris.
Title of the talk: Fixed-parameter algorithms for Unsplittable Flow Cover. (slides)
Abstract: The Unsplittable Flow Cover problem (UFP-cover) models the well-studied general caching problem and various natural resource allocation settings.
We are given a path with a demand on each edge and a set of tasks, each task being defined by a subpath and a size. The goal is to select a subset of the tasks of minimum cardinality such that on each edge e the total size of the selected tasks using e is at least the demand of e.
There is a polynomial time 4-approximation for the problem [Bar- Noy. et al., STOC 2000] and also a QPTAS [Höhn et al., ICALP 2014].
In the talk, I will present fixed-parameter algorithms for the problem.
The problem is W[1]-hard but I will show that it becomes FPT if we can slightly violate the edge demands (resource augmentation) and also if there is a fixed number of different task sizes. Based on these results, I will present a FPT-2-approximation algorithm. The main result of our paper is a parameterized approximation scheme (PAS) for the problem.
In several algorithms we use a new trick that intuitively allows us to pretend that we can select tasks from OPT multiple times.
Date: 20th July, 2020
Speaker: Bart M. P. Jansen
Assistant Professor,
Eindhoven University of Technology, The Netherlands.
Title of the talk: Bridge-Depth Characterizes which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel. (slides)
Abstract: We study the kernelization complexity of structural parameterizations of the Vertex Cover problem. Here, the goal is to find a polynomial-time preprocessing algorithm that can reduce any instance (G,k) of the Vertex Cover problem to an equivalent one, whose size is polynomial in the size of a pre-determined complexity parameter of G. A long line of previous research deals with parameterizations based on the number of vertex deletions needed to reduce G to a member of a simple graph class F, such as forests, graphs of bounded tree-depth, and graphs of maximum degree two. We set out to find the most general graph classes F for which Vertex Cover parameterized by the vertex-deletion distance of the input graph to F, admits a polynomial kernelization. We give a complete characterization of the minor-closed graph families F for which such a kernelization exists. We introduce a new graph parameter called bridge-depth, and prove that a polynomial kernelization exists if and only if F has bounded bridge-depth. The proof is based on an interesting connection between bridge-depth and the size of minimal blocking sets in graphs, which are vertex sets whose removal decreases the independence number.
Date: 13th July, 2020
Speaker: Paloma T. Lima
Postdoctoal Researcher,
University of Bergen, Norway.
Title of the talk: Well-partitioned chordal graphs: obstruction set and disjoint paths. (slides)
Abstract: We introduce a new subclass of chordal graphs that generalizes split graphs, which we call well-partitioned chordal graphs. Split graphs are graphs that admit a partition of the vertex set into cliques that can be arranged in a star structure, the leaves of which are of size one. Well-partitioned chordal graphs are a generalization of this concept in the following two ways. First, the cliques in the partition can be arranged in a tree structure, and second, each clique is of arbitrary size. We provide a characterization of well-partitioned chordal graphs by forbidden induced subgraphs, and give a polynomial-time algorithm that given any graph, either finds an obstruction, or outputs a partition of its vertex set that asserts that the graph is well-partitioned chordal. We demonstrate the algorithmic use of this graph class by showing that two variants of the problem of finding pairwise disjoint paths between k given pairs of vertices is in FPT parameterized by k on well-partitioned chordal graphs, while on chordal graphs, these problems are only known to be in XP. From the other end, we observe that there are problems that are polynomial-time solvable on split graphs, but become NP-complete on well-partitioned chordal graphs.This is joint work with Jungho Ahn, O-joung Kwon and Lars Jaffke.
Date: 06th July, 2020
Speaker: Magnus Wahlström
Professor,
Royal Holloway, University of London.
Title of the talk: On Quasipolynomial multicut-mimicking networks and kernelization of multiway cut problems. (slides)
Abstract: We show the existence of an exact mimicking network of k^{O(log k)} edges for minimum multicuts over a set of terminals in an undirected graph, where k is the total capacity of the terminals. Furthermore, if the Small Set Expansion problem has an approximation algorithm with a ratio slightly better than θ(log n), then a mimicking network of quasipolynomial size can be computed in polynomial time.
As a consequence of the latter, several problems would have quasipolynomial kernels, including Edge Multiway Cut, Group Feedback Edge Set and Subset Feedback Edge Set (in its general formulation, with undeletable edges). In particular, the existence of a polynomial kernel for Multiway Cut is one of the biggest open questions in kernelization, and this result would be the first improvement in general graphs since the introduction of the representative sets approach to kernelization in 2012 (Kratsch and W.).
Date: 29th June, 2020
Speaker: Eduard Eiben
Lecturer,
Royal Holloway, University of London.
Title of the talk: Removing Connected Obstacles in the Plane Is FPT (slides)
Abstract: Given two points in the plane, a set of obstacles defined by closed curves, and an integer $k$, does there exist a path between the two designated points intersecting at most $k$ of the obstacles? This is a fundamental and well-studied problem arising naturally in computational geometry, graph theory, wireless computing, and motion planning. It remains NP-hard even when the obstacles are very simple geometric shapes (e.g., unit-length line segments).
In this talk, we show that the problem is fixed-parameter tractable (FPT) parameterized by $k$, by giving an algorithm with running time $k^{O(k^3)}n^{O(1)}$. Here $n$ is the number connected areas in the plane drawing of all the obstacles.
Date: 22nd June, 2020
Speaker: Ramanujan Sridharan
Assistant Professor,
University of Warwick, England.
Title of the talk: Approximate Kernels for Connected Deletion Problems (slides)
Abstract: One of the most frequently investigated subgraph hitting problems in the literature is the F-Deletion problem which generalises numerous well-studied NP-complete problems. In this problem, F is a fixed finite family of graphs and one is given a graph G and an integer k as input. The objective is to determine whether at most k vertices can be deleted from G so that the resulting graph is F-minor free.
Already when F is as simple as {K_2}, this problem is the same as the classic Connected Vertex Cover problem and hence is NP-hard to approximate below a factor of 2 and does not admit a polynomial kernel under standard hypotheses. Moreover, no non-trivial approximation is known even in the special case of F = {K_3} (Connected Feedback Vertex Set).
In this talk, we will focus on the case F = {K_3} and describe a Polynomial Size Approximate Kernelization Scheme, which is an efficient preprocessing algorithm whose output has size bounded polynomially in a parameter of the input and whose error can be made arbitrarily close to 0. We will then discuss some consequences of this result and subsequent extensions.
Date: 15th June, 2020
Speaker: Astrid Pieterse
Postdoctoral Researcher,
HU Berlin, Germany.
Title of the talk: Approximate Turing Kernelization for Problems Parameterized by Treewidth (slides)
Abstract: We extend the notion of lossy kernelization, introduced by Lokshtanov et al. [STOC 2017], to approximate Turing kernelization. An α-approximate Turing kernel for a parameterized optimization problem is a polynomial-time algorithm that, when given access to an oracle that outputs c-approximate solutions in O(1) time, obtains an α · c-approximate solution to the considered problem, using calls to the oracle of size at most f(k) for some function f that only depends on the parameter. Using this definition, we show that Independent Set parameterized by treewidth ℓ has a (1+ε)- approximate Turing kernel with O( ℓ^2/ε ) vertices, answering an open question posed by Lokshtanov et al. [STOC 2017]. Furthermore, we give (1 + ε)-approximate Turing kernels for the following graph problems parameterized by treewidth: Vertex Cover, Edge Clique Cover, Edge-Disjoint Triangle Packing and Connected Vertex Cover. We generalize the result for Independent Set and Vertex Cover, by showing that all graph problems that we will call friendly admit (1 + ε)-approximate Turing kernels of polynomial size when parameterized by treewidth. We use this to obtain approximate Turing kernels for VertexDisjoint H-packing for connected graphs H, Clique Cover, Feedback Vertex Set and Edge Dominating Set.
Date: 8th June, 2020
Speaker: Akanksha Agrawal
Postdoctoral Researcher,
Ben-Gurion University of the Negev, Israel.
Title of the talk: Guarding Terrains through the Lens of Parameterized Complexity (slides)
Abstract: The Terrain Guarding problem is a well-studied visibility problem in Discrete and Computational Geometry. So far, the understanding of the parameterized complexity of Terrain Guarding has been very limited, and, more generally, exact (exponential-time) algorithms for visibility problem are extremely scarce. In this talk we will look at two results regarding Terrain Guarding, from the viewpoint of parameterized complexity. Both of these results will utilize new and known structural properties of terrains. The first result that we will see is a polynomial kernel for Terrain Guarding, when parameterized by the number of reflex vertices. (A reflex vertex is a vertex of the terrain where the angle is at least 180 degrees.) The next result will be regarding a special version of Terrain Guarding, called Orthogonal Terrain Guarding. We will consider the above problem when parameterized by the number of minima in the input terrain, and obtain a dynamic programming based XP algorithm for it.
If you are interested in attending our talks but not yet on our mailing list, join us by filling this form.
Steering Committee:
Talk Session Tips:
55 minutes talk + Q/A session
Keep you microphone muted if you are not the speaker
Type Question:<your question> in chat if you want to ask something during the talk
If you are interested in giving a talk on parameterized complexity or on fields around parameterized complexity such as graph theory, approximation algorithms etc. that could be useful in FPT-approximation or other PC related things, please fill this form and we will get in touch with you.