Abstracts of talks

Ré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 best-known approximation for these cases from logarithmic to constant. In addition, we show that (p,q)-dEDS is FPT parameterized by p+q+tw, but W-hard 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 quasi-polynomial time but not in P; and a single case (p=q=1) which is NP-hard (under randomized reductions) and cannot be solved in sub-exponential time, under standard assumptions.

Joint work with: Tesshu Hanaka, Ioannis Katsikarelis, Eun Jung Kim, and Michael Lampis

Julien Baste: Composing dynamic programming tree-decomposition-based algorithms

Given two integers ℓ and p as well as $ℓ$ graph classes $H1, . . . ,Hℓ$, the problems GraphPart(H1, . . . ,Hℓ, p),VertPart(H1, . . . ,Hℓ), and EdgePart(H1, . . . ,Hℓ) ask, given graph G as input, whetherV(G), E(G) respectively can be partitioned into ℓ sets S1, . . . , Sℓ such that, for eachibetween 1 and ℓ, G[Vi]∈ Hi,G[Vi]∈ Hi, (V(G), Si)∈ Hi respectively. Moreover in GraphPart(H1, . . . ,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 tree-decomposition-based algorithms for recognizing the graph classes Hi, for each i, then we can constructively create a dynamic programming tree-decomposition-based algorithms for GraphPart(H1, . . . ,Hℓ, p),VertPart(H1, . . . ,Hℓ), and EdgePart(H1, . . . ,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 C3-Pakcing-T problem asks if there exists a least k (vertex-) disjoint directed 3-cycles in T. This is the dual problem in tournaments of the classical minimal feedback vertex set problem. Surprisingly C3-Pakcing-T 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/(c-1)) approximation algorithm for sparse tournaments having a linear representation where all the backward arcs have "length" at least c. Concerning kernelization, we show that C3-Pakcing-T 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 C3-Packing-T when restricted to sparse instances. On the negative size, we show that C3-Pakcing-T does not admit a kernel of (total bit) size O(k2-ε) unless NP is a subset of coNP/Poly. The existence of a kernel in O(k) vertices for C3-Pakcing-T 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 bin-packing 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 next-fit algorithm provides a 2-approximation for model UΩ, and a 2(Γ+1)approximation for model UΓ (which can be improved to 2-approximation 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 Knot-free Vertex Deletion on Digraphs

A knot in a directed graph G is a strongly connected subgraph Q of G with at least two vertices, such that no vertex in V(Q) is an in-neighbor of a vertex in V(G)\V(Q). Knots are important graph structures, because they characterize the existence of deadlocks in a classical distributed computation model, the so-called OR-model. Deadlock detection is correlated with the recognition of
knot-free graphs as well as deadlock resolution is closely related to the Knot-Free Vertex Deletion (KFVD) problem, which consists of
determining whether an input graph G has a subset S ⊆ V(G) of size at most k such that G[V\S] contains no
knot. Because of natural applications in deadlock resolution, KFVD is closely related to Directed Feedback Vertex Set.

In this paper we focus on graph width measure parameterizations for KFVD. First, we show that: (i) KFVD parameterized by the size of the solution k is W[1]-hard even when p, the length of a longest directed path of the input graph, as well as κ, its Kenny-width, are bounded by constants, and we remark that KFVD is para-NP-hard even considering many directed width measures as parameters, but in FPT when parameterized by clique-width; (ii) KFVD can be solved in time 2O(tw)×n, but assuming ETH it cannot be solved in 2o(tw)×nO(1), where tw is the treewidth of the underlying undirected graph. Finally, since the size of a minimum directed feedback vertex set (dfv) is an upper bound for the size of a minimum knot-free vertex deletion set, we investigate parameterization by dfv and we show that (iii) KFVD can be solved in FPT-time parameterized by either dfv+κ or dfv+p; and it admits a Turing kernel by the distance to a DAG having an Hamiltonian path (another parameter larger than dfv). Results of (iii) cannot be improved when replacing dfv by k due to (i).

Joint work with: Stéphane Bessy, Alan D. A. Carneiro, Fábio Protti and Uéverton S. Souza

 

Michael Fellows: An Interesting Gap Between Upper and Lower Bounds in the Proliferation of
Structural Width Metrics

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 finite-state. 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 finite-state, is available by much simpler Myhill-Nerode 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 First-Order Logic Properties

We establish new connections between parameterized/kernelization complexity of graph modification problems and expressibility in logic. For a first-order 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 fixed-parameter tractable (parameterized by k) and when it admits a polynomial kernel.

Joint work with: Fedor V. Fomin and Dimitrios M. Thilikos

Daniel Gonçalves: 3-colorable 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 3-colorable 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 non-negative integer k, answers whether there is a successful monotone and connected node search strategy on G of cost at most k, in 2O(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 non-connected variant of node-search. 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 nO(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) 304-310) 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 primal-dual approximation algorithms with ratios (1−ϵ)Δ+1/2 for general Δ with ϵ≈0.02005, and 7/3 for Δ=3. Furthermore, we prove a best-possible 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 k-cores in Low Degeneracy Graphs

The k-core 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 k-core 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 k-Core.  We give polynomial/FPT algorithms for Edge k-Core 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}-M-Deletion 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)·nO(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) · nO(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={K5,K3,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 φ-FOL-planarization 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 φ-FOL-planarization can be solved in O(n2) time.

Joint work with: Fedor V. Fomin, Petr A. Golovach and Dimitrios M. Thilikos


Jan-Arne Telle: Width parameters of graphs and structured graph classes

Tree-width and clique-width are graph parameters of algorithmic use, with clique-width stronger in the sense that it is bounded on more classes of graphs. In this talk we will discuss the even stronger graph parameter mim-width (maximum induced matching-width). Several nicely structured graphs, like interval graphs, permutation graphs and leaf power graphs, have mim-width 1. We mention also a yet stronger parameter, sim-width (special induced matching-width), of value 1 even for chordal and co-comparability graphs.
Online user: 8 RSS Feed | Privacy
Loading...