nach oben

2020 | Buch

Kapitel lesen Erstes Kapitel lesen

Treewidth, Kernels, and Algorithms

Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday

herausgegeben von: Fedor V. Fomin, Stefan Kratsch, Erik Jan van Leeuwen

Verlag: Springer International Publishing

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This Festschrift was published in honor of Hans L. Bodlaender on the occasion of his 60th birthday.

The 14 full and 5 short contributions included in this volume show the many transformative discoveries made by H.L. Bodlaender in the areas of graph algorithms, parameterized complexity, kernelization and combinatorial games. The papers are written by his former Ph.D. students and colleagues as well as by his former Ph.D. advisor, Jan van Leeuwen.

Inhaltsverzeichnis

Frontmatter

Open Access

Correction to: Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds

Chapter [“Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds”] was previously published non-open access. It has now been changed to open access under a CC BY 4.0 license and the copyright holder updated to ‘The Author(s)’. The book has also been updated with this change.

Bart M. P. Jansen

PDF Zum Volltext

Short Contributions

Frontmatter

Seeing Arboretum for the (partial k-) Trees

Abstract

The idea of applying a dynamic programming strategy to evaluating certain objective functions on trees is fairly straightforward. The road for this idea to develop into theories of width parameters has been not so straight. Hans Bodlaender has played a major role in the process of mapping out that road. In this sentimental journey, we will recount our collective road trip over the past decades.

Stefan Arnborg, Andrzej Proskurowski

Collaborating with Hans: Some Remaining Wonderments

Abstract

This paper celebrates some family adventures, three concrete open problems and several research directions that have developed over our long collaboration.

Michael R. Fellows, Frances A. Rosamond

Hans Bodlaender and the Theory of Kernelization Lower Bounds

Abstract

In this short letter I give a brief subjective account of my favorite result with Hans – our kernelization lower bounds framework. The purpose of this manuscript is not to give a formal introduction to this result and the area that spawned from it, nor is it meant to be a comprehensive survey of all related and relevant results. Rather, my aim here is to informally describe the history that lead to this result from a personal perspective, and to outline Hans’s role in the development of this theory into what it is today.

Danny Hermelin

Algorithms, Complexity, and Hans

Abstract

In this essay on the occasion of Hans Bodlaender’s 60th birthday, we recount some of the early developments in the field in which Hans made his mark and of their context at Utrecht University.

Jan van Leeuwen

Surveys

Frontmatter

Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs

Abstract

Recently it was shown that many classic graph problems—Independent Set, Dominating Set, Hamiltonian Cycle, and more—can be solved in subexponential time on unit-ball graphs. More precisely, these problems can be solved in \(2^{O(n^{1-1/d})}\) time on unit-ball graphs in \(\mathbb {R}^d\), which is tight under ETH. The result can be generalized to intersection graphs of similarly-sized fat objects.

For Independent Set the same running time can be achieved for non-similarly-sized fat objects, and for the weighted version of the problem. We show that such generalizations most likely are not possible for Dominating Set: assuming ETH, we prove that

there is no algorithm with running time \(2^{o(n)}\) for Dominating Set on (non-unit) ball graphs in \(\mathbb {R}^3\);
there is no algorithm with running time \(2^{o(n)}\) for Weighted Dominating Set on unit-ball graphs in \(\mathbb {R}^3\);
there is no algorithm with running time \(2^{o(n)}\) for Dominating Set, Connected Dominating Set, or Steiner Tree on intersections graphs of arbitrary convex (but non-constant-complexity) objects in the plane.

Mark de Berg, Sándor Kisfaludi-Bak

As Time Goes By: Reflections on Treewidth for Temporal Graphs

Abstract

Treewidth is arguably the most important structural graph parameter leading to algorithmically beneficial graph decompositions. Triggered by a strongly growing interest in temporal networks (graphs where edge sets change over time), we discuss fresh algorithmic views on temporal tree decompositions and temporal treewidth. We review and explain some of the recent work together with some encountered pitfalls, and we point out challenges for future research.

Till Fluschnik, Hendrik Molter, Rolf Niedermeier, Malte Renken, Philipp Zschoche

Possible and Impossible Attempts to Solve the Treewidth Problem via ILPs

Abstract

We survey a number of integer programming formulations for the pathwidth and treewidth problems. The attempts to find good formulations for the problems span the period of 15 years, yet without any true success. Nevertheless, some formulations provide potentially useful frameworks for attacking these notorious problems. Some others are just curious and interesting fruits of mathematical imagination.

Alexander Grigoriev

Open Access

Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds

Abstract

On the occasion of Hans Bodlaender’s 60th birthday, I give a personal account of our history and work together on the technique of cross-composition for kernelization lower bounds. I present several simple new proofs for polynomial kernelization lower bounds using cross-composition, interlaced with personal anecdotes about my time as Hans’ PhD student at Utrecht University. Concretely, I will prove that Vertex Cover, Feedback Vertex Set, and the H-Factor problem for every graph H that has a connected component of at least three vertices, do not admit kernels of \(\mathcal {O}(n^{2-\varepsilon })\) bits when parameterized by the number of vertices n for any \(\varepsilon > 0\), unless \(\mathsf {NP \subseteq coNP/poly}\). These lower bounds are obtained by elementary gadget constructions, in particular avoiding the use of the Packing Lemma by Dell and van Melkebeek.

Bart M. P. Jansen

PDF Zum Volltext

Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths

Abstract

In the Disjoint Paths problem, the input consists of an n-vertex graph G and a collection of k vertex pairs, \(\{(s_i,t_i)\}_{i=1}^k\), and the objective is to determine whether there exists a collection \(\{P_i\}_{i=1}^k\) of k pairwise vertex-disjoint paths in G where the end-vertices of \(P_i\) are \(s_i\) and \(t_i\). This problem was shown to admit an \(f(k)n^3\)-time algorithm by Robertson and Seymour Graph Minors XIII, The Disjoint Paths Problem, JCTB. In modern terminology, this means that Disjoint Paths is fixed parameter tractable (FPT) with respect to k. Remarkably, the above algorithm for Disjoint Paths is a cornerstone of the entire Graph Minors Theory, and conceptually vital to the \(g(k)n^3\)-time algorithm for Minor Testing (given two undirected graphs, G and H on n and k vertices, respectively, determine whether G contains H as a minor).

In this semi-survey, we will first give an exposition of the Graph Minors Theory with emphasis on efficiency from the viewpoint of Parameterized Complexity. Secondly, we will review the state of the art with respect to the Disjoint Paths and Planar Disjoint Paths problems. Lastly, we will discuss the main ideas behind a new algorithm that combines treewidth reduction and an algebraic approach to solve Planar Disjoint Paths in time \(2^{k^{\mathcal {O}(1)}}n^{\mathcal {O}(1)}\) (for undirected graphs).

Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi

Four Shorts Stories on Surprising Algorithmic Uses of Treewidth

Abstract

This article briefly describes four algorithmic problems where the notion of treewidth is very useful. Even though the problems themselves have nothing to do with treewidth, it turns out that combining known results on treewidth allows us to easily describe very clean and high-level algorithms.

Dániel Marx

Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices

Abstract

We survey a number of recent results that relate the fine-grained complexity of several NP-Hard problems with the rank of certain matrices. The main technical theme is that for a wide variety of Divide & Conquer algorithms, structural insights on associated partial solutions matrices may directly lead to speedups.

Jesper Nederlof

A Survey on Spanning Tree Congestion

Abstract

In this short survey dedicated to Hans L. Bodlaender on the occasion of his 60th birthday, we review known results and open problems about the spanning tree congestion problem. We focus mostly on the algorithmic results, where his contribution was precious.

Yota Otachi

Surprising Applications of Treewidth Bounds for Planar Graphs

Abstract

In this chapter we continue a story told from in Dániel Marx’s Chapter and present three examples of surprising use of treewidth. In all cases, we present a state-of-the-art and provably optimal (assuming the Exponential Time Hypothesis) algorithm exploiting a sublinear bound on the treewidth of an auxiliary graph taken out of the blue.

Marcin Pilipczuk

Computing Tree Decompositions

Abstract

In this chapter we review the most important algorithmic approaches to the following problem: given a graph G, compute a tree decomposition of G of (nearly) optimum width. We present the 4-approximation algorithm running in time \(\mathcal {O}(27^k\cdot k^2\cdot n^2)\), which was first proposed by Robertson and Seymour in the Graph Minors series, and we discuss the main ideas behind the exact algorithm of Bodlaender that runs in linear fixed-parameter time [2].

Michał Pilipczuk

Experimental Analysis of Treewidth

Abstract

The goal of this chapter is to provide insights into treewidth obtained from experiments. In our experiments, we count the numbers of combinatorial objects closely related to treewidth in random graph instances. These combinatorial objects include connected sets, minimal separators, potential maximal cliques, and those with certain constraints. Such experimental analysis is expected to complement theoretical analysis, reveal the reasons why some algorithms work well in practice while some do not, and provide a basis for designing new algorithms.

Hisao Tamaki

A Retrospective on (Meta) Kernelization

Abstract

In parameterized complexity, a kernelization algorithm can be seen as a reduction of a parameterized problem to itself, so that the produced equivalent instance has size depending exclusively on the parameter. If this size is polynomial, then we say that the parameterized problem in question admits a polynomial kernelization algorithm. Kernelization can be seen as a formalization of the notion of preprocessing and has occupied a big part of the research on Multi-variate Algorithmics. The first algorithmic meta-theorem on kernelization appeared in [14] and unified a large family of previously known kernelization results on problems defined on topologically embeddable graphs. In this exposition we present the central results of this paper. During our presentation we pay attention to the abstractions on which the results where founded and take into account the subsequent advancements on this topic.

Dimitrios M. Thilikos

Games, Puzzles and Treewidth

Abstract

We discuss some results on the complexity of games and puzzles. In particular, we focus on the relationship between bounded treewidth and the (in-)tractability of games and puzzles in which graphs play a role. We discuss some general methods which are good starting points for finding complexity proofs for games and puzzles.

Tom C. van der Zanden

Fast Algorithms for Join Operations on Tree Decompositions

Abstract

Treewidth is a measure of how tree-like a graph is. It has many important algorithmic applications because many NP-hard problems on general graphs become tractable when restricted to graphs of bounded treewidth. Algorithms for problems on graphs of bounded treewidth mostly are dynamic programming algorithms using the structure of a tree decomposition of the graph. The bottleneck in the worst-case run time of these algorithms often is the computations for the so called join nodes in the associated nice tree decomposition.

In this paper, we review two different approaches that have appeared in the literature about computations for the join nodes: one using fast zeta and Möbius transforms and one using fast Fourier transforms. We combine these approaches to obtain new, faster algorithms for a broad class of vertex subset problems known as the \([\sigma ,\rho ]\)-domination problems. Our main result is that we show how to solve \([\sigma ,\rho ]\)-domination problems in \(\mathcal {O}(s^{t+2} t n^2 (t\log (s)+\log (n)))\) arithmetic operations. Here, t is the treewidth, s is the (fixed) number of states required to represent partial solutions of the specific \([\sigma ,\rho ]\)-domination problem, and n is the number of vertices in the graph. This reduces the polynomial factors involved compared to the previously best time bound (van Rooij, Bodlaender, Rossmanith, ESA 2009) of \(\mathcal {O}( s^{t+2} (st)^{2(s-2)} n^3 )\) arithmetic operations. In particular, this removes the dependence of the degree of the polynomial on the fixed number of states s.

Johan M. M. van Rooij

Backmatter

Titel: Treewidth, Kernels, and Algorithms
herausgegeben von: Fedor V. Fomin
Stefan Kratsch
Erik Jan van Leeuwen
Verlag: Springer International Publishing
Electronic ISBN: 978-3-030-42071-0
Print ISBN: 978-3-030-42070-3
DOI: https://doi.org/10.1007/978-3-030-42071-0