135 citations · 211 across the 20 of their papers we have counts for
24 papers
The tree-child network problem for line trees and the shortest common supersequences for permutations
Laurent Bulteau, Louxin Zhang
One strategy for reconstruction of phylogenetic networks is to solve the phylogenetic network problem, which involves inferring phylogenetic trees first and subsequently computing…
Better Collective Decisions via Uncertainty Reduction
Shiri Alouf-Heffetz, Laurent Bulteau, Edith Elkind +2
We consider an agent community wishing to decide on several binary issues by means of issue-by-issue majority voting. For each issue and each agent, one of the two options is bette…
2-Dimensional Euclidean Preferences
Laurent Bulteau, Jiehua Chen
A preference profile with m alternatives and n voters is 2-dimensional Euclidean if both the alternatives and the voters can be placed into a 2-dimensional space such that for each…
An Algorithmic Framework for Locally Constrained Homomorphisms
Laurent Bulteau, Konrad K. Dabrowski, Noleen Köhler +2
A homomorphism from a guest graph to a host graph is locally bijective, injective or surjective if for every , the restriction of to the neighbourhood of…
Parameterized String Equations
Laurent Bulteau, Michael R. Fellows, Christian Komusiewicz +1
We study systems of String Equations where block variables need to be assigned strings so that their concatenation gives a specified target string. We investigate this problem unde…
Your Rugby Mates Don't Need to Know your Colleagues: Triadic Closure with Edge Colors
Laurent Bulteau, Niels Grüttemeier, Christian Komusiewicz +1
Given an undirected graph the NP-hard Strong Triadic Closure (STC) problem asks for a labeling of the edges as \emph{weak} and \emph{strong} such that at most edges a…
Finding a Small Number of Colourful Components
Laurent Bulteau, Konrad K. Dabrowski, Guillaume Fertin +3
A partition of the vertex set of a graph with a (not necessarily proper) colouring is colourful if no two vertices in any have the same colour and…
Aggregation over Metric Spaces: Proposing and Voting in Elections, Budgeting, and Legislation
Laurent Bulteau, Gal Shahaf, Ehud Shapiro +1
We present a unifying framework encompassing many social choice settings. Viewing each social choice setting as voting in a suitable metric space, we consider a general model of so…
Tight Hardness Results for Consensus Problems on Circular Strings and Time Series
Laurent Bulteau, Vincent Froese, Rolf Niedermeier
Consensus problems for strings and sequences appear in numerous application contexts, ranging from bioinformatics over data mining to machine learning. Closing some gaps in the lit…
The Clever Shopper Problem
Laurent Bulteau, Danny Hermelin, Anthony Labarre +1
We investigate a variant of the so-called "Internet Shopping Problem" introduced by Blazewicz et al. (2010), where a customer wants to buy a list of products at the lowest possible…
Consensus Patterns parameterized by input string length is W[1]-hard
Laurent Bulteau
We consider the Consensus Patterns problem, where, given a set of input strings, one is asked to extract a long-enough pattern which appears (with some errors) in all strings. We p…
Precedence-constrained scheduling problems parameterized by partial order width
René van Bevern, Robert Bredereck, Laurent Bulteau +3
Negatively answering a question posed by Mnich and Wiese (Math. Program. 154(1-2):533-562), we show that P2|prec,|, the problem of finding a non-preempti…
Decomposing Cubic Graphs into Connected Subgraphs of Size Three
Laurent Bulteau, Guillaume Fertin, Anthony Labarre +2
Let be the set of connected graphs of size 3. We study the problem of partitioning the edge set of a graph into graphs taken from any non-empty $S'\subs…
Co-Clustering Under the Maximum Norm
Laurent Bulteau, Vincent Froese, Sepp Hartung +1
Co-clustering, that is, partitioning a numerical matrix into homogeneous submatrices, has many applications ranging from bioinformatics to election analysis. Many interesting varia…
Multi-Player Diffusion Games on Graph Classes
Laurent Bulteau, Vincent Froese, Nimrod Talmon
We study competitive diffusion games on graphs introduced by Alon et al. [1] to model the spread of influence in social networks. Extending results of Roshanbin [8] for two players…
The Complexity of Finding Effectors
Laurent Bulteau, Stefan Fafianie, Vincent Froese +2
The NP-hard EFFECTORS problem on directed graphs is motivated by applications in network mining, particularly concerning the analysis of probabilistic information-propagation proce…
Computing an Evolutionary Ordering is Hard
Laurent Bulteau, Gustavo Sacomoto, Blerina Sinaimeri
We prove that computing an evolutionary ordering of a family of sets, i.e. an ordering where each set intersects with --but is not included in-- the union earlier sets, is NP-hard.
Combinatorial Voter Control in Elections
Laurent Bulteau, Jiehua Chen, Piotr Faliszewski +2
Voter control problems model situations such as an external agent trying to affect the result of an election by adding voters, for example by convincing some voters to vote who wou…
Triangle counting in dynamic graph streams
Laurent Bulteau, Vincent Froese, Konstantin Kutzkov +1
Estimating the number of triangles in graph streams using a limited amount of memory has become a popular topic in the last decade. Different variations of the problem have been st…
Partitioning Perfect Graphs into Stars
René van Bevern, Robert Bredereck, Laurent Bulteau +4
The partition of graphs into "nice" subgraphs is a central algorithmic problem with strong ties to matching theory. We study the partitioning of undirected graphs into same-size st…
A Fixed-Parameter Algorithm for Minimum Common String Partition with Few Duplications
Laurent Bulteau, Guillaume Fertin, Christian Komusiewicz +1
Motivated by the study of genome rearrangements, the NP-hard Minimum Common String Partition problems asks, given two strings, to split both strings into an identical set of blocks…
Minimum Common String Partition Parameterized by Partition Size is Fixed-Parameter Tractable
Laurent Bulteau, Christian Komusiewicz
The NP-hard Minimum Common String Partition problem asks whether two strings and can each be partitioned into at most substrings, called blocks, such that both partitio…
Pancake Flipping is Hard
Laurent Bulteau, Guillaume Fertin, Irena Rusu
Pancake Flipping is the problem of sorting a stack of pancakes of different sizes (that is, a permutation), when the only allowed operation is to insert a spatula anywhere in the s…
Sorting by Transpositions is Difficult
Laurent Bulteau, Guillaume Fertin, Irena Rusu
In comparative genomics, a transposition is an operation that exchanges two consecutive sequences of genes in a genome. The transposition distance, that is, the minimum number of t…