We study a generalization of the classic Global Min-Cut problem, called Global Label Min-Cut (or sometimes Global Hedge Min-Cut ): the edges of the input (multi)graph are labeled (or partitioned into color classes or hedges), and removing all edges of the same label (color or from the same hedge) costs one. The problem asks to disconnect the graph at minimum cost. While the \(st\) -cut version of the problem is known to be \(\mathsf{NP}\) -hard, the above global cut version is known to admit a quasi-polynomial randomized \(n^{\mathcal{O}(\log\mathrm{OPT})}\) -time algorithm due to Ghaffari, Karger, and Panigrahi [SODA 2017]. They consider this as “strong evidence that this problem is in P ” . We show that this is actually not the case. We complete the study of the complexity of the Global Label Min-Cut problem by showing that the quasi-polynomial running time is probably optimal: We show that the existence of an algorithm with running time \((np)^{o(\log n/(\log\log n)^{2})}\) would contradict the Exponential Time Hypothesis, where \(n\) is the number of vertices, and \(p\) is the number of labels in the input. The key step for the lower bound is a proof that Global Label Min-Cut is \(\mathsf{W}\) [1]-hard when parameterized by the number of uncut labels . In other words, the problem is difficult in the regime where almost all labels need to be cut to disconnect the graph.

An elimination tree of a connected graph G is a rooted tree on the vertices of G obtained by choosing a root v and recursing on the connected components of G-v to obtain the subtrees of v. The graph associahedron of G is a polytope whose vertices correspond to elimination trees of G and whose edges correspond to tree rotations, a natural operation between elimination trees. These objects generalize associahedra, which correspond to the case where G is a path. Ito et al. [ICALP 2023] recently proved that the problem of computing distances on graph associahedra is NP-hard. In this paper we prove that the problem, for a general graph G, is fixed-parameter tractable parameterized by the distance k. Prior to our work, only the case where G is a path was known to be fixed-parameter tractable. To prove our result, we use a novel approach based on a marking scheme that restricts the search to a set of vertices whose size is bounded by a (large) function of k.

Musical arrangements have recently been considered from an algorithmic point of view. Demaine and Moses, in 2017, introduced three decision problems associated with musical arrangements. In these problems, the input is a score H consisting of n staves corresponding to the participating instruments and a parameter p, 0 ≤ p ≤ 1. The goal is to determine whether there is a subset H’ c H satisfying some properties, such that in each time unit p% of the input score H is played. In this paper, we take a step forward in this direction. We define more general versions of two of the original problems, which we call general consonant arrangement (con-arr) and general j -simultaneous notes ( j-notes ) with two additional parameters: s , a lower bound for the number of required staves in the solution, and k , a lower bound for the number of time units in which p% of the input score is played. We state the name of the problem followed by the parameter in parentheses to indicate which parameter is being maximized. We show that con-arr( k ) is MAXSNP-hard and that con-arr( s ) and j-notes(s) are not approximable within n 1_ε , for every ε > 0, unless P=NP. Let ∆ be the maximum number of staves that play simultaneously with any single stave at any moment in the music. If ∆ = 4, then con-arr(s) is MAXSNP-hard, because maximum degree 4 independent set is MAXSNP-complete, and it is polynomial-time 1/5-approximable. The j-notes (s) problem is O((∆ + 1) s .n 2 )-time solvable, i.e., it is in FPT with respect to the parameters ∆ and s. We also introduce two new problems we think are of musical interest: the arrangement for k instruments ( k -arrangement) and the time filling by instruments (fill-inst), which we prove to be hard. In particular, k -arrangement is hard even if each stave has exactly 2 notes. Also, k -arrangement is not polynomially approximable within a n 1 - ε factor, for ε > 0, unless P=NP. Finally, fill-inst is in FPT with respect to parameter τ, the maximum number of staves playing in each time, and in the size k of the solution. We prove that if P≠NP, then the best approximation ratio for fill-inst is Θ(log T) , where T is the number of non-silent times of an input.

One way to define the Matching Cut problem is: Given a graph G, is there an edge-cut M of G such that M is an independent set in the line graph of G? We propose the more general Conflict-Free Cut problem: Together with the graph G, we are given a so-called conflict graph Gˆ on the edges of G, and we ask for an edge-cutset M of G that is independent in Gˆ. Since conflict-free settings are popular generalizations of classical optimization problems and Conflict-Free Cut was not considered in the literature so far, we start the study of the problem. We show that the problem is NP-complete even when the maximum degree of G is 5 and Gˆ is 1-regular. The same reduction implies an exponential lower bound on the solvability based on the Exponential Time Hypothesis. We also give parameterized complexity results: We show that the problem is fixed-parameter tractable with the vertex cover number of G as a parameter, and we show W[1]-hardness even when G has a feedback vertex set of size one, and the clique cover number of Gˆ is the parameter. Since the clique cover number of Gˆ is an upper bound on the independence number of Gˆ and thus the solution size, this implies W[1]-hardness when parameterized by the cut size. We list polynomial-time solvable cases and interesting open problems. At last, we draw a connection to a symmetric variant of SAT.

The Independent Cutset problem asks whether there is a set of vertices in a given graph that is both independent and a cutset. This problem is -complete even when the input graph is planar and has maximum degree five. We first present a O ⁎ ( 1.4423 n ) -time algorithm to compute a minimum independent cutset (if any). Since the property of having an independent cutset is MSO 1 -expressible, our main results are concerned with structural parameterizations for the problem considering parameters incomparable with clique-width. We present -time algorithms under the following parameters: the dual of the maximum degree, the dual of the solution size, the size of a dominating set (where a dominating set is given as an additional input), the size of an odd cycle transversal, the distance to chordal graphs, and the distance to P 5 -free graphs. We close by introducing the notion of α -domination, which generalizes key ideas of this article.

Genome rearrangement has been an active area of research in computational comparative genomics for the last three decades. While initially mostly an interesting algorithmic endeavor, now the practical application of rearrangement distance methods and more advanced phylogenetic tasks is becoming common practice, given the availability of many completely sequenced genomes. Several genome rearrangement models have been developed over time, sometimes with surprising computational properties. A prominent example is the fact that computing the reversal distance of two signed permutations is possible in linear time, while for two unsigned permutations it is NP-hard. Therefore one has to always be careful about the precise problem formulation and complexity analysis of rearrangement problems in order not to be fooled. The double distance is the minimum number of genomic rearrangements between a singular and a duplicated genome that - in addition to rearrangements - are separated by a whole genome duplication. At the same time it allows to assign the genes of the duplicated genome to the two paralogous chromosome copies that existed right after the duplication event. Computing the double distance is another example of a tricky hardness landscape: If the distance measure underlying the double distance is the simple breakpoint distance, the problem can be solved in linear time, while with the more elaborate DCJ distance it is NP-hard. Indeed, there is a whole family of distance measures, parameterized by an even number $k$, between the breakpoint distance ($k=2$) at the one end and the DCJ distance ($k=\infty$) at the other end. Only little was known about the hardness border that lies somewhere on the way between these two extremes. Precisely, beneath the two border cases the (linear) problem complexity was known only for $k=4$ and $k=6$. In this paper we close the gap, giving a full picture of the hardness landscape when computing the double distance.

Genome rearrangements are events where large blocks of DNA exchange places during evolution. The analysis of these events is a promising tool for understanding evolutionary genomics, providing data for phylogenetic reconstruction based on genome rearrangement measures. Many pairwise rearrangement distances have been proposed, based on finding the minimum number of rearrangement events to transform one genome into the other, using some predefined operation. When more than two genomes are considered, we have the more challenging problem of rearrangement-based phylogeny reconstruction. Given a set of genomes and a distance notion, there are at least two natural ways to define the "target" genome. On the one hand, finding a genome that minimizes the sum of the distances from this to any other, called the median genome. Finding a genome that minimizes the maximum distance to any other, called the closest genome. Considering genomes as permutations, some distance metrics have been extensively studied. We investigate median and closest problems on permutations over the metrics: breakpoint, swap, block-interchange, short-block-move, and transposition. In biological matters some values are usually small, such as the solution value d or the number k of input permutations. For each of these metrics and parameters d or k, we analyze the closest and the median problems from the viewpoint of parameterized complexity. We obtain the following results: NP-hardness for finding the median/closest permutation for some metrics, even for k = 3; Polynomial kernels for the problems of finding the median permutation of all studied metrics, considering the target distance d as parameter; NP-hardness result for finding the closest permutation by short-block-moves; FPT algorithms and infeasibility of polynomial kernels for finding the closest permutation for some metrics parameterized by the target distance d.

Abstract The hybrid genetic search (HGS) metaheuristic has produced outstanding results for several variants of the vehicle routing problem. A recent implementation of HGS specialized to the capacitated vehicle routing problem (CVRP) is a state‐of‐the‐art method for this variant. This paper proposes an improved HGS for the CVRP obtained by incorporating a new solution generation method into its (re‐)initialization process to guide the search more efficiently and effectively. The solution generation method introduced in this work combines an approach based on frequent patterns extracted from good solutions by a data mining process and a randomized version of the Clarke and Wright savings heuristic. As observed in our experimental comparison, the proposed method significantly outperforms the original algorithm regarding the final gap to the best known solutions and the primal integral.

Abstract. We confirm a conjecture of Gartland and Lokshtanov [SODA 2023]: if for a hereditary graph class [Formula: see text] there exists a constant [Formula: see text] such that no member of [Formula: see text] contains a [Formula: see text]-creature as an induced subgraph or a [Formula: see text]-skinny-ladder as an induced minor, then there exists a polynomial [Formula: see text] such that every [Formula: see text] contains at most [Formula: see text] minimal separators. By a result of Fomin, Todinca, and Villanger [ SIAM J. Comput., 44 (2015), pp. 54–87] the latter entails the existence of polynomial-time algorithms for Maximum Weight Independent Set, Feedback Vertex Set and many other problems, when restricted to an input graph from [Formula: see text]. Furthermore, as shown by Gartland and Lokshtanov, our result implies a full dichotomy of hereditary graph classes defined by a finite set of forbidden induced subgraphs into tame (admitting a polynomial bound of the number of minimal separators) and feral (containing infinitely many graphs with exponential number of minimal separators).

We study a generalization of the classic GLOBAL MIN-CUT problem, called GLOBAL LABEL MIN-CUT (or sometimes GLOBAL HEDGE MIN-CUT): the edges of the input (multi)graph are labeled (or partitioned into color classes or hedges), and removing all edges of the same label (color or from the same hedge) costs one. The problem asks to disconnect the graph at minimum cost. While the st-cut version of the problem is known to be NP-hard, the above global cut version is known to admit a quasi-polynomial randomized nO(log OPT)-time algorithm due to Ghaffari, Karger, and Panigrahi [SODA 2017]. They consider this as “strong evidence that this problem is in P”. We show that this is actually not the case. We complete the study of the complexity of the Global Label Min-Cut problem by showing that the quasi-polynomial running time is probably optimal: We show that the existence of an algorithm with running time (np)o(log n/(log log n)2) would contradict the Randomized Exponential Time Hypothesis, where n is the number of vertices, and p is the number of labels in the input. The key step for the lower bound is a proof that Global Label Min-Cut is W[1]-hard when parameterized by the number of uncut labels. In other words, the problem is difficult in the regime where almost all labels need to be cut to disconnect the graph. To turn this lower bound into a quasi-polynomial-time lower bound, we also needed to revisit the framework due to Marx [Theory Comput. 2010] of proving lower bounds assuming Exponential Time Hypothesis through the SUBGRAPH ISOMORPHISM problem parameterized by the number of edges of the pattern. Here, we provide an alternative simplified proof of the hardness of this problem that is more versatile with respect to the choice of the regimes of the parameters. * This research is a part of a project that has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme Grant Agreement 714704 (LJ, TM, MP, US) and from the Research Council of Norway (LJ).

Given a graph G on n vertices and two integers k and d, the Contraction(vc) problem asks whether one can contract at most k edges to reduce the vertex cover number of G by at least d. Recently, Lima et al. [JCSS 2021] proved that Contraction(vc) admits an XP algorithm running in time f(d)⋅nO(d). They asked whether this problem is FPT under this parameterization. In this article, we prove that: (i) Contraction(vc) is W[1]-hard parameterized by k+d. Moreover, unless the ETH fails, the problem does not admit an algorithm running in time f(k+d)⋅no(k+d) for any function f. This answers negatively the open question stated in Lima et al. [JCSS 2021]. (ii) Contraction(vc) is NP-hard even when k=d. (iii) Contraction(vc) can be solved in time 2O(d)⋅nk−d+O(1). This improves the algorithm of Lima et al. [JCSS 2021], and shows that when k=d, Contraction(vc) is FPT parameterized by d (or by k).

We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class 𝒢 there exists a constant k such that no member of 𝒢 contains a k-creature as an induced subgraph or a k-skinny-ladder as an induced minor, then there exists a polynomial p such that every G ∈ 𝒢 contains at most p(|V(G)|) minimal separators. By a result of Fomin, Todinca, and Villanger [SIAM J. Comput. 2015] the latter entails the existence of polynomial-time algorithms for Maximum Weight Independent Set, Feedback Vertex Set and many other problems, when restricted to an input graph from 𝒢. Furthermore, as shown by Gartland and Lokshtanov, our result implies a full dichotomy of hereditary graph classes defined by a finite set of forbidden induced subgraphs into tame (admitting a polynomial bound of the number of minimal separators) and feral (containing infinitely many graphs with exponential number of minimal separators).

International audience

Clique-width and treewidth are two of the most important and useful graph parameters, and several problems can be solved efficiently when restricted to graphs of bounded clique-width or treewidth. Bounded treewidth implies bounded clique-width, but not vice versa. Problems like Longest Cycle, Longest Path, MaxCut, Edge Dominating Set, and Graph Coloring are fixed-parameter tractable when parameterized by the treewidth, but they cannot be solved in FPT time when parameterized by the clique-width unless FPT = W[1], as shown by Fomin, Golovach, Lokshtanov, and Saurabh [SIAM J. Comput. 2010, SIAM J. Comput. 2014]. For a given problem that is fixed-parameter tractable when parameterized by treewidth, but intractable when parameterized by clique-width, there may exist infinite families of instances of bounded clique-width and unbounded treewidth where the problem can be solved efficiently. In this work, we initiate a systematic study of the parameters co-treewidth (the treewidth of the complement of the input graph) and co-degeneracy (the degeneracy of the complement of the input graph). We show that Longest Cycle, Longest Path, and Edge Dominating Set are FPT when parameterized by co-degeneracy. On the other hand, Graph Coloring is para-NP-complete when parameterized by co-degeneracy but FPT when parameterized by the co-treewidth. Concerning MaxCut, we give an FPT algorithm parameterized by co-treewidth, while we leave open the complexity of the problem parameterized by co-degeneracy. Additionally, we show that Precoloring Extension is fixed-parameter tractable when parameterized by co-treewidth, while this problem is known to be W[1]-hard when parameterized by treewidth. These results give evidence that co-treewidth is a useful width parameter for handling dense instances of problems for which an FPT algorithm for clique-width is unlikely to exist. Finally, we develop an algorithmic framework for co-degeneracy based on the notion of Bondy-Chvátal closure.

For a fixed graph H, the H-IS-Deletion problem asks, given a graph G, for the minimum size of a set S⊆V(G) such that G∖S excludes H as an induced subgraph. We are interested in determining, for a fixed H, the smallest function fH(t) such that H-IS-Deletion can be solved in time fH(t)⋅nO(1) assuming the Exponential Time Hypothesis, where t and n denote the treewidth and the number of vertices of G, respectively. We show that fH(t)=2O(th−2) for every H on h≥3 vertices, and that fH(t)=2O(t) if H is a clique or an independent set. When H deviates slightly from a clique, the function fH(t) suffers a sharp jump: if H is obtained from a clique of size h by removing one edge, then fH(t)=2Θ(th−2). Moreover, fH(t)=2Ω(th) when H=Kh,h, answering a question of Pilipczuk [MFCS 2011].

Abstract Even, Itai, and Shamir (1976) proved simple two‐commodity integral flow is NP‐complete both in the directed and undirected cases. In particular, the directed case was shown to be NP‐complete even if one demand is unitary, which was improved by Fortune, Hopcroft and Wyllie (1980) who proved the problem is still NP‐complete if both demands are unitary. The undirected case, on the other hand, was proved by Robertson and Seymour (1995) to be polynomial‐time solvable if both demands are constant. Nevertheless, the complexity of the undirected case with exactly one constant demand has remained unknown. We close this 40‐year complexity gap, by showing the undirected case is NP‐complete even if exactly one demand is unitary. As a by product, we obtain the NP‐completeness of determining whether a graph contains 1 + d pairwise vertex‐disjoint paths, such that one path is between a given pair of vertices and d paths are between a second given pair of vertices. Additionally, we investigate the complexity of another related network design problem called strict terminal connection.

For a graph parameter π, the Contraction(π) problem consists in, given a graph G and two positive integers k,d, deciding whether one can contract at most k edges of G to obtain a graph in which π has dropped by at least d. Galby et al. [ISAAC 2019, MFCS 2019] recently studied the case where π is the size of a minimum dominating set. We focus on graph parameters defined as the minimum size of a vertex set that hits all the occurrences of graphs in a collection ℋ according to a fixed containment relation. We prove co-NP-hardness results under some assumptions on the graphs in ℋ, which in particular imply that Contraction(π) is co-NP-hard even for fixed k = d = 1 when π is the size of a minimum feedback vertex set or an odd cycle transversal. In sharp contrast, we show that when π is the size of a minimum vertex cover, the problem is in XP parameterized by d.

A knot in a directed graph G is a strongly connected subgraph Q of G with at least two vertices, such that no vertex in V(Q) is an in-neighbor of a vertex in V(G)\V(Q). Knots are important graph structures, because they characterize the existence of deadlocks in a classical distributed computation model, the so-called OR-model. Deadlock detection is correlated with the recognition of knot-free graphs as well as deadlock resolution is closely related to the Knot-Free Vertex Deletion (KFVD) problem, which consists of determining whether an input graph G has a subset S subseteq V(G) of size at most k such that G[V\S] contains no knot. Because of natural applications in deadlock resolution, KFVD is closely related to Directed Feedback Vertex Set. In this paper we focus on graph width measure parameterizations for KFVD. First, we show that: (i) KFVD parameterized by the size of the solution k is W[1]-hard even when p, the length of a longest directed path of the input graph, as well as kappa, its Kenny-width, are bounded by constants, and we remark that KFVD is para-NP-hard even considering many directed width measures as parameters, but in FPT when parameterized by clique-width; (ii) KFVD can be solved in time 2^{O(tw)} x n, but assuming ETH it cannot be solved in 2^{o(tw)} x n^{O(1)}, where tw is the treewidth of the underlying undirected graph. Finally, since the size of a minimum directed feedback vertex set (dfv) is an upper bound for the size of a minimum knot-free vertex deletion set, we investigate parameterization by dfv and we show that (iii) KFVD can be solved in FPT-time parameterized by either dfv+kappa or dfv+p. Results of (iii) cannot be improved when replacing dfv by k due to (i).

A bond of a graph G is an inclusion-wise minimal disconnecting set of G, i.e., bonds are cut-sets that determine cuts [S,V\S] of G such that G[S] and G[V\S] are both connected. Given s,t in V(G), an st-bond of G is a bond whose removal disconnects s and t. Contrasting with the large number of studies related to maximum cuts, there are very few results regarding the largest bond of general graphs. In this paper, we aim to reduce this gap on the complexity of computing the largest bond and the largest st-bond of a graph. Although cuts and bonds are similar, we remark that computing the largest bond of a graph tends to be harder than computing its maximum cut. We show that Largest Bond remains NP-hard even for planar bipartite graphs, and it does not admit a constant-factor approximation algorithm, unless P = NP. We also show that Largest Bond and Largest st-Bond on graphs of clique-width w cannot be solved in time f(w) x n^{o(w)} unless the Exponential Time Hypothesis fails, but they can be solved in time f(w) x n^{O(w)}. In addition, we show that both problems are fixed-parameter tractable when parameterized by the size of the solution, but they do not admit polynomial kernels unless NP subseteq coNP/poly.