Sufficient conditions for polynomial-time detection of induced minors
C. Dallard, M. Dumas, C. Hilaire, and A. Perez.
Dec. 2024.
Sufficient conditions for polynomial-time detection of induced minors
The $H$-Induced Minor Containment problem ($H$-IMC) consists in deciding if a fixed graph $H$ is an induced minor of a graph $G$ given as input, that is, whether $H$ can be obtained from $G$ by deleting vertices and contracting edges. Several graphs $H$ are known for which $H$-IMC is NP-complete, even when $H$ is a tree. In this paper, we investigate which conditions on $H$ and $G$ are sufficient so that the problem becomes polynomial-time solvable. Our results identify three infinite classes of graphs such that, if $H$ belongs to one of these classes, then $H$-IMC can be solved in polynomial time. Moreover, we show that if the input graph $G$ excludes long induced paths, then $H$-IMC is polynomial-time solvable for any fixed graph $H$. As a byproduct of our results, this implies that $H$-IMC is polynomial-time solvable for all graphs $H$ with at most 5 vertices, except for three open cases.
@misc{DDHP2024,
title = {Sufficient conditions for polynomial-time detection of induced minors},
author = {Dallard, Clément and Dumas, Maël and Hilaire, Claire and Perez, Anthony},
archiveprefix = {arXiv},
year = {2024},
month = dec,
eprint = {2501.00161},
primaryclass = {cs.DS},
volume = {abs/2501.00161},
url = {https://arxiv.org/abs/2501.00161}
}
Finding $k$-community structures in special graph
classes
N. Baghirova, C. Dallard, B. Ries, and D. Schindl.
Discrete Applied Mathematics, Dec. 2024.
Finding $k$-community structures in special graph classes
For a fixed integer $k\ge 2$, a $k$-community
structure in an undirected graph is a partition of its
vertex set into $k$ sets called communities, each
of size at least two, such that every vertex of the graph
has proportionally at least as many neighbours in its own
community as in any other community. In this paper, we give
a necessary and sufficient condition for a forest on $n$
vertices to admit a $k$-community structure. Furthermore,
we provide an $\mathcal{O}(n^{2})$-time algorithm that
computes such a $k$-community structure in a forest, if it
exists. These results extend a result of [Bazgan et al.,
Structural and algorithmic properties of $2$-community
structure, Algorithmica, 80(6):1890-1908, 2018]. We also
show that if communities are allowed to have size one, then
every forest with $n ≥k≥2$ vertices admits a
$k$-community structure that can be found in time
$\mathcal{O}(n^{2})$. We then consider threshold graphs and
show that every connected threshold graph admits a
$2$-community structure if and only if it is not isomorphic
to a star; also if such a $2$-community structure exists,
we explain how to obtain it in linear time. We further
describe two infinite families of disconnected threshold
graphs, containing exactly one isolated vertex, that do not
admit any $2$-community structure. Finally, we present a
new infinite family of connected graphs that may contain an
even or an odd number of vertices without $2$-community
structures, even if communities are allowed to have size one.
@article{BDRS2024,
title = {Finding $k$-community structures in special graph
classes},
journal = {Discrete Applied Mathematics},
volume = {359},
pages = {159-175},
year = {2024},
issn = {0166-218X},
doi = {https://doi.org/10.1016/j.dam.2024.07.033},
author = {Baghirova, Narmina and Dallard, Clément and Ries, Bernard and Schindl, David},
archiveprefix = {arXiv},
eprint = {2206.14738},
day = {31},
month = dec
}
Computing Tree Decompositions with Small Independence Number
C. Dallard, F. V. Fomin, P. A. Golovach, T. Korhonen, and M. Milanič.
In 51st International Colloquium on Automata, Languages, and
Programming (ICALP 2024), Jul. 2024.
Computing Tree Decompositions with Small Independence Number
The independence number of a tree decomposition is the
maximum of the independence numbers of the subgraphs
induced by its bags. The tree-independence number of a
graph is the minimum independence number of a tree
decomposition of it. Several NP-hard graph problems, like
maximum weight independent set, can be solved in time
$n^{O(k)}$ if the input graph is given with a tree
decomposition of independence number at most $k$. However,
it was an open problem if tree-independence number could be
computed or approximated in $n^{f(k)}$ time, for some
function $f$, and in particular it was not known if maximum
weight independent set could be solved in polynomial time
on graphs of bounded tree-independence number.
In this paper, we resolve the main open problems about the
computation of tree-independence number. First, we give an
algorithm that given an $n$-vertex graph $G$ and an integer
$k$, in time $2^{O(k^2)} n^{O(k)}$ either outputs a tree
decomposition of $G$ with independence number at most $8k$,
or determines that the tree-independence number of $G$ is
larger than $k$. This implies $2^{O(k^2)} n^{O(k)}$ time
algorithms for various problems, like maximum weight
independent set, parameterized by tree-independence number
$k$ without needing the decomposition as an input. Then, we
show that the exact computing of tree-independence number
is paraNP-hard, in particular, that for every constant $k
\ge 4$ it is NP-hard to decide if a given graph has
tree-independence number at most $k$.
@inproceedings{DFGKM2024,
title = {Computing Tree Decompositions with Small Independence Number},
author = {Dallard, Clément and Fomin, Fedor V. and Golovach, Petr A. and Korhonen, Tuukka and Milanič, Martin},
address = {Dagstuhl, Germany},
booktitle = {51st International Colloquium on Automata, Languages, and
Programming (ICALP 2024)},
day = {02},
doi = {10.4230/lipics.icalp.2024.51},
editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
isbn = {978-3-95977-322-5},
issn = {1868-8969},
month = jul,
pages = {51:1--51:18},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
series = {Leibniz International Proceedings in Informatics
(LIPIcs)},
url = {https://doi.org/10.4230/LIPIcs.ICALP.2024.51},
volume = {297},
year = {2024}
}
Treewidth versus clique number. III. Tree-independence
number of graphs with a forbidden structure
C. Dallard, M. Milanič, and K. Štorgel.
Journal of Combinatorial Theory, Series B, Jul. 2024.
Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure
We continue the study of $(tw,ω)$-bounded graph
classes, that is, hereditary graph classes in which the
treewidth can only be large due to the presence of a large
clique, with the goal of understanding the extent to which
this property has useful algorithmic implications for the
Maximum Independent Set and related problems.
In the previous paper of the series [Dallard, Milanič, and
Štorgel, Treewidth versus clique number. II.
Tree-independence number], we introduced the
tree-independence number, a min-max graph invariant
related to tree decompositions. Bounded tree-independence
number implies both $(tw,ω)$-boundedness and the
existence of a polynomial-time algorithm for the Maximum
Weight Independent Packing problem, provided that the input
graph is given together with a tree decomposition with
bounded independence number. In particular, this implies
polynomial-time solvability of the Maximum Weight
Independent Set problem.
In this paper, 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. The induced
minor relation is of particular interest: we show that
excluding either a $K_5$ minus an edge or the $4$-wheel
implies the existence of a tree decomposition in which
every bag is a clique plus at most $3$ vertices, while
excluding a complete bipartite graph $K_{2,q}$ implies the
existence of a tree decomposition with independence number
at most $2(q-1)$.
These results are obtained using a variety of tools,
including $\ell$-refined tree decompositions, SPQR trees,
and potential maximal cliques, and actually show that in
the bounded cases identified in this work, one can also
compute tree decompositions with bounded independence
number efficiently. Applying the algorithmic framework
provided by the previous paper in the series leads to
polynomial-time 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. In particular, these results apply to the
class of $1$-perfectly orientable graphs, answering a
question of Beisegel, Chudnovsky, Gurvich, Milanič, and
Servatius from 2019.
@article{DMS_JCTB2024,
title = {Treewidth versus clique number. {III}. {T}ree-independence
number of graphs with a forbidden structure},
author = {Dallard, Clément and Milanič, Martin and Štorgel, Kenny},
archiveprefix = {arXiv},
doi = {10.1016/j.jctb.2024.03.005},
eprint = {2206.15092},
journal = {Journal of Combinatorial Theory, Series {B}},
month = jul,
pages = {338-391},
shortjournal = {JCTB},
volume = {167},
year = {2024}
}
Detecting $K_{2,3}$ as an induced minor
C. Dallard, M. Dumas, C. Hilaire, M. Milanič, A. Perez, and N. Trotignon.
In Combinatorial Algorithms (IWOCA), Jun. 2024.
Detecting $K_{2,3}$ as an induced minor
We consider a natural generalization of chordal graphs, in
which every minimal separator induces a subgraph with
independence number at most $2$. Such graphs can be
equivalently defined as graphs that do not contain the
complete bipartite graph $K_{2,3}$ as an induced minor,
that is, graphs from which $K_{2,3}$ cannot be obtained by
a sequence of edge contractions and vertex deletions.
We develop a polynomial-time algorithm for recognizing
these graphs. Our algorithm relies on a characterization of
$K_{2,3}$-induced minor-free graphs in terms of excluding
particular induced subgraphs, called Truemper
configurations.
@inproceedings{DDHMPT_IWOCA2024,
title = {Detecting $K_{2,3}$ as an induced minor},
author = {Dallard, Clément and Dumas, Maël and Hilaire, Claire and Milanič, Martin and Perez, Anthony and Trotignon, Nicolas},
address = {Cham},
archiveprefix = {arXiv},
booktitle = {Combinatorial Algorithms},
day = {22},
doi = {10.1007/978-3-031-63021-7_12},
eprint = {2402.08332},
isbn = {978-3-031-63021-7},
month = jun,
pages = {151--164},
primaryclass = {math.CO},
publisher = {Springer Nature Switzerland},
shortbooktitle = {IWOCA},
year = {2024}
}
Graphs with at most two moplexes
C. Dallard, R. Ganian, M. Hatzel, M. Krnc, and M. Milanič.
Journal of Graph Theory, May. 2024.
Graphs with at most two moplexes
A moplex is a natural graph structure that arises when
lifting Dirac’s classical theorem from chordal graphs to
general graphs. The notion is known to be closely related
to lexicographic searches in graphs as well as to
asteroidal triples, and has been applied in several
algorithms related to graph classes such as interval
graphs, claw-free, and diamond-free graphs. However, while
every non-complete 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,
in part, 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, when restricted to connected graphs, the class of
$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 Max-Cut. 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.
@article{DGHKM2024,
title = {Graphs with at most two moplexes},
author = {Dallard, Clément and Ganian, Robert and Hatzel, Meike and Krnc, Matjaž and Milanič, Martin},
day = {8},
doi = {10.1002/jgt.23102},
eprint = {2106.10049},
journal = {Journal of Graph Theory},
month = may,
publisher = {Wiley Online Library},
year = {2024}
}
Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star
C. Dallard, M. Krnc, O.-joung Kwon, M. Milanič, A. Munaro, K. Štorgel, and S. Wiederrecht.
Feb. 2024.
Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star
Many recent works address the question of characterizing
induced obstructions to bounded treewidth. In 2022, Lozin
and Razgon completely answered this question for graph
classes defined by finitely many forbidden induced
subgraphs. Their result also implies a characterization of
graph classes defined by finitely many forbidden induced
subgraphs that are $(tw,ω)$-bounded, that is,
treewidth can only be large due to the presence of a large
clique. This condition is known to be satisfied for any
graph class with bounded tree-independence number, a graph
parameter introduced independently by Yolov in 2018 and by
Dallard, Milanič, and Štorgel in 2024. Dallard et al.
conjectured that $(tw,ω)$-boundedness is actually
equivalent to bounded tree-independence number. We address
this conjecture in the context of graph classes defined by
finitely many forbidden induced subgraphs and prove it for
the case of graph classes excluding an induced star. We
also prove it for subclasses of the class of line graphs,
determine the exact values of the tree-independence numbers
of line graphs of complete graphs and line graphs of
complete bipartite graphs, and characterize the
tree-independence number of $P_4$-free graphs, which
implies a linear-time algorithm for its computation.
Applying the algorithmic framework provided in a previous
paper of the series leads to polynomial-time algorithms for
the Maximum Weight Independent Set problem in an infinite
family of graph classes.
@misc{DKKMMSW2024,
title = {Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star},
author = {Dallard, Clément and Krnc, Matjaž and Kwon, O-joung and Milanič, Martin and Munaro, Andrea and Štorgel, Kenny and Wiederrecht, Sebastian},
archiveprefix = {arXiv},
doi = {10.48550/arxiv.2402.11222},
eprint = {2402.11222},
month = feb,
primaryclass = {math.CO},
url = {https://doi.org/10.48550/arXiv.2402.11222},
volume = {abs/2402.11222},
year = {2024}
}
Allocation of Indivisible Items with a Common Preference Graph: Minimizing Total Dissatisfaction
N. Chiarelli, C. Dallard, A. Darmann, S. Lendl, M. Milanič, P. Muršič, and U. Pferschy.
Feb. 2024.
Allocation of Indivisible Items with a Common Preference Graph: Minimizing Total Dissatisfaction
Allocating indivisible items among a set of agents is a
frequently studied discrete optimization problem. In the
setting considered in this work, the agents'
preferences over the items are assumed to be identical. We
consider a very recent measure for the overall quality of
an allocation which does not rely on numerical valuations
of the items. Instead, it captures the agents' opinion
by a directed acyclic preference graph with vertices
representing items. An arc $(a,b)$ in such a graph means
that the agents prefer item $a$ over item $b$. For a given
allocation of items the dissatisfaction of an agent is
defined as the number of items which the agent does not
receive and for which no more preferred item is given to
the agent. Our goal is to find an efficient allocation of
the items to the agents such that the total dissatisfaction
over all agents is minimized. We explore the dichotomy
between NP-hard and polynomially solvable instances,
depending on properties of the underlying preference graph.
While the problem is NP-hard already for three agents even
on very restricted graph classes, it is polynomially
solvable for two agents on general preference graphs. For
an arbitrary number of agents, we derive polynomial-time
algorithms for relevant restrictions of the underlying
undirected graph. These are trees and, among the graphs of
treewidth two, series-parallel graphs and cactus graphs.
@misc{CDDLMMP2024,
title = {Allocation of Indivisible Items with a Common Preference Graph: Minimizing Total Dissatisfaction},
author = {Chiarelli, Nina and Dallard, Clément and Darmann, Andreas and Lendl, Stefan and Milanič, Martin and Muršič, Peter and Pferschy, Ulrich},
archiveprefix = {arXiv},
doi = {10.48550/arxiv.2402.00921},
eprint = {2402.00921},
month = feb,
primaryclass = {cs.GT},
url = {https://doi.org/10.48550/arXiv.2402.00921},
volume = {abs/2402.00921},
year = {2024}
}
Minimizing Maximum Dissatisfaction in the Allocation of
Indivisible Items under a Common Preference Graph
N. Chiarelli, C. Dallard, A. Darmann, S. Lendl, M. Milanič, P. Muršič, and U. Pferschy.
Feb. 2024.
Minimizing Maximum Dissatisfaction in the Allocation of Indivisible Items under a Common Preference Graph
We consider the task of allocating indivisible items to
agents, when the agents’ preferences over the items are
identical. The preferences are captured by means of a
directed acyclic graph, with vertices representing items
and an edge $(a,b)$ meaning that each of the agents prefers
item $a$ over item $b$. The dissatisfaction of an agent is
measured by the number of items that the agent does not
receive and also does not receive any more preferred item.
The aim is to allocate the items to the agents in a fair
way, i.e., to minimize the maximum dissatisfaction among
the agents. We study the status of computational complexity
of that problem and establish the following dichotomy: the
problem is NP-hard for the case of at least three agents,
even on fairly restricted graphs, but polynomially solvable
for two agents. We also provide several polynomial-time
results with respect to different underlying graph
structures, such as graphs of width at most two and
tree-like structures such as stars and matchings. These
findings are complemented with fixed parameter tractability
results related to path modules and independent set
modules. Techniques employed in the paper include
bottleneck assignment problem, greedy algorithm, dynamic
programming, maximum network flow, and integer linear
programming.
@misc{CDDLMMP2024_1,
title = {Minimizing Maximum Dissatisfaction in the Allocation of
Indivisible Items under a Common Preference Graph},
author = {Chiarelli, Nina and Dallard, Clément and Darmann, Andreas and Lendl, Stefan and Milanič, Martin and Muršič, Peter and Pferschy, Ulrich},
archiveprefix = {arXiv},
eprint = {2312.01804},
month = feb,
primaryclass = {cs.DM},
year = {2024}
}
Functionality of box intersection graphs
C. Dallard, V. Lozin, M. Milanič, K. Štorgel, and V. Zamaraev.
Results in Mathematics, Jan. 2024.
Functionality of box intersection graphs
Functionality is a graph complexity measure that extends a
variety of parameters, such as vertex degree, degeneracy,
clique-width, or twin-width. In the present paper, we show
that functionality is bounded for box intersection graphs
in $\mathbb{R}^1$, i.e. for interval graphs, and unbounded
for box intersection graphs in $\mathbb{R}^3$. We also
study a parameter known as symmetric difference, which is
intermediate between twin-width and functionality, and show
that this parameter is unbounded both for interval graphs
and for unit box intersection graphs in $\mathbb{R}^2$.
@article{DLMSZ_RIM2024,
title = {Functionality of box intersection graphs},
author = {Dallard, Clément and Lozin, Vadim and Milanič, Martin and Štorgel, Kenny and Zamaraev, Viktor},
archiveprefix = {arXiv},
doi = {10.1007/s00025-023-02075-2},
eprint = {2301.09493},
issn = {1420-9012},
journal = {Results in Mathematics},
month = jan,
shortjournal = {RIM},
volume = {79},
year = {2024}
}
Treewidth versus clique number. II. Tree-independence number
C. Dallard, M. Milanič, and K. Štorgel.
Journal of Combinatorial Theory, Series B, Jan. 2024.
Treewidth versus clique number. II. Tree-independence number
In 2020, we initiated a systematic study of graph classes
in which the treewidth can only be large due to the
presence of a large clique, which we 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, it is an interesting open problem to which extent
$(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 polynomial-time algorithm for the
Maximum Weight Independent Packing problem and, as a
consequence, for the weighted variants of the Independent
Set and Induced Matching problems.
Our approach is based on a new min-max 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 tree-independence number of a
graph $G$ is then defined as the minimum independence
number over all tree decompositions of $G$. Boundedness of
the tree-independence number is a refinement of
$(tw,ω)$-boundedness that is still general enough to
hold for all the aforementioned families of graph classes.
Generalizing a result on chordal graphs due to Cameron and
Hell from 2006, we show that if a graph is given together
with a tree decomposition with bounded independence number,
then the Maximum Weight Independent Packing problem can be
solved in polynomial time. Applications of our general
algorithmic result to specific graph classes are given in
the third paper of the series [Dallard, Milanič, and
Štorgel, Treewidth versus clique number. III.
Tree-independence number of graphs with a forbidden
structure, 2022].
@article{DMS_JCTB2024_1,
title = {Treewidth versus clique number. II. Tree-independence number},
author = {Dallard, Clément and Milanič, Martin and Štorgel, Kenny},
archiveprefix = {arXiv},
doi = {10.1016/j.jctb.2023.10.006},
eprint = {2111.04543},
journal = {Journal of Combinatorial Theory, Series {B}},
month = jan,
pages = {404--442},
primaryclass = {math.CO},
shortjournal = {JCTB},
url = {https://doi.org/10.1016/j.jctb.2023.10.006},
volume = {164},
year = {2024}
}
Conditions for minimally tough graphs
C. Dallard, B. Fernández, G. Y. Katona, M. Milanič, and K. Varga.
Oct. 2023.
Conditions for minimally tough graphs
Katona, Soltész, and Varga showed that no induced
subgraph can be excluded from the class of minimally tough
graphs. In this paper, we consider the opposite question,
namely which induced subgraphs, if any, must necessarily be
present in each minimally $t$-tough graph. Katona and Varga
showed that for any rational number $t ∈(1/2,1]$, every
minimally $t$-tough graph contains a hole. We complement
this result by showing that for any rational number $t>1$,
every minimally $t$-tough graph must contain either a hole
or an induced subgraph isomorphic to the $k$-sun for some
integer $k \ge 3$. We also show that for any rational
number $t > 1/2$, every minimally $t$-tough graph must
contain either an induced $4$-cycle, an induced $5$-cycle,
or two independent edges as an induced subgraph.
@misc{DFKMV2023,
title = {Conditions for minimally tough graphs},
author = {Dallard, Clément and Fernández, Blas and Katona, Gyula Y. and Milanič, Martin and Varga, Kitti},
archiveprefix = {arXiv},
eprint = {2210.00383},
month = oct,
year = {2023}
}
Allocation of indivisible items with individual preference graphs
N. Chiarelli, C. Dallard, A. Darmann, S. Lendl, M. Milanič, P. Muršič, U. Pferschy, and N. Pivač.
Discrete Applied Mathematics, Jul. 2023.
Allocation of indivisible items with individual preference graphs
This paper studies the allocation of indivisible items to
agents, when each agent’s preferences are expressed by
means of a directed acyclic graph. The vertices of each
preference graph represent the subset of items approved of
by the respective agent. An arc $(a,b)$ in such a graph
means that the respective agent prefers item $a$ over item
$b$. We introduce a new measure of dissatisfaction of an
agent by counting the number of non-assigned items which
are approved of by the agent and for which no more
preferred item is allocated to the agent. Considering two
problem variants, we seek an allocation of 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 optimization
problems we study the status of computational complexity
and obtain NP-hardness results as well as polynomial
algorithms with respect to natural underlying graph
structures, such as stars, trees, paths, and matchings. We
also analyze the parameterized complexity of the two
problems with respect to various parameters related to the
number of agents, the dissatisfaction threshold, the vertex
degrees of the preference graphs, and the treewidth.
@article{CDDLMMPP_DAM2023,
title = {Allocation of indivisible items with individual preference graphs},
author = {Chiarelli, Nina and Dallard, Clément and Darmann, Andreas and Lendl, Stefan and Milanič, Martin and Muršič, Peter and Pferschy, Ulrich and Pivač, Nevena},
archiveprefix = {arXiv},
doi = {10.1016/j.dam.2023.02.010},
eprint = {2202.04465},
issn = {0166-218X},
journal = {Discrete Applied Mathematics},
keywords = {Fair division, Partial order, Preference graph,
Dissatisfaction},
month = jul,
pages = {45--62},
shortjournal = {DAM},
url = {https://doi.org/10.1016/j.dam.2023.02.010},
volume = {334},
year = {2023}
}
Impact of soft ride time constraints on the complexity of scheduling in Dial-A-Ride Problems
J. Chlebíková, C. Dallard, and N. Paulsen.
Theoretical Computer Science, Jun. 2023.
Impact of soft ride time constraints on the complexity of scheduling in Dial-A-Ride Problems
The Dial-a-Ride problem can contain various constraints
for pickup-delivery requests, such as time windows and ride
time constraints. Given a tour as a sequence of pickups and
deliveries, there exist polynomial time algorithms to find
a schedule respecting these constraints (provided that
there exists one). However, if no such schedule exists, it
is natural to ask for a schedule minimising constraint
violations. We model a generic fixed-sequence scheduling
problem, which we call Min Pickup-Delivery Scheduling, that
allows violation of time window constraints (by late
visits) and ride time constraints, both penalised with
linear penalty functions. Although our model only considers
these two types of time constraints, we show that it can
express other common time constraints such as earliness and
waiting times. We prove that Min Pickup-Delivery Scheduling
is APX-hard, even in the very restrictive case where only
the ride time constraints can be violated and the time
windows have the same length. Conversely, when only the
time window constraints can be violated (by late visits),
we present a polynomial time algorithm to solve the
problem. Then we focus on instances with some specific
structural properties and present two polynomial-time
algorithms: one for the case where all the ride time
constraints are bounded by a constant, and a second one for
the case where all the pickups precede all the deliveries
in the sequence of stops.
@article{CDP_TCS2023,
title = {Impact of soft ride time constraints on the complexity of scheduling in Dial-A-Ride Problems},
author = {Chlebíková, Janka and Dallard, Clément and Paulsen, Niklas},
doi = {10.1016/j.tcs.2023.113923},
issn = {0304-3975},
journal = {Theoretical Computer Science},
keywords = {dial-a-ride, scheduling, soft constraints, ride times,
time windows},
month = jun,
pages = {113923},
shortjournal = {TCS},
url = {https://www.sciencedirect.com/science/article/pii/S0304397523002360},
volume = {960},
year = {2023}
}
On Constrained Intersection Representations of Graphs and Digraphs
F. Cicalese, C. Dallard, and M. Milanič.
In 33rd International Symposium on Algorithms and
Computation (ISAAC), Dec. 2022.
On Constrained Intersection Representations of Graphs and Digraphs
We study the problem of determining minimal directed
intersection representations of DAGs in a model introduced
by [Kostochka, Liu, Machado, and Milenkovic, ISIT2019]:
vertices are assigned color sets, two vertices are
connected by an arc if and only if they share at least one
color and the tail vertex has a strictly smaller color set
than the head, and the goal is to minimize the total number
of colors. We show that the problem is polynomially
solvable in the class of triangle-free and Hamiltonian DAGs
and also disclose the relationship of this problem with
several other models of intersection representations of
graphs and digraphs.
@inproceedings{CDM_ISAAC2022,
title = {On Constrained Intersection Representations of Graphs and Digraphs},
author = {Cicalese, Ferdinando and Dallard, Clément and Milanič, Martin},
address = {Dagstuhl, Germany},
booktitle = {33rd International Symposium on Algorithms and
Computation},
doi = {10.4230/lipics.isaac.2022.38},
editor = {Bae, Sang Won and Park, Heejin},
isbn = {978-3-95977-258-7},
issn = {1868-8969},
month = dec,
pages = {38:1--38:15},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
series = {Leibniz International Proceedings in Informatics
(LIPIcs)},
shortbooktitle = {ISAAC},
url = {https://doi.org/10.4230/LIPIcs.ISAAC.2022.38},
volume = {248},
year = {2022}
}
Colourful components in k-caterpillars and planar graphs
J. Chlebíková and C. Dallard.
Theoretical Computer Science, Dec. 2021.
Colourful components in k-caterpillars and planar graphs
A connected component of a vertex-coloured 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 vertex-coloured 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 k-caterpillars, 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 NP-complete on 4-caterpillars with
maximum degree 3, 3-caterpillars with maximum degree 4 and
2-caterpillars with maximum degree 5. On the other hand, we
show that the problems are linear-time solvable on
1-caterpillars. Hence, our results imply two complexity
dichotomies on trees: Colourful Components and Colourful
Partition are linear-time solvable on trees with maximum
degree d if d≤2 (that is, on paths), and NP-complete
otherwise; Colourful Components and Colourful Partition are
linear-time solvable on k-caterpillars if k≤1, and
NP-complete otherwise. We leave three open cases which, if
solved, would provide a complexity dichotomy for both
problems on k-caterpillars, for every non-negative integer
k, with respect to the maximum degree. We also show that
Colourful Components is NP-complete on 5-coloured planar
graphs with maximum degree 4 and on 12-coloured 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].
@article{CD_TCS2021,
title = {Colourful components in k-caterpillars and planar graphs},
author = {Chlebíková, Janka and Dallard, Clément},
doi = {10.1016/j.tcs.2021.09.040},
eprint = {1902.11191},
issn = {0304-3975},
journal = {Theoretical Computer Science},
month = dec,
pages = {137--150},
shortjournal = {TCS},
volume = {895},
year = {2021}
}
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 (LATIN), Dec. 2021.
Graphs with Two Moplexes
A moplex is a natural graph structure that arises when
lifting Dirac’s classical theorem from chordal graphs to
general graphs. However, while every non-complete 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 Max-Cut. 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.
@inproceedings{DGHKM_LATIN2021,
title = {Graphs with Two Moplexes},
author = {Dallard, Clément and Ganian, Robert and Hatzel, Meike and Krnc, Matjaž and Milanič, Martin},
booktitle = {XI Latin and American Algorithms, Graphs and Optimization
Symposium},
doi = {10.1016/j.procs.2021.11.031},
month = dec,
pages = {248--256},
shortbooktitle = {LATIN},
year = {2021}
}
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 (ADT), Oct. 2021.
Allocating Indivisible Items with Minimum Dissatisfaction on Preference Graphs
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
non-assigned 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 NP-hardness results as well as polynomial
algorithms with respect to different underlying graph
structures, such as trees, stars, paths, and matchings.
@inproceedings{CDDLMMPP_ADT2021,
title = {Allocating Indivisible Items with Minimum Dissatisfaction on Preference Graphs},
author = {Chiarelli, Nina and Dallard, Clément and Darmann, Andreas and Lendl, Stefan and Milanič, Martin and Muršič, Peter and Pivač, Nevena and Pferschy, Ulrich},
booktitle = {7th International Conference on Algorithmic Decision
Theory},
doi = {10.1007/978-3-030-87756-9_16},
month = oct,
pages = {243--257},
shortbooktitle = {ADT},
year = {2021}
}
Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure
C. Dallard, M. Milanič, and K. Štorgel.
SIAM Journal on Discrete Mathematics, Jul. 2021.
Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure
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 well-known 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
induced-minor-closed graph classes and imply that the class
of $1$-perfectly orientable graphs is
$(tw,ω)$-bounded, leading to linear-time 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 polynomial-time
solvable in every class of graphs excluding a fixed star as
an induced minor.
@article{DMS_SIDMA2021,
title = {Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure},
author = {Dallard, Clément and Milanič, Martin and Štorgel, Kenny},
doi = {10.1137/20m1352119},
eprint = {2006.06067},
journal = {SIAM Journal on Discrete Mathematics},
month = jul,
number = {4},
pages = {2618--2646},
shortjournal = {SIDMA},
volume = {35},
year = {2021}
}
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, Jul. 2021.
On Girth and the Parameterized Complexity of Token Sliding and Token Jumping
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 PSPACE-complete 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 PSPACE-complete 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 fixed-parameter 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.
@article{BBDLM_ALGORITHMICA2021,
title = {On Girth and the Parameterized Complexity of Token Sliding and Token Jumping},
author = {Bartier, Valentin and Bousquet, Nicolas and Dallard, Clément and Lomer, Kyle and Mouawad, Amer E},
doi = {10.1007/s00453-021-00848-1},
eprint = {2007.01673},
issn = {0178-4617},
journal = {Algorithmica},
month = jul,
mrclass = {68R10 (68Q27)},
mrnumber = {4296283},
number = {9},
pages = {2914--2951},
shortjournal = {Algorithmica},
url = {https://doi.org/10.1007/s00453-021-00848-1},
volume = {83},
year = {2021}
}
Vertex Cover at Distance on H-Free Graphs
C. Dallard, M. Krbezlija, and M. Milanič.
In Combinatorial Algorithms (IWOCA), Jun. 2021.
Vertex Cover at Distance on H-Free Graphs
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 distance-based 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 NP-complete otherwise.
@inproceedings{DKM_IWOCA2021,
title = {Vertex Cover at Distance on H-Free Graphs},
author = {Dallard, Clément and Krbezlija, Mirza and Milanič, Martin},
booktitle = {Combinatorial Algorithms},
day = {30},
doi = {10.1007/978-3-030-79987-8_17},
editor = {Flocchini, Paola and Moura, Lucia},
isbn = {978-3-030-79987-8},
month = jun,
pages = {237--251},
publisher = {Springer International Publishing},
shortbooktitle = {IWOCA},
year = {2021}
}
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 (ISAAC), Dec. 2020.
On Girth and the Parameterized Complexity of Token Sliding and Token Jumping
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 PSPACE-complete 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 PSPACE-complete
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
fixed-parameter 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.
@inproceedings{BBDLM_ISAAC2020,
title = {On Girth and the Parameterized Complexity of Token Sliding and Token Jumping},
author = {Bartier, Valentin and Bousquet, Nicolas and Dallard, Clément and Lomer, Kyle and Mouawad, Amer E},
annote = {Keywords: Combinatorial reconfiguration, Independent Set,
Token Jumping, Token Sliding, Parameterized Complexity},
booktitle = {31st International Symposium on Algorithms and
Computation},
doi = {10.4230/lipics.isaac.2020.44},
editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
isbn = {978-3-95977-173-3},
issn = {1868-8969},
month = dec,
pages = {44:1--44:17},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
series = {Leibniz International Proceedings in Informatics
(LIPIcs)},
shortbooktitle = {ISAAC},
url = {https://doi.org/10.4230/LIPIcs.ISAAC.2020.44},
urn = {urn:nbn:de:0030-drops-133886},
volume = {181},
year = {2020}
}
Treewidth Versus Clique Number in Graph Classes with a Forbidden Structure
C. Dallard, M. Milanič, and K. Štorgel.
In Graph-Theoretic Concepts in Computer Science (WG), Oct. 2020.
Treewidth Versus Clique Number in Graph Classes with a Forbidden Structure
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
well-known 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.
@inproceedings{DMS_WG2020,
title = {Treewidth Versus Clique Number in Graph Classes with a Forbidden Structure},
author = {Dallard, Clément and Milanič, Martin and Štorgel, Kenny},
booktitle = {Graph-Theoretic Concepts in Computer Science},
day = {09},
doi = {10.1007/978-3-030-60440-0_8},
isbn = {978-3-030-60440-0},
month = oct,
pages = {92--105},
publisher = {Springer International Publishing},
shortbooktitle = {WG},
year = {2020}
}
Graphs without a partition into two proportionally dense subgraphs
C. Bazgan, J. Chlebíková, and C. Dallard.
Information Processing Letters, Mar. 2020.
Graphs without a partition into two proportionally dense subgraphs
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].
@article{BCD_IPL2020,
title = {Graphs without a partition into two proportionally dense subgraphs},
author = {Bazgan, Cristina and Chlebíková, Janka and Dallard, Clément},
doi = {10.1016/j.ipl.2019.105877},
eprint = {1806.10963},
issn = {0020-0190},
journal = {Information Processing Letters},
month = mar,
mrclass = {05C85 (05C70)},
mrnumber = {4042574},
pages = {105877, 5},
shortjournal = {IPL},
url = {https://doi.org/10.1016/j.ipl.2019.105877},
volume = {155},
year = {2020}
}
Proportionally dense subgraph of maximum size: Complexity and approximation
C. Bazgan, J. Chlebíková, C. Dallard, and T. Pontoizeau.
Discrete Applied Mathematics, Nov. 2019.
Proportionally dense subgraph of maximum size: Complexity and approximation
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 NP-hard, more
precisely APX-hard, even on split graphs. On the other
hand, we present a simple polynomial-time
$(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
inclusion-wise maximal is co-NP-complete on bipartite
graphs.
@article{BCDP_DAM2019,
title = {Proportionally dense subgraph of maximum size: Complexity and approximation},
author = {Bazgan, Cristina and Chlebíková, Janka and Dallard, Clément and Pontoizeau, Thomas},
doi = {10.1016/j.dam.2019.07.010},
eprint = {1903.06579},
issn = {0166-218X},
journal = {Discrete Applied Mathematics},
month = nov,
mrclass = {05C85 (05C70 68Q17 68Q25 68R10 68W25)},
mrnumber = {4023158},
mrreviewer = {Lenwood S. Heath},
pages = {25--36},
shortjournal = {DAM},
url = {https://doi.org/10.1016/j.dam.2019.07.010},
volume = {270},
year = {2019}
}
Towards a Complexity Dichotomy for Colourful Components Problems on k-caterpillars and Small-Degree Planar Graphs
J. Chlebíková and C. Dallard.
In Combinatorial algorithms (IWOCA), Jul. 2019.
Towards a Complexity Dichotomy for Colourful Components Problems on k-caterpillars and Small-Degree Planar Graphs
A connected component of a vertex-coloured 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 vertex-coloured 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
NP-complete cases. It is known that the problems are
NP-complete on $2$-caterpillars with unbounded maximum
degree. We prove that both problems remain NP-complete 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
NP-complete 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
polynomial-time on graphs with maximum degree $2$, the
results are the best possible with regard to the maximum
degree.
@inproceedings{CD_IWOCA2019,
title = {Towards a Complexity Dichotomy for Colourful Components Problems on k-caterpillars and Small-Degree Planar Graphs},
author = {Chlebíková, Janka and Dallard, Clément},
booktitle = {Combinatorial algorithms},
doi = {10.1007/978-3-030-25005-8_12},
month = jul,
mrclass = {68R10 (68Q17 68Q25)},
mrnumber = {3991231},
pages = {136--147},
publisher = {Springer, Cham},
series = {Lecture Notes in Comput. Sci.},
shortbooktitle = {IWOCA},
url = {https://doi.org/10.1007/978-3-030-25005-8_12},
volume = {11638},
year = {2019}
}
Complexity of Scheduling for DARP with Soft Ride Times
J. Chlebíková, C. Dallard, and N. Paulsen.
In Algorithms and complexity (CIAC), Apr. 2019.
Complexity of Scheduling for DARP with Soft Ride Times
The Dial-a-Ride problem may contain various constraints
for pickup-delivery 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
fixed-sequence scheduling problem, allowing lateness and
ride time violations with linear penalty functions and
prove its APX-hardness. 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.
@inproceedings{CDP_CIAC2019,
title = {Complexity of Scheduling for DARP with Soft Ride Times},
author = {Chlebíková, Janka and Dallard, Clément and Paulsen, Niklas},
booktitle = {Algorithms and complexity},
doi = {10.1007/978-3-030-17402-6_13},
month = apr,
mrclass = {68Q17 (68Q25 90B35)},
mrnumber = {3973648},
pages = {149--160},
publisher = {Springer, Cham},
series = {Lecture Notes in Comput. Sci.},
shortbooktitle = {CIAC},
url = {https://doi.org/10.1007/978-3-030-17402-6_13},
volume = {11485},
year = {2019}
}
Scaffolding Problems Revisited: Complexity, Approximation and Fixed Parameter Tractable Algorithms, and Some Special Cases
M. Weller, A. Chateau, C. Dallard, and R. Giroudeau.
Algorithmica, Jan. 2018.
Scaffolding Problems Revisited: Complexity, Approximation and Fixed Parameter Tractable Algorithms, and Some Special Cases
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.
@article{WCDG_ALGORITHMICA2018,
title = {Scaffolding Problems Revisited: Complexity, Approximation and Fixed Parameter Tractable Algorithms, and Some Special Cases},
author = {Weller, Mathias and Chateau, Annie and Dallard, Clément and Giroudeau, Rodolphe},
doi = {10.1007/s00453-018-0405-x},
issn = {0178-4617},
journal = {Algorithmica},
month = jan,
mrclass = {05C85 (05C90 68W25 92D10)},
mrnumber = {3782437},
number = {6},
pages = {1771--1803},
shortjournal = {Algorithmica},
url = {https://doi.org/10.1007/s00453-018-0405-x},
volume = {80},
year = {2018}
}
Instance Guaranteed Ratio on Greedy Heuristic for Genome Scaffolding
C. Dallard, M. Weller, A. Chateau, and R. Giroudeau.
In Combinatorial optimization and applications (COCOA), Oct. 2016.
Instance Guaranteed Ratio on Greedy Heuristic for Genome Scaffolding
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 NP-hard and its exact
resolution is generally impossible on large instances.
Hence, heuristics like polynomial-time 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.
@inproceedings{DWCG_COCOA2016,
title = {Instance Guaranteed Ratio on Greedy Heuristic for Genome Scaffolding},
author = {Dallard, Clément and Weller, Mathias and Chateau, Annie and Giroudeau, Rodolphe},
booktitle = {Combinatorial optimization and applications},
doi = {10.1007/978-3-319-48749-6_22},
month = oct,
mrclass = {92D10 (90C35)},
mrnumber = {3614403},
pages = {294--308},
publisher = {Springer, Cham},
series = {Lecture Notes in Comput. Sci.},
shortbooktitle = {COCOA},
url = {https://doi.org/10.1007/978-3-319-48749-6_22},
volume = {10043},
year = {2016}
}