About
I am a postdoc at the Faculty of Mathematics, Informatics and Natural Sciences at University of Primorska, Koper, Slovenia. I completed my PhD in September 2019 at the University of Portsmouth, UK.
My research interests mostly lie within the fields of structural and algorithmic graph theory.
Publications
2021

“Tree decompositions with bounded independence number and their algorithmic applications.”C. Dallard, M. Milanič, and K. Štorgel.Available on arXiv only.
In 2020, Dallard, Milanič, and Štorgel initiated a systematic study of graph classes in which the treewidth can only be large due the presence of a large clique, which they call $(tw,ω)$bounded. The family of $(tw,ω)$bounded graph classes provides a unifying framework for a variety of very different families of graph classes, including graph classes of bounded treewidth, graph classes of bounded independence number, intersection graphs of connected subgraphs of graphs with bounded treewidth, and graphs in which all minimal separators are of bounded size. While Chaplick and Zeman showed in 2017 that $(tw,ω)$bounded graph classes enjoy some good algorithmic properties related to clique and coloring problems, an interesting open problem is whether $(tw,ω)$boundedness has useful algorithmic implications for problems related to independent sets. We provide a partial answer to this question by identifying a sufficient condition for $(tw,ω)$bounded graph classes to admit a polynomialtime algorithm for the Maximum Weight Independent $\mathcal{H}$Packing problem, for any fixed finite set $\mathcal{H}$ of connected graphs. This family of problems generalizes several other problems studied in the literature, including the Maximum Weight Independent Set and Maximum Weight Induced Matching problems. Our approach is based on a new minmax graph parameter related to tree decompositions. We define the independence number of a tree decomposition $\mathcal{T}$ of a graph as the maximum independence number over all subgraphs of $G$ induced by some bag of $\mathcal{T}$. The treeindependence number of a graph $G$ is then defined as the minimum independence number over all tree decompositions of $G$. Boundedness of the treeindependence number is a refinement of \hbox$(tw,ω)$boundedness that is still general enough to hold for all the aforementioned families of graph classes. We show that if a graph is given together with a tree decomposition with bounded independence number, then for any fixed finite set $\mathcal{H}$ of connected graphs, the Maximum Weight Independent $\mathcal{H}$Packing problem can be solved in polynomial time. Motivated by this result, we consider six graph containment relations—the subgraph, topological minor, and minor relations, as well as their induced variants—and for each of them characterize the graphs $H$ for which any graph excluding $H$ with respect to the relation admits a tree decomposition with bounded independence number. These results build on and refine the analogous characterizations due to Dallard, Milanič, and Štorgel for $(tw,ω)$boundedness, and shows that in all these cases, $(tw,ω)$boundedness is actually equivalent to bounded treeindependence number. We use a variety of tools including SPQR trees and potential maximal cliques, and show that in the bounded cases, one can also obtain tree decompositions with bounded independence number efficiently. This leads to polynomialtime algorithms for the Maximum Weight Independent Set problem in an infinite family of graph classes, each of which properly contains the class of chordal graphs. These results also apply to the class of $1$perfectly orientable graphs, answering a question of Beisegel, Chudnovsky, Gurvich, Milanič, and Servatius from 2019. 
“Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure.”C. Dallard, M. Milanič, and K. Štorgel.SIAM Journal on Discrete Mathematics, vol. 35, no. 4, pp. 2618–2646
Treewidth is an important graph invariant, relevant for both structural and algorithmic reasons. A necessary condition for a graph class to have bounded treewidth is the absence of large cliques. We study graph classes closed under taking induced subgraphs in which this condition is also sufficient, which we call $(tw,ω)$bounded. Such graph classes are known to have useful algorithmic applications related to variants of the clique and $k$coloring problems. We consider six wellknown graph containment relations: the minor, topological minor, subgraph, induced minor, induced topological minor, and induced subgraph relations. For each of them, we give a complete characterization of the graphs $H$ for which the class of graphs excluding $H$ is $(tw,ω)$bounded. Our results yield an infinite family of $χ$bounded inducedminorclosed graph classes and imply that the class of $1$perfectly orientable graphs is $(tw,ω)$bounded, leading to lineartime algorithms for $k$coloring $1$perfectly orientable graphs for every fixed $k$. This answers a question of Brešar, Hartinger, Kos, and Milanič from 2018, and one of Beisegel, Chudnovsky, Gurvich, Milanič, and Servatius from 2019, respectively. We also reveal some further algorithmic implications of $(tw,ω)$boundedness related to list $k$coloring and clique problems. In addition, we propose a question about the complexity of the Maximum Weight Independent Set problem in $(tw,ω)$bounded graph classes and prove that the problem is polynomialtime solvable in every class of graphs excluding a fixed star as an induced minor. 
“Colourful components in $k$caterpillars and planar graphs.”J. Chlebíková and C. Dallard.Theoretical Computer Science, vol. 895, pp. 137–150
A connected component of a vertexcoloured graph is said to be colourful if all its vertices have different colours. By extension, a graph is colourful if all its connected components are colourful. Given a vertexcoloured graph G and an integer p, the Colourful Components problem asks whether there exist at most p edges whose removal makes G colourful and the Colourful Partition problem asks whether there exists a partition of G into at most p colourful components. In order to refine our understanding of the complexity of the problems on trees, we study both problems on kcaterpillars, which are trees with a central path P such that every vertex not in P is within distance k from a vertex in P. We prove that Colourful Components and Colourful Partition are NPcomplete on 4caterpillars with maximum degree 3, 3caterpillars with maximum degree 4 and 2caterpillars with maximum degree 5. On the other hand, we show that the problems are lineartime solvable on 1caterpillars. Hence, our results imply two complexity dichotomies on trees: Colourful Components and Colourful Partition are lineartime solvable on trees with maximum degree d if d≤2 (that is, on paths), and NPcomplete otherwise; Colourful Components and Colourful Partition are lineartime solvable on kcaterpillars if k≤1, and NPcomplete otherwise. We leave three open cases which, if solved, would provide a complexity dichotomy for both problems on kcaterpillars, for every nonnegative integer k, with respect to the maximum degree. We also show that Colourful Components is NPcomplete on 5coloured planar graphs with maximum degree 4 and on 12coloured planar graphs with maximum degree 3. Our results answer two open questions of Bulteau et al. mentioned in [30th Annual Symposium on Combinatorial Pattern Matching, 2019]. 
“Allocating indivisible items with minimum dissatisfaction on preference graphs.”N. Chiarelli, C. Dallard, A. Darmann, S. Lendl, M. Milanič, P. Muršič, N. Pivač, and U. Pferschy.in 7th International Conference on Algorithmic Decision Theory
We consider the task of allocating indivisible items to agents, when each agent’s preferences are captured by means of a directed acyclic graph. The vertices of such a graph represent items and an arc $(a,b)$ means that the respective agent prefers item $a$ over item $b$. The dissatisfaction of an agent is measured by the number of nonassigned items which are desired by the agent and for which no more preferred item is given to the agent. The aim is to allocate the items to the agents in a way that minimizes (i) the total dissatisfaction over all agents, or (ii) the maximum dissatisfaction among the agents. For both problems we study the status of computational complexity and obtain NPhardness results as well as polynomial algorithms with respect to different underlying graph structures, such as trees, stars, paths, and matchings. 
“Vertex cover at distance on Hfree graphs.”C. Dallard, M. Krbezlija, and M. Milanič.in International Workshop on Combinatorial Algorithms, pp. 237–251
The question of characterizing graphs $H$ such that the vertex cover problem is solvable in polynomial time in the class of $H$free graphs is notoriously difficult and still widely open. We completely solve the corresponding question for a distancebased generalization of vertex cover called distance$k$ vertex cover, for any positive integer $k$. In this problem the task is to determine, given a graph $G$ and an integer $\ell$, whether $G$ contains a set of at most $\ell$ vertices such that each edge of $G$ is at distance at most $k$ from a vertex in the set. We show that for all $k \ge 1$ and all graphs $H$, the distance$k$ vertex cover problem is solvable in polynomial time in the class of $H$free graphs if $H$ is an induced subgraph of $P_{2k+2} + sP_{\max\{k,2\}}$ for some $s \ge 0$, and NPcomplete otherwise. 
“Graphs with two moplexes.”C. Dallard, R. Ganian, M. Hatzel, M. Krnc, and M. Milanič.in XI Latin and American Algorithms, Graphs and Optimization Symposium
A moplex is a natural graph structure that arises when lifting Dirac’s classical theorem from chordal graphs to general graphs. However, while every noncomplete graph has at least two moplexes, little is known about structural properties of graphs with a bounded number of moplexes. The study of these graphs is motivated by the parallel between moplexes in general graphs and simplicial modules in chordal graphs: Unlike in the moplex setting, properties of chordal graphs with a bounded number of simplicial modules are well understood. For instance, chordal graphs having at most two simplicial modules are interval. In this work we initiate an investigation of $k$moplex graphs, which are defined as graphs containing at most $k$ moplexes. Of particular interest is the smallest nontrivial case $k=2$, which forms a counterpart to the class of interval graphs. As our main structural result, we show that the class of connected $2$moplex graphs is sandwiched between the classes of proper interval graphs and cocomparability graphs; moreover, both inclusions are tight for hereditary classes. From a complexity theoretic viewpoint, this leads to the natural question of whether the presence of at most two moplexes guarantees a sufficient amount of structure to efficiently solve problems that are known to be intractable on cocomparability graphs, but not on proper interval graphs. We develop new reductions that answer this question negatively for two prominent problems fitting this profile, namely Graph Isomorphism and MaxCut. On the other hand, we prove that every connected $2$moplex graph contains a Hamiltonian path, generalising the same property of connected proper interval graphs. Furthermore, for graphs with a higher number of moplexes, we lift the previously known result that graphs without asteroidal triples have at most two moplexes to the more general setting of larger asteroidal sets. 
“On girth and the parameterized complexity of Token Sliding and Token Jumping.”V. Bartier, N. Bousquet, C. Dallard, K. Lomer, and A. E. Mouawad.Algorithmica, vol. 83, no. 9, pp. 2914–2951
In the Token Jumping problem we are given a graph $G = (V,E)$ and two independent sets $S$ and $T$ of $G$, each of size $k ≥1$. The goal is to determine whether there exists a sequence of $k$sized independent sets in $G$, $⟨S_0, S_1, \ldots, S_\ell ⟩$, such that for every $i$, $S_i = k$, $S_i$ is an independent set, $S = S_0$, $S_\ell = T$, and $S_i ∆S_{i+1} = 2$. In other words, if we view each independent set as a collection of tokens placed on a subset of the vertices of $G$, then the problem asks for a sequence of independent sets which transforms $S$ to $T$ by individual token jumps which maintain the independence of the sets. This problem is known to be PSPACEcomplete on very restricted graph classes, e.g., planar bounded degree graphs and graphs of bounded bandwidth. A closely related problem is the Token Sliding problem, where instead of allowing a token to jump to any vertex of the graph we instead require that a token slides along an edge of the graph. Token Sliding is also known to be PSPACEcomplete on the aforementioned graph classes. We investigate the parameterized complexity of both problems on several graph classes, focusing on the effect of excluding certain cycles from the input graph. In particular, we show that both Token Sliding and Token Jumping are fixedparameter tractable on $C_4$free bipartite graphs when parameterized by $k$. For Token Jumping, we in fact show that the problem admits a polynomial kernel on $\{C_3,C_4\}$free graphs. In the case of Token Sliding, we also show that the problem admits a polynomial kernel on bipartite graphs of bounded degree. We believe both of these results to be of independent interest. We complement these positive results by showing that, for any constant $p ≥4$, both problems are W[1]hard on $\{C_4, …, C_p\}$free graphs and Token Sliding remains W[1]hard even on bipartite graphs.
2020

“On girth and the parameterized complexity of token sliding and token jumping.”V. Bartier, N. Bousquet, C. Dallard, K. Lomer, and A. E. Mouawad.in 31st International Symposium on Algorithms and Computation, vol. 181, pp. 44:1–44:17
In the Token Jumping problem we are given a graph $G = (V,E)$ and two independent sets $S$ and $T$ of $G$, each of size $k ≥1$. The goal is to determine whether there exists a sequence of $k$sized independent sets in $G$, $⟨S_0, S_1, \ldots, S_\ell ⟩$, such that for every $i$, $S_i = k$, $S_i$ is an independent set, $S = S_0$, $S_\ell = T$, and $S_i ∆S_{i+1} = 2$. In other words, if we view each independent set as a collection of tokens placed on a subset of the vertices of $G$, then the problem asks for a sequence of independent sets which transforms $S$ to $T$ by individual token jumps which maintain the independence of the sets. This problem is known to be PSPACEcomplete on very restricted graph classes, e.g., planar bounded degree graphs and graphs of bounded bandwidth. A closely related problem is the Token Sliding problem, where instead of allowing a token to jump to any vertex of the graph we instead require that a token slides along an edge of the graph. Token Sliding is also known to be PSPACEcomplete on the aforementioned graph classes. We investigate the parameterized complexity of both problems on several graph classes, focusing on the effect of excluding certain cycles from the input graph. In particular, we show that both Token Sliding and Token Jumping are fixedparameter tractable on $C_4$free bipartite graphs when parameterized by $k$. For Token Jumping, we in fact show that the problem admits a polynomial kernel on $\{C_3,C_4\}$free graphs. In the case of Token Sliding, we also show that the problem admits a polynomial kernel on bipartite graphs of bounded degree. We believe both of these results to be of independent interest. We complement these positive results by showing that, for any constant $p ≥4$, both problems are W[1]hard on $\{C_4, …, C_p\}$free graphs and Token Sliding remains W[1]hard even on bipartite graphs. 
“Treewidth versus clique number in graph classes with a forbidden structure.”C. Dallard, M. Milanič, and K. Štorgel.in GraphTheoretic Concepts in Computer Science, pp. 92–105
Treewidth is an important graph invariant, relevant for both structural and algorithmic reasons. A necessary condition for a graph class to have bounded treewidth is the absence of large cliques. We study graph classes in which this condition is also sufficient, which we call $(tw,ω)$bounded. Such graph classes are known to have useful algorithmic applications related to variants of the clique and $k$coloring problems. We consider six wellknown graph containment relations: the minor, topological minor, subgraph, induced minor, induced topological minor, and induced subgraph relations. For each of them, we give a complete characterization of the graphs $H$ for which the class of graphs excluding $H$ is $(tw,ω)$bounded. Our results imply that the class of $1$perfectly orientable graphs is $(tw,ω)$bounded, answering a question of Brešar, Hartinger, Kos, and Milanič from 2018. We also reveal some further algorithmic implications of $(tw,ω)$boundedness related to list $k$coloring and clique problems. 
“Graphs without a partition into two proportionally dense subgraphs.”C. Bazgan, J. Chlebíková, and C. Dallard.Information Processing Letters, vol. 155, pp. 105877, 5
A proportionally dense subgraph (PDS) is an induced subgraph of a graph such that each vertex in the PDS is adjacent to proportionally as many vertices in the subgraph as in the rest of the graph. In this paper, we study a partition of a graph into two proportionally dense subgraphs, namely a $2$PDS partition, with and without additional constraint of connectivity of the subgraphs. We present two infinite classes of graphs: one with graphs without a $2$PDS partition, and another with graphs that only admit a disconnected $2$PDS partition. These results answer some questions proposed by Bazgan et al. [Algorithmica 80(6) (2018), 1890–1908].
2019

“Proportionally dense subgraph of maximum size: complexity and approximation.”C. Bazgan, J. Chlebíková, C. Dallard, and T. Pontoizeau.Discrete Applied Mathematics, vol. 270, pp. 25–36
We define a proportionally dense subgraph (PDS) as an induced subgraph of a graph with the property that each vertex in the PDS is adjacent to proportionally as many vertices in the subgraph as in the graph. We prove that the problem of finding a PDS of maximum size is NPhard, more precisely APXhard, even on split graphs. On the other hand, we present a simple polynomialtime $(2\frac{2}{∆+1})$approximation algorithm for the problem. We also prove that all Hamiltonian cubic graphs (except two) have a PDS of the maximum possible size which can be found in linear time (if a Hamiltonian cycle is given). Finally, we show that deciding if a PDS is inclusionwise maximal is coNPcomplete on bipartite graphs. 
“Towards a complexity dichotomy for colourful components problems on $k$caterpillars and smalldegree planar graphs.”J. Chlebíková and C. Dallard.in Combinatorial algorithms, vol. 11638, Springer, Cham, pp. 136–147
A connected component of a vertexcoloured graph is said to be colourful if all its vertices have different colours, and a graph is colourful if all its connected components are colourful. Given a vertexcoloured graph, the Colourful Components problem asks whether there exist at most $p$ edges whose removal makes the graph colourful, and the Colourful Partition problem asks whether there exists a partition of the vertex set with at most $p$ parts such that each part induces a colourful component. We study the problems on $k$caterpillars (caterpillars with hairs of length at most $k$) and explore the boundary between polynomial and NPcomplete cases. It is known that the problems are NPcomplete on $2$caterpillars with unbounded maximum degree. We prove that both problems remain NPcomplete on binary $4$caterpillars and on ternary $3$caterpillars. This answers an open question regarding the complexity of the problems on trees with maximum degree at most $5$. On the positive side, we give a linear time algorithm for $1$caterpillars with unbounded degree, even if the backbone is a cycle, which outperforms the previous best complexity for paths and widens the class of graphs. Finally, we answer an open question regarding the complexity of Colourful Components on graphs with maximum degree at most $5$. We show that the problem is NPcomplete on $5$coloured planar graphs with maximum degree $4$, and on $12$coloured planar graphs with maximum degree $3$. Since the problem can be solved in polynomialtime on graphs with maximum degree $2$, the results are the best possible with regard to the maximum degree. 
“Complexity of scheduling for DARP with soft ride times.”J. Chlebíková, C. Dallard, and N. Paulsen.in Algorithms and complexity, vol. 11485, Springer, Cham, pp. 149–160
The DialaRide problem may contain various constraints for pickupdelivery requests, such as time windows and ride time constraints. For a tour, given as a sequence of pickup and delivery stops, there exist polynomial time algorithms to find a schedule respecting these constraints, provided that there exists one. However, if no feasible schedule exists, the natural question is to find a schedule minimising constraint violations. We model a generic fixedsequence scheduling problem, allowing lateness and ride time violations with linear penalty functions and prove its APXhardness. We also present an approach leading to a polynomial time algorithm if only the time window constraints can be violated (by late visits). Then, we show that the problem can be solved in polynomial time if all the ride time constraints are bounded by a constant. Lastly, we give a polynomial time algorithm for the instances where all the pickups precede all the deliveries in the sequence of stops.
2018

“Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases.”M. Weller, A. Chateau, C. Dallard, and R. Giroudeau.Algorithmica, vol. 80, no. 6, pp. 1771–1803
This paper is devoted to new results about the scaffolding problem, an integral problem of genome inference in bioinformatics. The problem consists in finding a collection of disjoint cycles and paths covering a particular graph called the “scaffold graph”. We examine the difficulty and the approximability of the scaffolding problem in special classes of graphs, either close to trees, or very dense. We propose negative and positive results, exploring the frontier between difficulty and tractability of computing and/or approximating a solution to the problem. Also, we explore a new direction through related problems consisting in finding a family of edges having a strong effect on solution weight.
2016

“Instance guaranteed ratio on greedy heuristic for genome scaffolding.”C. Dallard, M. Weller, A. Chateau, and R. Giroudeau.in Combinatorial optimization and applications, vol. 10043, Springer, Cham, pp. 294–308
The Scaffolding problem in bioinformatics, aims to complete the contig assembly process by determining the relative position and orientation of these contigs. Modeled as a combinatorial optimization problem in a graph named scaffold graph, this problem is NPhard and its exact resolution is generally impossible on large instances. Hence, heuristics like polynomialtime approximation algorithms remain the only possibility to propose a solution. In general, even in the case where we know a constant guaranteed approximation ratio, it is impossible to know if the solution proposed by the algorithm is close to the optimal, or close to the bound defined by this ratio. In this paper we present a measure, associated to a greedy algorithm, determining an upper bound on the score of the optimal solution. This measure, depending on the instance, guarantees a – non constant – ratio for the greedy algorithm on this instance. We prove that this measure is a fine upper bound on optimal score, we perform experiments on real instances and show that the greedy algorithm yields near from optimal solutions.
Courses recently taught
 Lectures and tutorials : Graph Theory and Optimization Methods (3rd year students)
 Tutorials: Discrete Mathematics (1st and 2nd year students)