Author name cluster

Mathieu Liedloff

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

13 papers

2 author rows

TCS Journal 2019 Journal Article

Enumeration and maximum number of minimal dominating sets for chordal graphs

Petr A. Golovach
Dieter Kratsch
Mathieu Liedloff
Mohamed Yosri Sayadi

We study the enumeration of the minimal dominating sets and upper bounds for the number of such sets in chordal graphs. We show that the maximum number of minimal dominating sets of an n-vertex chordal graph is at most 1. 5048 n and prove that these sets can be enumerated in time O ( 1. 5048 n ). In this way we improve the previous upper bound of 1. 5214 n, recently established by Abu-Khzam and Heggernes, and narrow the gap between the upper bound and the known lower bound of 1. 4422 n.

Details DOI

TCS Journal 2018 Journal Article

Fixing improper colorings of graphs

Valentin Garnero
Konstanty Junosza-Szaniawski
Mathieu Liedloff
Pedro Montealegre
Paweł Rzążewski

In this paper we consider a variation of a recoloring problem, called the Color-Fixing. Let us have some non-proper r-coloring φ of a graph G. We investigate the problem of finding a proper r-coloring of G, which is “the most similar” to φ, i. e. , the number k of vertices that have to be recolored is minimum possible. We observe that the problem is NP-complete for any fixed r ≥ 3, even for bipartite planar graphs. Moreover, it is W [ 1 ] -hard even for bipartite graphs, when parameterized by the number k of allowed recoloring transformations. On the other hand, the problem is fixed-parameter tractable, when parameterized by k and the number r of colors. We provide a 2 n ⋅ n O ( 1 ) algorithm for the problem and a linear algorithm for graphs with bounded treewidth. We also show several lower complexity bounds, using standard complexity assumptions. Finally, we investigate the fixing number of a graph G. It is the minimum k such that k recoloring transformations are sufficient to transform any coloring of G into a proper one.

Details DOI

TCS Journal 2018 Journal Article

The many facets of upper domination

Cristina Bazgan
Ljiljana Brankovic
Katrin Casel
Henning Fernau
Klaus Jansen
Kim-Manuel Klein
Michael Lampis
Mathieu Liedloff

This paper studies Upper Domination, i. e. , the problem of computing the maximum cardinality of a minimal dominating set in a graph with respect to classical and parameterised complexity as well as approximability.

Details DOI

TCS Journal 2017 Journal Article

Exact exponential algorithms to find tropical connected sets of minimum size

Mathieu Chapelle
Manfred Cochefert
Dieter Kratsch
Romain Letourneur
Mathieu Liedloff

Tropical Connected Set is strongly related to the Graph Motif problem which deals with vertex-colored graphs. Graph Motif has various applications in biology and metabolic networks, and has widely been studied in the last twenty years. The input of the Tropical Connected Set problem is a vertex-colored graph ( G, c ), where G = ( V, E ) is a graph and c is a vertex coloring assigning to each vertex of G a color. The task is to find a connected subset S ⊆ V of minimum size such that each color of G appears in S. This problem is known to be NP-complete, even when restricted to trees of height at most three. We study exact exponential algorithms to solve Tropical Connected Set. We present an O ⁎ ( 1. 5359 n ) time algorithm for general graphs and an O ⁎ ( 1. 2721 n ) time algorithm for trees. We also show that Tropical Connected Set on trees has no sub-exponential algorithm unless the Exponential Time Hypothesis fails.

Details DOI

TCS Journal 2015 Journal Article

On finding optimal polytrees

Serge Gaspers
Mikko Koivisto
Mathieu Liedloff
Sebastian Ordyniak
Stefan Szeider

We study the NP-hard problem of finding a directed acyclic graph (DAG) on a given set of nodes so as to maximize a given scoring function. The problem models the task of inferring a probabilistic network from data, which has been studied extensively in the fields of artificial intelligence and machine learning. Several variants of the problem, where the output DAG is constrained in several ways, are NP-hard as well, for example when the DAG is required to have bounded in-degree, or when it is required to be a polytree. Polynomial-time algorithms are known only for rare special cases, perhaps most notably for branchings, that is, polytrees in which the in-degree of every node is at most one. In this paper, we generalize this polynomial-time result to polytrees that can be turned into a branching by deleting a constant number of arcs. Our algorithm stems from a matroid intersection formulation. As the order of the polynomial time bound depends on the number of deleted arcs, the algorithm does not establish fixed-parameter tractability when parameterized by that number. We show that certain additional constraints on the sought polytree render the problem fixed-parameter tractable. We contrast this positive result by showing that if we parameterize by the number of deleted nodes, a somewhat more powerful parameter, the problem is not fixed-parameter tractable, subject to a complexity-theoretic assumption.

Details DOI

TCS Journal 2015 Journal Article

On the number of minimal dominating sets on some graph classes

Jean-François Couturier
Romain Letourneur
Mathieu Liedloff

A dominating set in a graph is a subset of vertices such that each vertex is either in the dominating set or adjacent to some vertex in the dominating set. It is known that graphs have at most O ( 1. 7159 n ) minimal dominating sets. In this paper, we establish upper bounds on this maximum number of minimal dominating sets for split graphs, cobipartite graphs and interval graphs. For each of these graph classes, we provide an algorithm to enumerate them. For split and interval graphs, we show that the number of minimal dominating sets is at most 3 n / 3 ≈ 1. 4423 n, which is the best possible bound. This settles a conjecture by Couturier et al. (SOFSEM 2012, [1]). For cobipartite graphs, we lower the O ( 1. 5875 n ) upper bound from Couturier et al. to O ( 1. 4511 n ).

Details DOI

TCS Journal 2013 Journal Article

Fast exact algorithm for L ( 2, 1 ) -labeling of graphs

Konstanty Junosza-Szaniawski
Jan Kratochvíl
Mathieu Liedloff
Peter Rossmanith
Paweł Rzążewski

An L ( 2, 1 ) -labeling of a graph is a mapping from its vertex set into nonnegative integers such that the labels assigned to adjacent vertices differ by at least 2, and labels assigned to vertices of distance 2 are different. The span of such a labeling is the maximum label used, and the L ( 2, 1 ) -span of a graph is the minimum possible span of its L ( 2, 1 ) -labelings. We show how to compute the L ( 2, 1 ) -span of a connected graph in time O ∗ ( 2. 648 8 n ). Previously published exact exponential time algorithms were gradually improving the base of the exponential function from 4 to the so far best known 3, with 3 itself seemingly having been the Holy Grail for quite a while. As concerns special graph classes, we are able to solve the problem in time O ∗ ( 2. 594 4 n ) for claw-free graphs, and in time O ∗ ( 2 n − r ( 2 + n r ) r ) for graphs having a dominating set of size r.

Details DOI

AAAI Conference 2012 Conference Paper

On Finding Optimal Polytrees

Serge Gaspers
Mikko Koivisto
Mathieu Liedloff
Sebastian Ordyniak
Stefan Szeider

Inferring probabilistic networks from data is a notoriously difficult task. Under various goodness-of-fit measures, finding an optimal network is NP-hard, even if restricted to polytrees of bounded in-degree. Polynomial-time algorithms are known only for rare special cases, perhaps most notably for branchings, that is, polytrees in which the in-degree of every node is at most one. Here, we study the complexity of finding an optimal polytree that can be turned into a branching by deleting some number of arcs or nodes, treated as a parameter. We show that the problem can be solved via a matroid intersection formulation in polynomial time if the number of deleted arcs is bounded by a constant. The order of the polynomial time bound depends on this constant, hence the algorithm does not establish fixed-parameter tractability when parameterized by the number of deleted arcs. We show that a restricted version of the problem allows fixed-parameter tractability and hence scales well with the parameter. We contrast this positive result by showing that if we parameterize by the number of deleted nodes, a somewhat more powerful parameter, the problem is not fixed-parameter tractable, subject to a complexity-theoretic assumption.

PDF Details

TCS Journal 2011 Journal Article

An exact algorithm for the Maximum Leaf Spanning Tree problem

Henning Fernau
Joachim Kneis
Dieter Kratsch
Alexander Langer
Mathieu Liedloff
Daniel Raible
Peter Rossmanith

Given an undirected graph with n vertices, the Maximum Leaf Spanning Tree problem is to find a spanning tree with as many leaves as possible. When parameterized in the number of leaves k, this problem can be solved in time O ( 4 k poly ( n ) ) using a simple branching algorithm introduced by a subset of the authors (Kneis et al. 2008 [16]). Daligault et al. (2010) [6] improved the branching and obtained a running time of O ( 3. 7 2 k poly ( n ) ). In this paper, we study the problem from an exponential time viewpoint, where it is equivalent to the Connected Dominating Set problem. Here, Fomin, Grandoni, and Kratsch showed how to break the Ω ( 2 n ) barrier and proposed an O ( 1. 940 7 n ) -time algorithm (Fomin et al. 2008 [11]). Based on some useful properties of Kneis et al. (2008) [16] and Daligault et al. (2010) [6], we present a branching algorithm whose running time of O ( 1. 896 6 n ) has been analyzed using the Measure-and-Conquer technique. Finally, we provide a lower bound of Ω ( 1. 442 2 n ) for the worst case running time of our algorithm.

Details DOI

TCS Journal 2010 Journal Article

Iterative compression and exact algorithms

Fedor V. Fomin
Serge Gaspers
Dieter Kratsch
Mathieu Liedloff
Saket Saurabh

Iterative compression has recently led to a number of breakthroughs in parameterized complexity. Here, we show that the technique can also be useful in the design of exact exponential time algorithms to solve NP-hard problems. We exemplify our findings with algorithms for the Maximum Independent Set problem, a parameterized and a counting version of d -Hitting Set and the Maximum Induced Cluster Subgraph problem.

Details DOI

MFCS Conference 2008 Conference Paper

Iterative Compression and Exact Algorithms

Fedor V. Fomin
Serge Gaspers
Dieter Kratsch
Mathieu Liedloff
Saket Saurabh 0001

Abstract Iterative Compression has recently led to a number of breakthroughs in parameterized complexity. The main purpose of this paper is to show that iterative compression can also be used in the design of exact exponential time algorithms. We exemplify our findings with algorithms for the Maximum Independent Set problem, a counting version of k - Hitting Set and the Maximum Induced Cluster Subgraph problem.

Details

TCS Journal 2007 Journal Article

An exact algorithm for the minimum dominating clique problem

Dieter Kratsch
Mathieu Liedloff

A subset of vertices D ⊆ V of a graph G = ( V, E ) is a dominating clique if D is a dominating set and a clique of G. The existence problem ‘Given a graph G, is there a dominating clique in G? ’ is NP-complete, and thus both the Minimum and the Maximum Dominating Clique problems are NP-hard. We present an O ( 1. 338 7 n ) time and polynomial space algorithm that for an input graph on n vertices either computes a minimum dominating clique or reports that the graph has no dominating clique. The algorithm uses the Branch & Reduce paradigm and its time analysis is based on the Measure & Conquer approach. We also establish a lower bound of Ω ( 1. 259 9 n ) for the worst case running time of the algorithm. Finally using memorization we obtain an O ( 1. 323 4 n ) time and exponential space algorithm for the same problem.

Details DOI

MFCS Conference 2007 Conference Paper

Exact Algorithms for L (2, 1)-Labeling of Graphs

Jan Kratochvíl
Dieter Kratsch
Mathieu Liedloff

Abstract The notion of distance constrained graph labelings, motivated by the Frequency Assignment Problem, reads as follows: A mapping from the vertex set of a graph G = ( V, E ) into an interval of integers [0. . k ] is an L (2, 1)-labeling of G of span k if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices with a common neighbor are mapped onto distinct integers. It is known that for any fixed k ≥ 4, deciding the existence of such a labeling is an NP-complete problem. We present exact exponential time algorithms that are faster than the naive O (( k + 1) n ) algorithm that would try all possible mappings. The improvement is best seen in the first NP-complete case of k = 4 – here the running time of our algorithm is O (1. 3161 n ).

Details