

Abstracts of talksRémy Belmonte: New Results on Directed Edge Dominating Set We study a family of generalizations of Edge Dominating Set on directed graphs called Directed (p,q)Edge Dominating Set. In this problem an arc (u,v) is said to dominate itself, as well as all arcs which are at distance at most q from v, or at distance at most p to u. First, we give significantly improved FPT algorithms for the two most important cases of the problem, (0,1)dEDS and (1,1)dEDS (that correspond to versions of Dominating Seton line graphs), as well as polynomial kernels. We also improve the bestknown approximation for these cases from logarithmic to constant. In addition, we show that (p,q)dEDS is FPT parameterized by p+q+tw, but Whard parameterized just by tw, where tw is the treewidth of the underlying graph of the input. We then go on to focus on the complexity of the problem on tournaments. Here, we provide a complete classification for every possible fixed value of p,q, which shows that the problem exhibits a surprising behavior, including cases which are in P; cases which are solvable in quasipolynomial time but not in P; and a single case (p=q=1) which is NPhard (under randomized reductions) and cannot be solved in subexponential time, under standard assumptions. Joint work with: Tesshu Hanaka, Ioannis Katsikarelis, Eun Jung Kim, and Michael Lampis Julien Baste: Composing dynamic programming treedecompositionbased algorithms Given two integers ℓ and p as well as $ℓ$ graph classes $H_{1}, . . . ,H_{ℓ}$, the problems GraphPart(H_{1}, . . . ,H_{ℓ}, p),VertPart(H_{1}, . . . ,H_{ℓ}), and EdgePart(H_{1}, . . . ,H_{ℓ}) ask, given graph G as input, whetherV(G), E(G) respectively can be partitioned into ℓ sets S_{1}, . . . , S_{ℓ }such that, for eachibetween 1 and ℓ, G[V_{i}]∈ H_{i},G[V_{i}]∈ H_{i}, (V(G), S_{i})∈ H_{i }respectively. Moreover in GraphPart(H_{1}, . . . ,H_{ℓ}, p), we request that the number of edges with endpoints in different sets of the partition is bounded by p. We show that if there exist dynamic programming treedecompositionbased algorithms for recognizing the graph classes H_{i}, for each i, then we can constructively create a dynamic programming treedecompositionbased algorithms for GraphPart(H_{1}, . . . ,H_{ℓ}, p),VertPart(H_{1}, . . . ,H_{ℓ}), and EdgePart(H_{1}, . . . ,H_{ℓ}). We show that, in some known cases, the obtained running times are comparable to those ofthe best know algorithms. Stéphane Bessy: Triangle packing in (sparse) tournaments: approximation and kernelization Given a tournament T and a positive integer k, the C_{3}PakcingT problem asks if there exists a least k (vertex) disjoint directed 3cycles in T. This is the dual problem in tournaments of the classical minimal feedback vertex set problem. Surprisingly C_{3}PakcingT did not receive a lot of attention in the literature. We show that it does not admit a PTAS unless P=NP, even if we restrict the considered instances to sparse tournaments, that is tournaments with a feedback arc set (FAS) being a matching. Focusing on sparse tournaments we provide a (1+6/(c1)) approximation algorithm for sparse tournaments having a linear representation where all the backward arcs have "length" at least c. Concerning kernelization, we show that C_{3}PakcingT admits a kernel with O(m) vertices, where m is the size of a given feedback arc set. In particular, we derive a O(k) vertices kernel for C_{3}PackingT when restricted to sparse instances. On the negative size, we show that C_{3}PakcingT does not admit a kernel of (total bit) size O(k^{2ε}) unless NP is a subset of coNP/Poly. The existence of a kernel in O(k) vertices for C_{3}PakcingT remains an open question. Joint work with: Stéphane Bessy, Marin Bougeret, and Jocelyn Thiebaut Aniket Basu Roy: Approximating robust bin packing with budgeted uncertainty We consider robust variants of the binpacking problem where the sizes of the items can take any value in a given uncertainty set U ⊆ ×ni=1 [ai , ai + âi ], where a ∈ [0, 1]n represents the nominal sizes of the items and â∈ [0, 1]n their possible deviations. We consider more specifically two uncertainty sets previously studied in the literature. The first set, denoted U Γ , contains scenarios in which at most Γ ∈ N items deviate, each of them reaching its peak value ai + âi, while each other item has its nominal value ai. The second set, denoted UΩ, bounds by Ω ∈ [0, 1] the total amount of deviation in each scenario. We show that a variant of the nextfit algorithm provides a 2approximation for model UΩ, and a 2(Γ+1)approximation for model UΓ (which can be improved to 2approximation for Γ=1). This motivates the question of the existence of a constant ratio approximation algorithm for the UΓ model. Our main result is to answer positively to this question by providing a 4.5 approximation for UΓ model based on dynamic programming. Joint work with: Marin Bougeret, Noam Goldberg, and Michael Poss Marin Bougeret: Width Parameterizations for Knotfree Vertex Deletion on Digraphs
Michael Fellows: An Interesting Gap Between Upper and Lower Bounds in the Proliferation of As there should be, given the spectacular success of the almost universally (and somewhat mysteriously) relevant structural parameter treewidth, there has been a notable proliferation of structural width metrics, for graphs and for other mathematical objects, often interpreted into graphs or other elemental logical relational structures. Then the natural parameterized complexity issue arises of whether "w(X) ≤ k?" is FPT. Positive upper bounds (FPT!) usually proceed by proving something very much stronger: that the question is finitestate. The gold standard in lower bounds is to prove M[1] or W[1] hardness, which is known in some cases, such as GRAPH BANDWIDTH, but can require heroic gadgeteering. In many cases the weaker, but by the above discussion, still quite quite relevant, lower bound: that the parameterized width question is not finitestate, is available by much simpler MyhillNerode argumentation, which still does require some gadgets  which can provide insights into the more complicated gadgetry required to prove gold standard lower bounds. Fedor Fomin: Longest Path above guarantee We discuss parameterized algorithms ``above guarantee’’ for finding a long path in a graph. We talk first about the detour problem (is there a path between two vertices whose length is at least k plus the distance between these vertices) and then about algorithmic consequences of the classical theorem of Erdős and Gallai from 1959 about cycles in degenerated graphs. Petr Golovach: On Parameterized Complexity of Graph Modification to FirstOrder Logic Properties We establish new connections between parameterized/kernelization complexity of graph modification problems and expressibility in logic. For a firstorder logic formula φ, we consider the problem of deciding whether an input graph can be modified by removing/adding at most k vertices/edges such that the resulting modification has the property expressible by φ. We provide sufficient and necessary conditions on the structure of the prefix of \phi specifying when the corresponding graph modification problem is fixedparameter tractable (parameterized by k) and when it admits a polynomial kernel. Joint work with: Fedor V. Fomin and Dimitrios M. Thilikos Daniel Gonçalves: 3colorable planar graphs have an intersection segment representation using 3 slopes In his PhD Thesis E.R. Scheinerman conjectured that planar graphs are intersection graphs of segments in the plane. This conjecture was proved with two different approaches. In the case of 3colorable planar graphs E.R. Scheinerman conjectured that it is possible to restrict the set of slopes used by the segments to only 3 slopes. Here we prove this conjecture by using an approach introduced by S. Felsner to deal with contact representations of planar graphs with homothetic triangles. Christophe Paul: A linear time algorithm for fixed connected pathwidth In the classic setting of the node search game, a team of cops is pursuing a robber who occupies the vertices of the graph G and who moves with infinite speed via unguarded paths of G. A node search strategy consists of a series of moves of the cops that are either the removal or the placement of a cop to a vertex of G. A successful search strategy is one that, when deployed, guarantees the capture of the cop, no matter how the cop moves trying to avoid captrure. The cost of a search strategy is the maximum number of cops that are simultaneously on the graph when this strategy is deployed. A search strategy is monotone when at each time of the search the clean territories (i.e., the vertices from which the robber has been expelled) are gradually increasing. Also a search strategy is called connected when, at each time of the search, the clean territories induce a connected subgraph. In this talk we outline an algorithm that, given a graph G and a nonnegative integer k, answers whether there is a successful monotone and connected node search strategy on G of cost at most k, in 2^{O(k^2)} ·n steps. Our algorithm is based on a dynamic programming procedure that uses the characteristic sequence technique, invented by Bodlaender and Kloks for the nonconnected variant of nodesearch. Our algorithm uses a suitable adaptation of this technique that takes into consideration the connectivity demand. The previous known algorithm on this problem, is the recent one by Dariusz Dereniowski, Dorota Osula, and Paweł Rzążewski that runs in n^{O(k^2)} steps. Joint work with: Mamadou Kanté and Dimitrios M. Thilikos Dieter Rautenbach: LP based approximation of induced matchings A matching in a graph is induced if no two of its edges are joined by an edge, and finding a large induced matching is a very hard problem. Lin et al. (Approximating weighted induced matchings, Discrete Applied Mathematics 243 (2018) 304310) provide an approximation algorithm with ratio Δ for the weighted version of the induced matching problem on graphs of maximum degree Δ. Their approach is based on an integer linear programming formulation whose integrality gap is at least Δ−1, that is, their approach offers only little room for improvement in the weighted case. For the unweighted case though, we conjecture that the integrality gap is at most 5Δ/8+O(1), and that also the approximation ratio can be improved at least to this value. We provide primaldual approximation algorithms with ratios (1−ϵ)Δ+1/2 for general Δ with ϵ≈0.02005, and 7/3 for Δ=3. Furthermore, we prove a bestpossible bound on the fractional induced matching number in terms of the order and the maximum degree. Joint work with: Julien Baste and Maximilian Fürst Olav Røthe Bakken: Graph Arrangement Problems Parameterized by Neighbourhood Diversity In this talk we will consider graph layout problems parametrized by neighbourhood diversity. Two vertices u and v in a graph G are in the same neighbourhood class if N(u) \ v = N(v) \ u. The neighbourhood diversity of G is exactly the number of distinct neighbourhood classes. In graph layout problems we try to find an optimal enumeration of the vertices of G subject to some criteria, for example in bandwidth we want to find the enumeration which minimizes the distance (in the enumeration) between the endpoints of any edge in G. Using some classical results about the parametrized complexity of integer linear programs, as well as recent results about integer quadratic problems, we show that bandwidth, distortion and imbalance is fixed parameter tractable when parametrized by neighbourhood diversity. Kiril Simonov: Constructing Large kcores in Low Degeneracy Graphs The kcore in a graph G is the maximal induced subgraph of G with all vertex degrees at least k. For a given graph G and integers k, b and p, is it possible to add at most b edges to G so that there is a kcore with at least p vertices? This problem is motivated by the studies of unraveling phenomena in social networks and was introduced by Chitnis and Talmon under the name Edge kCore. We give polynomial/FPT algorithms for Edge kCore on several classes of low degeneracy graphs: forests, graphs with small vertex cover, and graphs with small treewidth.
Joint work with: Fedor V. Fomin and Danil Sagunov Ignasi Sau: A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary For a fixed connected graph H, the {H}MDeletion problem asks, given a graph G, for the minimum number of vertices that intersect all minor models of H in G. It is known that this problem can be solved in time f(tw)·n^{O(1)}, where tw is the treewidth of G. We determine the asymptotically optimal function f(tw), for each possible choice of H. Namely, we prove that, under the ETH, f(tw)=2^{Θ(tw)} if H is a contraction of the chair or the banner, and f(tw)=2^{Θ(tw· log tw)} otherwise. Prior to this work, such a complete characterization was only known when H is a planar graph with at most five vertices. For the upper bounds, we present an algorithm in time 2^{Θ(tw· log tw)} · n^{O(1)} for the more general problem where all minor models of connected graphs in a finite family F need to be hit. We combine several ingredients such as the machinery of boundaried graphs in dynamic programming via representatives, the Flat Wall Theorem, Bidimensionality, the irrelevant vertex technique, treewidth modulators, and protrusion replacement. In particular, this algorithm vastly generalizes a result of Jansen et al. [SODA 2014] for the particular case F={K_{5},K_{3,3}}. For the lower bounds, our reductions are based on a generic construction building on the one given by the authors in [IPEC 2018], which uses the framework introduced by Lokshtanov et al. [SODA 2011] to obtain superexponential lower bounds. Joint work with: Julien Baste and Dimitrios M. Thilikos Giannos Stamoulis: Vertex deletion to planar FOL is fixed parameter tractable Given a First Order Logic sentence φ on graphs, we consider the problem Vertex φFOLplanarization where, given a graph G and an integer k, the question is whether it is possible to remove a set S of k vertices from G so that the resulting graph is planar and, moreover, G is a model for φ. We prove that, for every φ and every fixed k, Vertex φFOLplanarization can be solved in O(n^{2}) time. Joint work with: Fedor V. Fomin, Petr A. Golovach and Dimitrios M. Thilikos
Treewidth and cliquewidth are graph parameters of algorithmic use, with cliquewidth stronger in the sense that it is bounded on more classes of graphs. In this talk we will discuss the even stronger graph parameter mimwidth (maximum induced matchingwidth). Several nicely structured graphs, like interval graphs, permutation graphs and leaf power graphs, have mimwidth 1. We mention also a yet stronger parameter, simwidth (special induced matchingwidth), of value 1 even for chordal and cocomparability graphs. 
Online user: 1  RSS Feed 