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, vol. 334, pp. 45–62.
    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.
  • Functionality of box intersection graphs
    C. Dallard, V. Lozin, M. Milanič, K. Štorgel, and V. Zamaraev.
    Available on arXiv only.
    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$.

2022

  • On Constrained Intersection Representations of Graphs and Digraphs
    F. Cicalese, C. Dallard, and M. Milanič.
    In 33rd International Symposium on Algorithms and Computation (ISAAC), Dagstuhl, Germany, vol. 248, pp. 38:1–38:15.
    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.
  • Conditions for minimally tough graphs
    C. Dallard, B. Fernández, G. Y. Katona, M. Milanič, and K. Varga.
    Available on arXiv only.
    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.
  • Computing Tree Decompositions with Small Independence Number
    C. Dallard, F. V. Fomin, P. A. Golovach, T. Korhonen, and M. Milanič.
    Available on arXiv only.
    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$.
  • Treewidth versus clique number. II. Tree-independence number
    C. Dallard, M. Milanič, and K. Štorgel.
    Available on arXiv only.
    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].
  • Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure
    C. Dallard, M. Milanič, and K. Štorgel.
    Available on arXiv only.
    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.
  • Finding $k$-community structures in special graph classes
    N. Baghirova, C. Dallard, B. Ries, and D. Schindl.
    Available on arXiv only.
    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 present a necessary and sufficient condition for a forest $F$ to admit a $k$-community structure, for any integer $k\ge 2$. Furthermore, if such a $k$-community exists, it can be found in polynomial time. This generalises a result of Bazgan et al. (2018), who showed that all trees of size at least four, except stars, admit a $2$-community that can be found in polynomial time. We also show that, if communities are allowed to have size one, then every forest with at least $k≥2$ vertices admits a $k$-community structure that can be found in polynomial time. We then consider threshold graphs and show that every such connected 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, it can be found in polynomial time. Finally, we introduce a new infinite family of connected graphs that do not admit any $2$-community structure (even if communities are allowed to have size one). Such a family was presented in Bazgan et al. (2020), but its graphs all contained an even number of vertices. The graphs in our new family may contain an even or an odd number of vertices.

2021

  • Colourful components in $k$-caterpillars and planar graphs
    J. Chlebíková and C. Dallard.
    Theoretical Computer Science, vol. 895, pp. 137–150.
    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].
  • 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).
    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.
  • 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).
    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.
  • 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 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.
  • 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.
    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.
  • Vertex cover at distance on H-free graphs
    C. Dallard, M. Krbezlija, and M. Milanič.
    In Combinatorial Algorithms (IWOCA), pp. 237–251.
    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.
  • Graphs with at most two moplexes
    C. Dallard, R. Ganian, M. Hatzel, M. Krnc, and M. Milanič.
    Available on arXiv only.
    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.

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 (ISAAC), vol. 181, pp. 44:1–44:17.
    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.
  • 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), pp. 92–105.
    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.
  • 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.
    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].

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.
    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.
  • 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), vol. 11638, pp. 136–147.
    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.
  • Complexity of scheduling for DARP with soft ride times
    J. Chlebíková, C. Dallard, and N. Paulsen.
    In Algorithms and complexity (CIAC), vol. 11485, pp. 149–160.
    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.

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.
    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.

2016

  • Instance guaranteed ratio on greedy heuristic for genome scaffolding
    C. Dallard, M. Weller, A. Chateau, and R. Giroudeau.
    In Combinatorial optimization and applications (COCOA), vol. 10043, pp. 294–308.
    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.