Hans L. Bodlaender

JAAMAS Journal 2025 Journal Article

Hedonic seat arrangement problems

• Hans L. Bodlaender
• Tesshu Hanaka
• Tom C. van der Zanden

Abstract In this paper, we study a variant of hedonic games, called Seat Arrangement. The model is defined by a bijection from agents with preferences for each other to vertices in a graph G. The utility of an agent depends on the neighbors assigned in the graph. More precisely, it is the sum over all neighbors of the preferences that the agent has towards the agent assigned to the neighbor. We first consider the price of stability and fairness for different classes of preferences. In particular, we show that there is an instance such that the price of fairness (PoF) is unbounded in general. Moreover, we show an upper bound \(\tilde{d}(G)\) and an almost tight lower bound \(\tilde{d}(G)-1/4\) of PoF, where \(\tilde{d}(G)\) is the average degree of an input graph. Then we investigate the computational complexity of problems to find certain “good” seat arrangements, say Utilitarian Arrangement, Egalitarian Arrangement, Stable Arrangement, and Envy-free Arrangement. We give dichotomies of computational complexity of four Seat Arrangement problems from the perspective of the maximum order of connected components in an input graph. For the parameterized complexity, Utilitarian Arrangement can be solved in time \(n^{O(\gamma )}\), while it cannot be solved in time \(f(\gamma )n^{o(\gamma )}\) under ETH, where n is the number of agents and \(\gamma\) is the vertex cover number of an input graph. Moreover, we show that Egalitarian Arrangement and Envy-free Arrangement are weakly NP-hard even on graphs of bounded vertex cover number. Finally, we prove that determining whether a stable arrangement can be obtained from a given arrangement by k swaps is W[1]-hard when parameterized by \(k+\gamma\), whereas it can be solved in time \(n^{O(k)}\).

I&C Journal 2024 Journal Article

Parameterized problems complete for nondeterministic FPT time and logarithmic space

• Hans L. Bodlaender
• Carla Groenland
• Jesper Nederlof
• Céline Swennenhuis

Let XNLP be the class of parameterized problems such that an instance of size n with parameter k can be solved nondeterministically in time f ( k ) n O ( 1 ) and space f ( k ) log ⁡ ( n ) (for some computable function f). We give a wide variety of XNLP-complete problems, such as List Coloring and Precoloring Extension with pathwidth as parameter, Scheduling of Jobs with Precedence Constraints, with both number of machines and partial order width as parameter, Bandwidth and variants of Weighted CNF-Satisfiability. In particular, this implies that all these problems are W [ t ] -hard for all t.

FOCS Conference 2021 Conference Paper

Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space

• Hans L. Bodlaender
• Carla Groenland
• Jesper Nederlof
• Céline M. F. Swennenhuis

Let XNLP be the class of parameterized prob-lems such that an instance of size $n$ with parameter $k$ can be solved nondeterministically in time $f$ ( $k$ ) nO (1) and space f (k) log(n) (for some computable function f). We give a wide variety of XNLP-complete problems, such as List Coloringand Precoloring Extensionwith pathwidth as parameter, Scheduling Of Jobs With Precedence Constraints, with both number of machines and partial order width as parameter, Bandwidthand variants of Weighted Cnf-satisfiability and reconfiguration problems. In particular, this implies that all these problems are W[ $t$ ]-hard for all t. This also answers a long standing question on the parameterized complexity of the Bandwidth problem.

TCS Journal 2021 Journal Article

Steiner trees for hereditary graph classes: A treewidth perspective

• Hans L. Bodlaender
• Nick Brettell
• Matthew Johnson
• Giacomo Paesani
• Daniël Paulusma
• Erik Jan van Leeuwen

We consider the classical problems (Edge) Steiner Tree and Vertex Steiner Tree after restricting the input to some class of graphs characterized by a small set of forbidden induced subgraphs. We show a dichotomy for the former problem restricted to ( H 1, H 2 ) -free graphs and a dichotomy for the latter problem restricted to H-free graphs. We find that there exists an infinite family of graphs H such that Vertex Steiner Tree is polynomial-time solvable for H-free graphs, whereas there exist only two graphs H for which this holds for Edge Steiner Tree (assuming P ≠ NP ). We also find that Edge Steiner Tree is polynomial-time solvable for ( H 1, H 2 ) -free graphs if and only if the treewidth of the class of ( H 1, H 2 ) -free graphs is bounded (subject to P ≠ NP ). To obtain the latter result, we determine all pairs ( H 1, H 2 ) for which the class of ( H 1, H 2 ) -free graphs has bounded treewidth.

TCS Journal 2020 Journal Article

On the exact complexity of polyomino packing

• Hans L. Bodlaender
• Tom C. van der Zanden

We show that the problem of deciding whether a collection of polyominoes, each fitting in a 2 × O ( log ⁡ n ) rectangle, can be packed into a 3 × n box does not admit a 2 o ( n / log ⁡ n ) -time algorithm, unless the Exponential Time Hypothesis fails. We also give an algorithm that attains this lower bound, solving any instance of polyomino packing with total area n in 2 O ( n / log ⁡ n ) time. This establishes a tight bound on the complexity of Polyomino Packing, even in a very restricted case. In contrast, for a 2 × n box, we show that the problem can be solved in strongly subexponential time.

TCS Journal 2020 Journal Article

Recognizing hyperelliptic graphs in polynomial time

• Jelco M. Bodewes
• Hans L. Bodlaender
• Gunther Cornelissen
• Marieke van der Wegen

Based on analogies between algebraic curves and graphs, Baker and Norine introduced divisorial gonality, a graph parameter for multigraphs related to treewidth, multigraph algorithms and number theory. Various equivalent definitions of the gonality of an algebraic curve translate to different notions of gonality for graphs, called stable gonality and stable divisorial gonality. We consider so-called hyperelliptic graphs (multigraphs of gonality 2, in any meaning of graph gonality) and provide a safe and complete set of reduction rules for such multigraphs. This results in an algorithm to recognize hyperelliptic graphs in time O ( m + n log ⁡ n ), where n is the number of vertices and m the number of edges of the multigraph. A corollary is that we can decide with the same runtime whether a two-edge-connected graph G admits an involution σ such that the quotient G / 〈 σ 〉 is a tree.

TCS Journal 2019 Journal Article

On the maximum weight minimal separator

• Tesshu Hanaka
• Hans L. Bodlaender
• Tom C. van der Zanden
• Hirotaka Ono

Given an undirected and connected graph G = ( V, E ) and two vertices s, t ∈ V, a vertex subset S that separates s and t is called an s-t separator, and an s-t separator is called minimal if no proper subset of S separates s and t. Moreover, we say that a set S is a minimal separator of G if S is a minimal s-t separator for some s and t. In this paper, we consider finding a minimal (s-t) separator with maximum weight on a vertex-weighted graph. We first prove that these problems are NP-hard. On the other hand, we give an O ⁎ ( tw O ( tw ) ) -time deterministic algorithm based on tree decompositions where O ⁎ is the order notation omitting the polynomial factor of n. Moreover, we improve the algorithm by using the Rank-Based approach and the running time is O ⁎ ( 38 ⋅ 2 ω ) tw. Finally, we give an O ⁎ ( 9 tw ⋅ W 2 ) -time randomized algorithm to determine whether there exists a minimal (s-t) separator where W is its weight and tw is the treewidth of G.

STOC Conference 2018 Conference Paper

A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs

• Mark de Berg
• Hans L. Bodlaender
• Sándor Kisfaludi-Bak
• Dániel Marx
• Tom C. van der Zanden

We give an algorithmic and lower-bound framework that facilitates the construction of subexponential algorithms and matching conditional complexity bounds. It can be applied to a wide range of geometric intersection graphs (intersections of similarly sized fat objects), yielding algorithms with running time 2 O ( n 1−1/ d ) for any fixed dimension d ≥ 2 for many well known graph problems, including Independent Set, r -Dominating Set for constant r , and Steiner Tree. For most problems, we get improved running times compared to prior work; in some cases, we give the first known subexponential algorithm in geometric intersection graphs. Additionally, most of the obtained algorithms work on the graph itself, i.e., do not require any geometric information. Our algorithmic framework is based on a weighted separator theorem and various treewidth techniques.

FOCS Conference 2018 Conference Paper

An ETH-Tight Exact Algorithm for Euclidean TSP

• Mark de Berg
• Hans L. Bodlaender
• Sándor Kisfaludi-Bak
• Sudeshna Kolay

We study exact algorithms for Euclidean TSP in R d. In the early 1990s algorithms with n O(√n) running time were presented for the planar case, and some years later an algorithm with n O(n1-1/d) running time was presented for any d ≥ 2. Despite significant interest in subexponential exact algorithms over the past decade, there has been no progress on Euclidean TSP, except for a lower bound stating that the problem admits no 2 O (n 1-1/d-ε ) algorithm unless ETH fails. Up to constant factors in the exponent, we settle the complexity of Euclidean TSP by giving a 2 O(n1-1/d) algorithm and by showing that a 2 o(n1-1/d) algorithm does not exist unless ETH fails.

I&C Journal 2015 Journal Article

Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth

• Hans L. Bodlaender
• Marek Cygan
• Stefan Kratsch
• Jesper Nederlof

It is well known that many local graph problems, like Vertex Cover and Dominating Set, can be solved in time 2 O ( tw ) | V | O ( 1 ) for graphs G = ( V, E ) with a given tree decomposition of width tw. However, for nonlocal problems, like the fundamental class of connectivity problems, for a long time we did not know how to do this faster than tw O ( tw ) | V | O ( 1 ). Recently, Cygan et al. (FOCS 2011) presented Monte Carlo algorithms for a wide range of connectivity problems running in time c tw | V | O ( 1 ) for a small constant c, e. g. , for Hamiltonian Cycle and Steiner Tree. Naturally, this raises the question whether randomization is necessary to achieve this runtime; furthermore, it is desirable to also solve counting and weighted versions (the latter without incurring a pseudo-polynomial cost in the runtime in terms of the weights). We present two new approaches rooted in linear algebra, based on matrix rank and determinants, which provide deterministic c tw | V | O ( 1 ) time algorithms, also for weighted and counting versions. For example, in this time we can solve Traveling Salesman or count the number of Hamiltonian cycles. The rank based ideas provide a rather general approach for speeding up even straightforward dynamic programming formulations by identifying “small” sets of representative partial solutions; we focus on the case of expressing connectivity via sets of partitions, but the essential ideas should have further applications. The determinant-based approach uses the Matrix Tree Theorem for deriving closed formulas for counting versions of connectivity problems; we show how to evaluate those formulas via dynamic programming.

TCS Journal 2015 Journal Article

Exact algorithms for Kayles

• Hans L. Bodlaender
• Dieter Kratsch
• Sjoerd T. Timmer

In the game of Kayles, two players select alternatingly a vertex from a given graph G, but may never choose a vertex that is adjacent or equal to an already chosen vertex. The last player that can select a vertex wins the game. In this paper, we give an exact algorithm to determine which player has a winning strategy in this game. To analyze the running time of the algorithm, we introduce the notion of a K-set: a nonempty set of vertices W ⊆ V is a K-set in a graph G = ( V, E ), if G [ W ] is connected and there exists an independent set X such that W = V − N [ X ]. The running time of the algorithm is bounded by a polynomial factor times the number of K-sets in G. We prove that the number of K-sets in a graph with n vertices is bounded by O ( 1. 6052 n ). A computer-generated case analysis improves this bound to O ( 1. 6031 n ) K-sets, and thus we have an upper bound of O ( 1. 6031 n ) on the running time of the algorithm for Kayles. We also show that the number of K-sets in a tree is bounded by n ⋅ 3 n / 3 and thus Kayles can be solved on trees in O ( 1. 4423 n ) time. We show that apart from a polynomial factor, the number of K-sets in a tree is sharp. As corollaries, we obtain that determining which player has a winning strategy in the games G avoid ( POS DNF 2 ) and G seek ( POSDNF 3 ) can also be determined in O ( 1. 6031 n ) time. In G avoid ( POSDNF 2 ), we have a positive formula F on n Boolean variables in Disjunctive Normal Form with two variables per clause. Initially, all variables are false, and players alternately set a variable from false to true; the first player that makes F true loses the game. The game G seek ( POSDNF 3 ) is similar, but now there are three variables per clause, and the first player that makes F true wins the game.

ECAI Conference 2014 Conference Paper

Provisional Propagation for Verifying Monotonicity of Bayesian Networks

• Merel T. Rietbergen
• Linda C. van der Gaag
• Hans L. Bodlaender

Many real-world Bayesian networks are expected to exhibit commonly known properties of monotonicity. Since monotonicity violations may be introduced despite careful engineering efforts, these properties need be verified before using a network in practice. We will show that the problem of verifying monotonicity in general has a prohibitively high computational complexity. We will argue however, that the runtime complexity involved can be substantially reduced by using a tailored algorithm which we coined provisional propagation. By means of this algorithm in fact, verifying monotonicity may become feasible for a range of real-world networks.

FOCS Conference 2013 Conference Paper

An O(c^k n) 5-Approximation Algorithm for Treewidth

• Hans L. Bodlaender
• Pål Grønås Drange
• Markus S. Dregi
• Fedor V. Fomin
• Daniel Lokshtanov
• Michal Pilipczuk

We give an algorithm that for an input n-vertex graph G and integer k > 0, in time O(c k n) either outputs that the tree width of G is larger than k, or gives a tree decomposition of G of width at most 5k + 4. This is the first algorithm providing a constant factor approximation for tree width which runs in time single-exponential in k and linear in n. Tree width based computations are subroutines of numerous algorithms. Our algorithm can be used to speed up many such algorithms to work in time which is single-exponential in the tree width and linear in the input size.

TCS Journal 2013 Journal Article

Kernel bounds for path and cycle problems

• Hans L. Bodlaender
• Bart M.P. Jansen
• Stefan Kratsch

Connectivity problems like k -Path and k -Disjoint Paths relate to many important milestones in parameterized complexity, namely the Graph Minors Project, color coding, and the recent development of techniques for obtaining kernelization lower bounds. This work explores the existence of polynomial kernels for various path and cycle problems, by considering nonstandard parameterizations. We show polynomial kernels when the parameters are a given vertex cover, a modulator to a cluster graph, or a (promised) max leaf number. We obtain lower bounds via cross-composition, e. g. , for Hamiltonian Cycle and related problems when parameterized by a modulator to an outerplanar graph.

TCS Journal 2012 Journal Article

On switching classes, NLC-width, cliquewidth and treewidth

• Hans L. Bodlaender
• Jurriaan Hage

In this paper we consider a connection between switching (of undirected graphs), and the notions of NLC-width, cliquewidth and treewidth. In particular, we show that the NLC-widths and the cliquewidths of two graphs in a switching class are at most a constant factor apart (2 for the former, 4 for the latter). A similar result can be shown not to hold for treewidth: it is easy to find a switching classes in which the distance between the lowest treewidth and the highest is dependent on the number of vertices of the graph. We also show that for NLC-width every width between the lowest and the highest of the switching class is attained by some graph in that switching class. We prove that this also holds for treewidth.

TCS Journal 2011 Journal Article

Kernel bounds for disjoint cycles and disjoint paths

• Hans L. Bodlaender
• Stéphan Thomassé
• Anders Yeo

In this paper, we show that the problems Disjoint Cycles and Disjoint Paths do not have polynomial kernels, unless N P ⊆ c o N P / p o l y. Thus, these problems do not allow polynomial time preprocessing that results in instances whose size is bounded by a polynomial in the parameter at hand. We build upon recent results by Bodlaender et al. [6] and Fortnow and Santhanam [20], that show that NP-complete problems that are ‘or-compositional’ do not have polynomial kernels, unless N P ⊆ c o N P / p o l y. To this machinery, we add a notion of transformation, and obtain that Disjoint Cycles, and Disjoint Paths do not have polynomial kernels, unless N P ⊆ c o N P / p o l y. For the proof, we introduce a problem on strings, called Disjoint Factors, and first show that this problem has no polynomial kernel unless N P ⊆ c o N P / p o l y. We also show that the related Disjoint Cycles Packing problem has a kernel of size O ( k log k ).

I&C Journal 2011 Journal Article

Treewidth computations II. Lower bounds

• Hans L. Bodlaender
• Arie M.C.A. Koster

For several applications, it is important to be able to compute the treewidth of a given graph and to find tree decompositions of small width reasonably fast. Good lower bounds on the treewidth of a graph can, amongst others, help to speed up branch and bound algorithms that compute the treewidth of a graph exactly. A high lower bound for a specific graph instance can tell that a dynamic programming approach for solving a problem is infeasible for this instance. This paper gives an overview of several recent methods that give lower bounds on the treewidth of graphs.

TCS Journal 2010 Journal Article

Clustering with partial information

• Hans L. Bodlaender
• Michael R. Fellows
• Pinar Heggernes
• Federico Mancini
• Charis Papadopoulos
• Frances Rosamond

The Correlation Clustering problem, also known as the Cluster Editing problem, seeks to edit a given graph by adding and deleting edges to obtain a collection of vertex-disjoint cliques, such that the editing cost is minimized. The Edge Clique Partitioning problem seeks to partition the edges of a given graph into edge-disjoint cliques, such that the number of cliques is minimized. Both problems are known to be NP-hard, and they have been previously studied with respect to approximation and fixed-parameter tractability. In this paper we study these two problems in a more general setting that we term fuzzy graphs, where the input graphs may have missing information, meaning that whether or not there is an edge between some pairs of vertices of the input graph can be undecided. For fuzzy graphs the Correlation Clustering and Edge Clique Partitioning problems have previously been studied only with respect to approximation. Here we give parameterized algorithms based on kernelization for both problems. We prove that the Correlation Clustering problem is fixed-parameter tractable on fuzzy graphs when parameterized by ( k, r ), where k is the editing cost and r is the minimum number of vertices required to cover the undecided edges. In particular we show that it has a polynomial-time reduction to a problem kernel on O ( k 2 + r ) vertices. We provide an analogous result for the Edge Clique Partitioning problem on fuzzy graphs. Using ( k, r ) as parameters, where k bounds the size of the partition, and r is the minimum number of vertices required to cover the undecided edges, we describe a polynomial-time kernelization to a problem kernel on O ( k 4 ⋅ 3 r ) vertices. This implies fixed-parameter tractability for this parameterization. Furthermore we also show that parameterizing only by the number of cliques k, is not enough to obtain fixed-parameter tractability. The problem remains, in fact, NP-hard for each fixed k > 2.

MFCS Conference 2010 Conference Paper

Faster Algorithms on Branch and Clique Decompositions

• Hans L. Bodlaender
• Erik Jan van Leeuwen
• Johan M. M. van Rooij
• Martin Vatshelle

Abstract We combine two techniques recently introduced to obtain faster dynamic programming algorithms for optimization problems on graph decompositions. The unification of generalized fast subset convolution and fast matrix multiplication yields significant improvements to the running time of previous algorithms for several optimization problems. As an example, we give an \(O^{*}(3^{\frac{\omega}{2}k})\) time algorithm for Minimum Dominating Set on graphs of branchwidth k, improving on the previous O * (4 k ) algorithm. Here ω is the exponent in the running time of the best matrix multiplication algorithm (currently ω < 2. 376). For graphs of cliquewidth k, we improve from O * (8 k ) to O * (4 k ). We also obtain an algorithm for counting the number of perfect matchings of a graph, given a branch decomposition of width k, that runs in time \(O^{*}(2^{\frac{\omega}{2}k})\). Generalizing these approaches, we obtain faster algorithms for all so-called [ ρ, σ ]-domination problems on branch decompositions if ρ and σ are finite or cofinite. The algorithms presented in this paper either attain or are very close to natural lower bounds for these problems.

ECAI Conference 2010 Conference Paper

The Necessity of Bounded Treewidth for Efficient Inference in Bayesian Networks

• Johan Kwisthout
• Hans L. Bodlaender
• Linda C. van der Gaag

Algorithms for probabilistic inference in Bayesian networks are known to have running times that are worst-case exponential in the size of the network. For networks with a moralised graph of bounded treewidth, however, these algorithms take a time which is linear in the network's size. In this paper, we show that under the assumption of the Exponential Time Hypothesis (ETH), small treewidth of the moralised graph actually is a necessary condition for a Bayesian network to render inference efficient by an algorithm accepting arbitrary instances. We thus show that no algorithm can exist that performs inference on arbitrary Bayesian networks of unbounded treewidth in polynomial time, unless the ETH fails.

I&C Journal 2010 Journal Article

Treewidth computations I. Upper bounds

• Hans L. Bodlaender
• Arie M.C.A. Koster

For more and more applications, it is important to be able to compute the treewidth of a given graph and to find tree decompositions of small width reasonably fast. This paper gives an overview of several upper bound heuristics that have been proposed and tested for the problem of determining the treewidth of a graph and finding tree decompositions. Each of the heuristics produces tree decompositions whose width may be larger than the optimal width. However, experiments show that in many cases, the heuristics give tree decompositions whose width is close to the exact treewidth of the input graphs.

FOCS Conference 2009 Conference Paper

(Meta) Kernelization

• Hans L. Bodlaender
• Fedor V. Fomin
• Daniel Lokshtanov
• Eelko Penninkx
• Saket Saurabh 0001
• Dimitrios M. Thilikos

Polynomial time preprocessing to reduce instance size is one of the most commonly deployed heuristics to tackle computationally hard problems. In a parameterized problem, every instance I comes with a positive integer k. The problem is said to admit a polynomial kernel if, in polynomial time, we can reduce the size of the instance I to a polynomial in k, while preserving the answer. In this paper, we show that all problems expressible in Counting Monadic Second Order Logic and satisfying a compactness property admit a polynomial kernel on graphs of bounded genus. Our second result is that all problems that have finite integer index and satisfy a weaker compactness condition admit a linear kernel on graphs of bounded genus. The study of kernels on planar graphs was initiated by a seminal paper of Alber, Fellows, and Niedermeier [J. ACM, 2004 ] who showed that Planar Dominating Set admits a linear kernel. Following this result, a multitude of problems have been shown to admit linear kernels on planar graphs by combining the ideas of Alber et al. with problem specific reduction rules. Our theorems unify and extend all previously known kernelization results for planar graph problems. Combining our theorems with the Erdos-Posa property we obtain various new results on linear kernels for a number of packing and covering problems.

MFCS Conference 2008 Conference Paper

Clustering with Partial Information

• Hans L. Bodlaender
• Michael R. Fellows
• Pinar Heggernes
• Federico Mancini 0001
• Charis Papadopoulos
• Frances A. Rosamond

Abstract The Correlation Clustering problem, also known as the Cluster Editing problem, seeks to edit a given graph by adding and deleting edges to obtain a collection of vertex-disjoint cliques, such that the editing cost is minimized. The Edge Clique Partitioning problem seeks to partition the edges of a given graph into edge-disjoint cliques, such that the number of cliques is minimized. Both problems are known to be NP-hard, and they have been previously studied with respect to approximation and fixed parameter tractability. In this paper we study these two problems in a more general setting that we term fuzzy graphs, where the input graphs may have missing information, meaning that whether or not there is an edge between some pairs of vertices of the input graph can be undecided. For fuzzy graphs the Correlation Clustering and Edge Clique Partitioning problems have previously been studied only with respect to approximation. Here we give parameterized algorithms based on kernelization for both problems. We prove that the Correlation Clustering problem is fixed-parameter tractable on fuzzy graphs when parameterized by ( k, r ), where k is the editing cost and r is the minimum number of vertices required to cover the undecided edges. In particular we show that it has a polynomial-time reduction to a problem kernel on O ( k 2 + r ) vertices. We provide an analogous result for the Edge Clique Partitioning problem on fuzzy graphs. Using ( k, r ) as parameters, where k bounds the size of the partition, and r is the minimum number of vertices required to cover the undecided edges, we describe a polynomial-time kernelization to a problem kernel on O ( k 4 ·3 r ) vertices. This implies fixed-parameter tractability for this parameterization. Furthermore we also show that parameterizing only by the number of cliques k, is not enough to obtain fixed-parameter tractability. The problem remains, in fact, NP-hard for each fixed k > 2.

TCS Journal 2005 Journal Article

Equitable colorings of bounded treewidth graphs

• Hans L. Bodlaender
• Fedor V. Fomin

A proper coloring of a graph G is equitable if the sizes of any two color classes differ by at most one. A proper coloring is ℓ -bounded, when each color class has size at most ℓ. We consider the problems to determine for a given graph G (and a given integer ℓ ) whether G has an equitable ( ℓ -bounded) k -coloring. We prove that both problems can be solved in polynomial time on graphs of bounded treewidth, and show that a precolored version remains NP-complete on trees.

TCS Journal 2005 Journal Article

On algorithms for ( P 5,gem)-free graphs

• Hans L. Bodlaender
• Andreas Brandstädt
• Dieter Kratsch
• Michaël Rao
• Jeremy Spinrad

A graph is ( P 5, gem)-free, when it does not contain P 5 (an induced path with five vertices) or a gem (a graph formed by making an universal vertex adjacent to each of the four vertices of the induced path P 4 ) as an induced subgraph. We present O ( n 2 ) time recognition algorithms for chordal gem-free graphs and for ( P 5, gem)-free graphs. Using a characterization of ( P 5, gem)-free graphs by their prime graphs with respect to modular decomposition and their modular decomposition trees [A. Brandstädt, D. Kratsch, On the structure of ( P 5, gem)-free graphs, Discrete Appl. Math. 145 (2005), 155–166], we give linear time algorithms for the following NP-complete problems on ( P 5, gem)-free graphs: Minimum Coloring; Maximum Weight Stable Set; Maximum Weight Clique; and Minimum Clique Cover.

SODA Conference 2005 Conference Paper

Online topological ordering

• Irit Katriel
• Hans L. Bodlaender

MFCS Conference 2004 Conference Paper

Equitable Colorings of Bounded Treewidth Graphs

• Hans L. Bodlaender
• Fedor V. Fomin

Abstract A proper coloring of a graph G is equitable if the sizes of any two color classes differ by at most one. A proper coloring is ℓ-bounded, when each color class has size at most ℓ. We consider the problems to determine for a given graph G (and a given integer ℓ) whether G has an equitable (ℓ-bounded) k -coloring. We prove that both problems can be solved in polynomial time on graphs of bounded treewidth, and show that a precolored version remains NP-complete on trees.

UAI Conference 2004 Conference Paper

Monotonicity in Bayesian Networks

• Linda C. van der Gaag
• Hans L. Bodlaender
• Ad Feelders

For many real-life Bayesian networks, common knowledge dictates that the output established for the main variable of interest increases with higher values for the observable variables. We define two concepts of monotonicity to capture this type of knowledge. We say that a network is isotone in distribution if the probability distribution computed for the output variable given specific observations is stochastically dominated by any such distribution given higher-ordered observations; a network is isotone in mode if a probability distribution given higher observations has a higher mode. We show that establishing whether a network exhibits any of these properties of monotonicity is coNPPP-complete in general, and remains coNP-complete for polytrees. We present an approximate algorithm for deciding whether a network is monotone in distribution and illustrate its application to a real-life network in oncology.

MFCS Conference 2003 Conference Paper

Starting with Nondeterminism: The Systematic Derivation of Linear-Time Graph Layout Algorithms

• Hans L. Bodlaender
• Michael R. Fellows
• Dimitrios M. Thilikos

Abstract This paper investigates algorithms for some related graph parameters. Each asks for a linear ordering of the vertices of the graph (or can be formulated as such), and there are constructive linear time algorithms for the fixed parameter versions of the problems. Examples are cutwidth, pathwidth, and directed or weighted variants of these. However, these algorithms have complicated technical details. This paper attempts to present these algorithms in a different more easily accessible manner, by showing that the algorithms can be obtained by a stepwise modification of a trivial hypothetical non-deterministic algorithm. The methodology is applied for a generalisation of the cutwidth problem to weighted mixed graphs. As a consequence, we obtain new algorithmic results for various problems like modified cutwidth, and rederive known results for other related problems with simpler proofs.

ECAI Conference 2002 Conference Paper

On the Complexity of the MPA Problem in Probabilistic Networks

• Hans L. Bodlaender
• Frank van den Eijkhof
• Linda C. van der Gaag

UAI Conference 2001 Conference Paper

Pre-processing for Triangulation of Probabilistic Networks

• Hans L. Bodlaender
• Arie M. C. A. Koster
• Frank van den Eijkhof
• Linda C. van der Gaag

TCS Journal 2000 Journal Article

The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs

• Hans L. Bodlaender
• Michael R. Fellows
• Michael T. Hallett
• H.Todd Wareham
• Tandy J. Warnow

In this paper, we consider the complexity of a number of combinatorial problems; namely, Intervalizing Colored Graphs (DNA physical mapping), Triangulating Colored Graphs (perfect phylogeny), (Directed) (Modified) Colored Cutwidth, Feasible Register Assignment and Module Allocation for graphs of bounded pathwidth. Each of these problems has as a characteristic a uniform upper bound on the tree or path width of the graphs in “yes”-instances. For all of these problems with the exceptions of Feasible Register Assignment and Module Allocation, a vertex or edge coloring is given as part of the input. Our main results are that the parameterized variant of each of the considered problems is hard for the complexity classes W[t] for all t∈ N. We also show that Intervalizing Colored Graphs, Triangulating Colored Graphs, and Colored Cutwidth are NP-Complete.

TCS Journal 1998 Journal Article

A partial k-arboretum of graphs with bounded treewidth

• Hans L. Bodlaender

The notion of treewidth has seen to be a powerful vehicle for many graph algorithmic studies. This survey paper wants to give an overview of many classes of graphs that can be seen to have a uniform upper bound on the treewidth of graphs in the class. Also, some mutual relations between such classes are discussed.

SODA Conference 1998 Conference Paper

Linear-Time Register Allocation for a Fixed Number of Registers

• Hans L. Bodlaender
• Jens Gustedt
• Jan Arne Telle

MFCS Conference 1998 Conference Paper

Tree Decompositions of Small Diameter

• Hans L. Bodlaender
• Torben Hagerup

Abstract Motivated by applications in parallel and dynamic graph algorithms, we investigate the tradeoff between width and diameter of tree decompositions. For all integers n, k and K with 1 ≤ k ≤ K ≤ n − 1, denote by D(n, k, K) the maximum, over all n -vertex graphs G of treewidth k, of the smallest diameter of a tree decomposition of G of width K. We determine D(n, k, K), up to a constant factor, for all values of n, k and K. When K is bounded by a constant (the case of greatest practical relevance), D(n, k, K) is θ(n) for K ≤ 2 k -1, θ(√n) for 2 k ≤ K ≤ 3 k −2, and θ(log n ) for K ≥ 3 k −1. We provide much more accurate bounds for the case K ≤ 2 k −1.

I&C Journal 1997 Journal Article

On Interval Routing Schemes and Treewidth

• Hans L. Bodlaender
• Jan van Leeuwen
• Richard Tan
• Dimitrios M. Thilikos

In this paper, we investigate which processor networks allowk-label Interval Routing Schemes, under the assumption that costs of edges may vary. We show that for each fixedk⩾1, the class of graphs allowing such routing schemes is closed under minor-taking in the domain of connected graphs, and hence has a linear time recognition algorithm. This result connects the theory of compact routing with the theory of graph minors and treewidth. We show that every graph that does not containK 2, :r as a minor has treewidth at most 2r−2. As a consequence, graphs that allowk-label Interval Routing Schemes under dynamic cost edges have treewidth at most 4k. Similar results are shown for other types of Interval Routing Schemes.

MFCS Conference 1997 Invited Paper

Treewidth: Algorithmic Techniques and Results

• Hans L. Bodlaender

Abstract This paper gives an overview of several results and techniques for graphs algorithms that compute the treewidth of a graph or that solve otherwise intractable problems when restricted graphs with bounded treewidth more efficiently. Also, several results on graph minors are reviewed.

I&C Journal 1997 Journal Article

Triangulating Planar Graphs While Minimizing the Maximum Degree

• Goos Kant
• Hans L. Bodlaender

In this paper we consider the problem how to augment a planar graph to a triangulated planar graph while minimizing the maximum degree increase. We show that the general problem is NP-complete for bi-connected planar graphs. An approximation algorithm is presented to triangulate triconnected planar graphs such that the maximum degree of the triangulation is at mostd+8, wheredis the maximum degree of the input graph. Generalizing this result yields a triangulation algorithm for general planar graphs with maximum degree at most an additional constant larger than existing lower bounds.

TCS Journal 1995 Journal Article

Restrictions of graph partition problems. Part I

• Hans L. Bodlaender
• Klaus Jansen

In this paper partition problems into k independent sets or cliques of bounded size k′ are analyzed for several classes of graphs. We prove the computational complexity of both problems restricted to cographs, split graphs, bipartite graphs and interval graphs given general or constant k and k′. It is shown, that the assignment problem for operations in a branching flow graph to processors, each with a limit on the number of executable operations, equals the first problem restricted to cographs. In addition a job-assignment problem given intervals for each job and k machines, each executing at most k′ jobs, equals the first problem restricted to interval graphs. It is shown, that both problem are NP-complete.

TCS Journal 1995 Journal Article

The parameterized complexity of sequence alignment and consensus

• Hans L. Bodlaender
• Rodney G. Downey
• Michael R. Fellows
• Harold T. Wareham

The longest common subsequence problem is examined from the point of view of parameterized computational complexity. There are several different ways in which parameters enter the problem, such as the number of sequences to be analyzed, the length of the common subsequence, and the size of the alphabet. Lower bounds on the complexity of this basic problem imply lower bounds on a number of other sequence alignment and consensus problems. An issue in the theory of parameterized complexity is whether a problem which takes input (x, k) can be solved in time ƒ(k) · nα where α is independent of k (termed fixed-parameter tractability). It can be argued that this is the appropriate asymptotic model of feasible computability for problems for which a small range of parameter values covers important applications — a situation which certainly holds for many problems in biological sequence analysis. Our main results show that: 1. (1) The longest common subsequence (LCS) parameterized by the number of sequences to be analyzed is hard for W[t] for all t. 2. (2) The LCS problem, parameterized by the length of the common subsequence, belongs to W[P] and is hard for W[2]. 3. (3) The LCS problem parameterized both by the number of sequences and the length of the common subsequence, is complete for W[1]. All of the above results are obtained for unrestricted alphabet sizes. For alphabets of a fixed size, problems (2) and (3) are fixed-parameter tractable. We conjecture that (1) remains hard.

STOC Conference 1994 Conference Paper

Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy

• Hans L. Bodlaender
• Michael R. Fellows
• Michael T. Hallett

STOC Conference 1993 Conference Paper

A linear time algorithm for finding tree-decompositions of small treewidth

• Hans L. Bodlaender

TCS Journal 1993 Journal Article

Complexity of path-forming games

• Hans L. Bodlaender

For a number of two-player games where players alternately choose the next vertex of a simple or an elementary path in a graph, we consider the problem to determine whether, for a given game instance, there is a winning strategy for the first player. We show several of these problems to be PSPACE-complete. In some special cases, we obtain polynomial-time algorithms, based on graph rewriting or an intricate form of dynamic programming, e. g. we show GENERALIZED GEOGRAPHY and some other PSPACE-complete problems to be linear-time-solvable on graphs with constant bounded treewidth.

MFCS Conference 1993 Conference Paper

On the Complexity of Scheduling Incompatible Jobs with Unit-Times

• Hans L. Bodlaender
• Klaus Jansen

Abstract We consider scheduling problems in a multiprocessor system with incompatibile jobs of unit-time length where two incompatible jobs can not be processed on the same machine. Given a deadline κ′ and a number of κ machines, the problem is to find a feasible assignment of the jobs to the machines. We prove the computational complexity of this scheduling problem restricted to different graph classes, arbitary and constant numbers κ and κ′.

TCS Journal 1992 Journal Article

The complexity of coloring games on perfect graphs

• Hans L. Bodlaender
• Dieter Kratsch

In this paper we consider the following type of game: two players must color the vertices of a given graph G = (V, E), in a prescribed order, in such a way that no two adjacent vertices are colored with the same color. In one variant, the first player which is unable to move loses the game. In another variant, player 1 wins the game, if and only if the game ends with all vertices colored. In this paper, we obtain several results on the complexity of the problem to decide whether there is a winning strategy for player 1 in a given game instance, when G is restricted to split graphs, interval graphs, or bipartite graphs.

I&C Journal 1990 Journal Article

The complexity of finding uniform emulations on paths and ring networks

• Hans L. Bodlaender

Uniform emulations are a method to obtain efficient, balanced simulations of large processor networks (guests) on smaller processor networks (hosts). Each uniform emulation has associated with it a constant c, called the computation factor, which is the size of the guest network divided by the size of the host network. In this paper we prove that the problem to decide whether a given connected graph (guest network) G can be uniformly emulated on a path or a ring network is NP-complete, even if G is required to be a binary tree. If the computation factor c is fixed, then these problems become solvable in polynomial time for arbitrary connected graphs G. However, if we keep the computation factor fixed at at least 4 or 2 for the path- or ring-version, respectively, but allow disconnected graphs G, then the problem again is NP-complete. Similar results are shown for directed graphs.