Time table of all LIRMM seminars

Barnette’s Conjecture claims that all cubic, 3-connected, planar, bipartite graphs are Hamiltonian. We give a translation of this conjecture into the matching-theoretic setting. This allows us to relax the requirement of planarity to give the equivalent conjecture that all cubic, 3-connected, Pfaffian, bipartite graphs are Hamiltonian.

A graph is a brace if it is bipartite and any two disjoint edges are part of a perfect matching. Our perspective allows us to observe that Barnette’s Conjecture can be reduced to cubic, planar braces. We show a similar reduction to braces for cubic, 3-connected, bipartite graphs regarding four stronger versions of Hamiltonicity. Note that in these cases we do not need planarity. As a practical application of these results, we provide some supplements to a generation procedure for cubic, 3-connected, planar, bipartite graphs discovered by Holton et al. [Hamiltonian Cycles in Cubic 3-Connected Bipartite Planar Graphs, JCTB, 1985]. These allow us to check whether a graph we generated is a brace.

Joint work with Sebastian Wiederrecht und Raphael Steiner.

Le problème de recouvrement de graphes supposant des bornes de degré hétérogènes sur des nœuds est l’objet de cette présentation. Les bornes représentent des capacités momentanées limitées des nœuds. Nous donnons la formulation exacte de la structure couvrante connexe à coût minimum satisfaisant les contraintes qui est une hiérarchie. Le problème est NP-difficile et la solution n’existe pas toujours. Les conditions nécessaires et suffisantes pour l’existence de la hiérarchie couvrante sont alors présentées. Dans certains cas, la solution peut être approchée et un algorithme est aussi proposé.

We introduce a logic called distance neighborhood logic with acyclicity and connectivity constraints (A&C DN for short) which extends existential MSO1 with predicates for querying neighborhoods of vertex sets and for verifying connectivity and acyclicity of vertex sets in various powers of a graph. Building upon [Bergougnoux and Kanté, ESA 2019; SIDMA 2021], we show that the model checking problem for every fixed A&C DN formula is solvable in n^O(w) time when the input graph is given together with a branch decomposition of mim-width w. Nearly all problems that are known to be solvable in polynomial time given a branch decomposition of constant mim-width can be expressed in this framework. We add several natural problems to this list, including problems asking for diverse sets of solutions.

Our model checking algorithm is efficient whenever the given branch decomposition of the input graph has small index in terms of the d-neighborhood equivalence [Bui-Xuan, Telle, and Vatshelle, TCS 2013]. We therefore unify and extend known algorithms for tree-width, clique-width and rank-width. Our algorithm has a single-exponential dependence on these three width measures and asymptotically matches run times of the fastest known algorithms for several problems. This results in algorithms with tight run times under the Exponential Time Hypothesis (ETH) for tree-width and clique-width; the above mentioned run time for mim-width is nearly tight under the ETH for several problems as well. Our results are also tight in terms of the expressive power of the logic: we show that already slight extensions of our logic make the model checking problem para-NP-hard when parameterized by mim-width plus formula length.

Joint work with Benjamin Bergougnoux and Jan Dreier.

Two boxes in $\mathbb{R}^d$ are comparable if one of them is a subset
of a translation of the other. The comparable box dimension of a graph
$G$ is the minimum integer $d$ such that $G$ can be represented as a
touching graph of comparable axis-aligned boxes in $\mathbb{R}^d$. We
show that proper minor-closed classes have bounded comparable box
dimension and explore further properties of this notion. In particular we show that graphs with bounded comparable box dimension are treewidth fragile.

Joint work with Z. Dvořák, Abhiruk Lahiri, Jane Tan, and Torsten Ueckerdt

Robust optimization is one of the most popular methods to tackle optimization problems under uncertainty. In this approach we assume that all possible outcomes of the uncertain parameters are contained in a given uncertainty set and the task is to find solutions which are worst-case optimal under all these scenarios.

In the first part of this talk we study optimization problems under uncertainty which contain a two-stage structure and apply the two-stage robust optimization approach with discrete uncertainty. Two-stage robust problems can be solved by so called column-and-constraint algorithms where iteratively new variables and constraints are generated. Unfortunately solving these problems is computationally very demanding, especially if the second-stage variables are integer. In our work we propose a data-driven heuristic to determine a set of starting scenarios that provide strong lower bounds early in the iterative process. We learn the relevance of scenarios by extracting information from training data using a combined similarity measure between robust problem instances and single scenarios. Our experiments show that predicting even a small number of good start scenarios can considerably reduce the computation time.

In the second part of this talk we consider the problem of constructing uncertainty sets for robust optimization from historic data. We propose to train deep neural networks on historic data to exclude outliers and extract hidden structures in the data which leads to uncertainty sets which have a more complex structure than the ones constructed by previous approaches. We show that the trained neural networks can be integrated into a robust optimization model by formulating the adversarial problem as a convex quadratic mixed-integer program. Our computations show that our uncertainty sets lead to robust solutions that often outperform the comparison methods both with respect to objective value and feasibility.

Note: this is a zoom seminar, the link will be communicated later.

We study the approximability of covering problems when the set of
items chosen to satisfy the covering constraints must be a prefix of a
given partial order. We examine the general case with multiplicity
constraints, where item $i$ can be chosen up to $d_i$ times. For the
basic Precedence-Constrained Knapsack problem (PCKP) we answer an open
question of McCormick et al. and show the existence of approximation
algorithms with strongly-polynomial bounds.

PCKP is a special case, with a single covering constraint, of a
Precedence-Constrained Covering Integer Program (PCCP). For a general
PCCP where the number of covering constraints is $m \geq 1,$ we show
that an algorithm of Pritchard and Chakrabarty for Covering Integer
Programs can be extended to yield an $f$-approximation, where $f$ is
the maximum number of variables with nonzero coefficients in a
covering constraint. This is nearly-optimal under standard
complexity-theoretic assumptions and rather surprisingly matches the
bound known for the problem without precedence constraints.

Joint work with Antonis Skarlatos.

TBA