• NP-Completeness and APX-Hardness • We prove that the problems MinFixMask OPT and MinFixMask BOUND are NP-complete. • We establish that FixMasks + is NP-complete and APX-hard. • We show NP-completeness of DFixMasks + . • Exact, FPT, and Approximation Algorithms for DFixMasks + • We design a fixed-parameter tractable (FPT) algorithm running in O *(2 M ) time, parameterized by the number of shield configurations M . • We present a polynomial-time 1 M -approximation algorithm. • We propose an exponential k M -approximation method (for a treatment plan length k ). • We provide a tight ( 1 − 1 e ) -approximation algorithm by exploiting monotonicity and submodularity of the objective function. • Quasi-Polynomial Algorithms and Logarithmic Approximations • We develop quasi-polynomial-time algorithms for MinFixMask OPT , MinFixMask OPT + , MinFixMask BOUND , and MinFixMask BOUND + , assuming that the maximum prescribed dose d ^ max is polynomially bounded. • Under the same assumption, we achieve polynomial-time approximation algorithms with a logarithmic factor log ( d ^ max ) for MinFixMask OPT and MinFixMask OPT + . • Polynomial-Time Solvable Special Cases • We identify polynomial-time solvable cases: FixMask and FixMasks + when M = 1 . • We show that the problems MinFixMask BOUND and MinFixMask BOUND + can be solved in polynomial time when T max 1, N ;. In this paper, we study a combinatorial problem which arises in the development of innovative treatment strategies and equipment using tunable shields in internal radiotherapy. From an algorithmic point of view, the problem is related to circular integer word decomposition into circular binary words under constraints. We consider several variants of the problem, depending on constraints and parameters and present exact, approximation, fixed parameter tractable algorithms and NP-hardness and APX-hardness results.

In this contribution we introduce two combinatorial problems related to graph string matching, motivated by recent approaches in computational genomics. Given a DAG where each node is labeled by a symbol, the problems aim to find a path in the DAG whose nodes contain all (or the maximum number of) symbols of the alphabet. We introduce a decision problem, Σ-Representing Path , that asks whether there exists a path that contains all the symbols of the alphabet, and an optimization problem, called Maximum Representing Path , that asks for a path that contains the maximum number of symbols. We analyze the complexity of the problems, showing the NP-completeness of Σ-Representing Path when each symbol labels at most three nodes in the DAG, and showing the APX-hardness of Maximum Representing Path when each symbol labels at most two nodes in the DAG. We complement the first result by giving a polynomial-time algorithm for Σ-Representing Path when each symbol labels at most two nodes in the DAG. Then we investigate the parameterized complexity of the two problems for two parameters: (1) the number of symbols in a solution and (2) the distance from a set of disjoint paths. We show that both problems are FPT when parameterized by the former parameter, and W[1]-hard for the latter. We consider the approximation of Maximum Representing Path , and we give an approximation algorithm of factor the maximum number of occurrences of a symbol and an approximation algorithm of factor O P T , where OPT is the number of distinct symbols in an optimal solution. We also show that Maximum Representing Path cannot be approximated within factor e e − 1 − α , for any constant α > 0, unless NP ⊆ DTIME (| V | O (log log | V |) ) ( V is the set of nodes of the DAG).

We consider a variant of the Vertex Cover problem on temporal graphs, called Minimum Timeline Cover (k-MinTimelineCover). Temporal graphs are used to model complex systems, describing how edges (relations) change in a discrete time domain. The k-MinTimelineCover problem has been introduced in complex data summarization and synthesis jobs. Given a temporal graph G, k-MinTimelineCover asks to define k activity intervals for each vertex, such that each temporal edge is covered by at least one active interval. The objective function is the minimization of the sum of interval lengths. k-MinTimelineCover is NP-hard and even hard to approximate within any factor for k > 1. While the literature has mainly focused on the cases k = 1, in this contribution we consider the case k > 1. We first present an ILP formulation that is able to solve the problem on moderate size instances. Then we develop an efficient heuristic, based on local search which is built on top of the solution of an existing literature method. Finally, we present an experimental evaluation of our algorithms on synthetic data sets, that shows in particular that our heuristic has a consistent improvement on the state-of-the art method.

The anti-Ramsey numbers are a fundamental notion in graph theory, introduced in 1978, by Erdős, Simonovits and Sós. For given graphs G and H the anti-Ramsey number ar ( G , H ) is defined to be the maximum number k such that there exists an assignment of k colors to the edges of G in which every copy of H in G has at least two edges with the same color. Usually, combinatorists study extremal values of anti-Ramsey numbers for various classes of graphs. There are works on the computational complexity of the problem when H is a star. Along this line of research, we study the complexity of computing the anti-Ramsey number ar ( G , P k ) , where P k is a path of length k . First, we observe that when k is close to n (the number of vertices in G ), the problem is hard; hence, the challenging part is the computational complexity of the problem when k is a fixed constant. We provide a characterization of the problem for paths of constant length. Our first main contribution is to prove that computing ar ( G , P k ) for every integer k ≥ 3 is NP-hard. We obtain this by providing several structural properties of such coloring in graphs. We also study the exact complexity of the precolored version and show that there is no subexponential algorithm for the problem unless ETH fails for any fixed constant k .

This study aims to improve the transportation sector by leveraging Graph Neural Networks (GNN) and solutions to the Traveling Salesman Problem (TSP) to enhance the deployment of charging stations in an urban environment. We focus on the city of Bucharest where we use a dataset with 153 existing charging stations and 220 potential locations for new charging stations and make use of GNN to rank the latter based on suitability. The proposed model takes into account geographical and infrastructural data and predicts the new charging stations in a non-conventional manner. Subsequently, we apply various TSP solvers to find the optimal sequence for installing the new stations, ensuring spatial efficiency. This research aims to set a new benchmark for electric vehicles charging stations infrastructure, as well as showcase the importance of AI in smart city planning. Our work can offer, in the same time, guidance for urban planners and stakeholder in the EV ecosystem.

A gapped palindrome is a string uvu^{R}, where u^{R} represents the reverse of string u. In this paper we show three efficient algorithms for counting the occurrences of gapped palindromes in a given string S of length N. First, we present a solution in O(N) time for counting all gapped palindromes without additional constraints. Then, in the case where the length of v is constrained to be in an interval [g, G], we show an algorithm with running time O(N log N). Finally, we show an algorithm in O(N log² N) time for a more general case where we count gapped palindromes uvu^{R}, where u^{R} starts at position i with g(i) ≤ v ≤ G(i), for all positions i.

Wireless body area networks (WBANs) play a paramount role in modern health-care systems and bring numerous benefits. Modern WBANs provide a promising service especially for elderly people suffering from heart disease, Alzheimer, etc., which enable them to live safely and independently. Medical institutions tend to use WBANs to provide real-time monitoring of remote patients outside hospitals, which helps saving their lives by means of instant and proper responses at emergency situations. However, in 2020, the world was affected by COVID-19 pandemic and thousands of new cases are discovered daily all over the world. The pandemic provoked a serious lack in professional staff and in many countries there were not enough beds in hospitals for patients with COVID-19 symptoms. This in turn increases the demand for WBANs, which can help medical institutions to withstand harmful consequences of the pandemic and to ensure regular patients monitoring. In this context, very recently, Fotouhi et al. proposed a new lightweight authentication scheme to secure patient's sensitive data in WBANs. The authors claimed that their scheme is secure against various known attacks and is efficient to be applied in practice. However, we analyze Fotouhi et al.'s scheme and find out that their scheme is prone to several attacks. In this paper, we point out the weaknesses associated with their proposed lightweight authentication scheme.

The anti-Ramsey numbers are a fundamental notion in graph theory, introduced in 1978, by Erdös, Simonovits and Sós. For given graphs G and H the anti-Ramsey number ar(G,H) is defined to be the maximum number k such that there exists an assignment of k colors to the edges of G in which every copy of H in G has at least two edges with the same color. Usually, combinatorists study extremal values of anti-Ramsey numbers for various classes of graphs. There are works on the computational complexity of the problem when H is a star. Along this line of research, we study the complexity of computing the anti-Ramsey number ar(G,P_k), where P_k is a path of length k. First, we observe that when k is close to n, the problem is hard; hence, the challenging part is the computational complexity of the problem when k is a fixed constant. We provide a characterization of the problem for paths of constant length. Our first main contribution is to prove that computing ar(G,P_k) for every integer k > 2 is NP-hard. We obtain this by providing several structural properties of such coloring in graphs. We investigate further and show that approximating ar(G,P₃) to a factor of n^{-1/2 - ε} is hard already in 3-partite graphs, unless P = NP. We also study the exact complexity of the precolored version and show that there is no subexponential algorithm for the problem unless ETH fails for any fixed constant k. Given the hardness of approximation and parametrization of the problem, it is natural to study the problem on restricted graph families. Along this line, we first introduce the notion of color connected coloring, and, employing this structural property, we obtain a linear time algorithm to compute ar(G,P_k), for every integer k, when the host graph, G, is a tree.

A factorization of a string w is a partition of w into substrings \(u_1,\dots ,u_k\) such that \(w=u_1 u_2 \cdots u_k\) . Such a partition is called equality-free if no two factors are equal: \(u_i \ne u_j, \forall i,j\) with \(i \ne j\) . The maximum equality-free factorization problem is to decide, for a given string w and integer k , whether w admits an equality-free factorization with k factors. Equality-free factorizations have lately received attention because of their application in DNA self-assembly. Condon et al. (CPM 2012) study a version of the problem and show that it is \(\mathcal {NP}\) -complete to decide if there exists an equality-free factorization with an upper bound on the length of the factors. At STACS 2015, Fernau et al. show that the maximum equality-free factorization problem with a lower bound on the number of factors is \(\mathcal {NP}\) -complete. Shortly after, Schmid (CiE 2015) presents results concerning the Fixed Parameter Tractability of the problems. In this paper we approach equality free factorizations from a practical point of view i.e. we wish to obtain good solutions on given instances. To this end, we provide approximation algorithms, heuristics, Integer Programming models, an improved FPT algorithm and we also conduct experiments to analyze the performance of our proposed algorithms. Additionally, we study a relaxed version of the problem where gaps are allowed between factors and we design a constant factor approximation algorithm for this case. Surprisingly, after extensive experiments we conjecture that the relaxed problem has the same optimum as the original.

An important area of computational biology consists in problems inspired by genome evolution that can be solved using combinatorial algorithms. One of these problems is to calculate the evolutionary distance between two genomes of different organisms by determining the minimum number of genome rearrangements needed to obtain one from the other. The aim of our work is to propose a new algorithm for determining the evolutionary distance by translocations. We represent the chromosomes in a genome as a set of strings over the DNA alphabet {A, T,C,G}. Given two strings, the translocation operation is defined as swapping two prefixes between these strings such that two new strings are obtained. When all the strings are swapping equal length prefixes, the translocation distance is called uniform. The uniform translocation distance was initially introduced by Martín-Vide and Mitrana [7]. Starting from their work, we introduce a new polynomial time exact algorithm to compute the translocation distance for a target set of size two.

Recently, hardness results for problems in P were achieved using reasonable complexity-theoretic assumptions such as the Strong Exponential Time Hypothesis. According to these assumptions, many graph-theoretic problems do not admit truly subquadratic algorithms. A central technique used to tackle the difficulty of the above-mentioned problems is fixed-parameter algorithms with polynomial dependency in the fixed parameter (P-FPT). Applying this technique to clique-width , an important graph parameter, remained to be done. In this article, we study several graph-theoretic problems for which hardness results exist such as cycle problems , distance problems , and maximum matching . We give hardness results and P-FPT algorithms, using clique-width and some of its upper bounds as parameters. We believe that our most important result is an algorithm in O ( k 4 ⋅ n + m )-time for computing a maximum matching, where k is either the modular-width of the graph or the P 4 -sparseness. The latter generalizes many algorithms that have been introduced so far for specific subclasses such as cographs. Our algorithms are based on preprocessing methods using modular decomposition and split decomposition. Thus they can also be generalized to some graph classes with unbounded clique-width.

We address the following general question: given a graph class C on which we can solve Maximum Matching in (quasi) linear time, does the same hold true for the class of graphs that can be modularly decomposed into C? As a way to answer this question for distance-hereditary graphs and some other superclasses of cographs, we study the combined effect of modular decomposition with a pruning process over the quotient subgraphs. We remove sequentially from all such subgraphs their so-called one-vertex extensions (i.e., pendant, anti-pendant, twin, universal and isolated vertices). Doing so, we obtain a "pruned modular decomposition", that can be computed in quasi linear time. Our main result is that if all the pruned quotient subgraphs have bounded order then a maximum matching can be computed in linear time. The latter result strictly extends a recent framework in (Coudert et al., SODA'18). Our work is the first to explain why the existence of some nice ordering over the modules of a graph, instead of just over its vertices, can help to speed up the computation of maximum matchings on some graph classes.

We make progress on the fine-grained complexity of Maximum-Cardinality Matching on graphs of bounded clique-width. Quasi linear-time algorithms for this problem have been recently proposed for the important subclasses of bounded-treewidth graphs (Fomin et al., SODA'17) and graphs of bounded modular-width (Coudert et al., SODA'18). We present such algorithm for bounded split-width graphs - a broad generalization of graphs of bounded modular-width, of which an interesting subclass are the distance-hereditary graphs. Specifically, we solve Maximum-Cardinality Matching in O((k log^2{k})*(m+n) * log{n})-time on graphs with split-width at most k. We stress that the existence of such algorithm was not even known for distance-hereditary graphs until our work. Doing so, we improve the state of the art (Dragan, WG'97) and we answer an open question of (Coudert et al., SODA'18). Our work brings more insights on the relationships between matchings and splits, a.k.a., join operations between two vertex-subsets in different connected components. Furthermore, our analysis can be extended to the more general (unit cost) b-Matching problem. On the way, we introduce new tools for b-Matching and dynamic programming over split decompositions, that can be of independent interest.

Recently, hardness results for problems in P were achieved using reasonable complexity theoretic assumptions such as the Strong Exponential Time Hypothesis. According to these assumptions, many graph theoretic problems do not admit truly subquadratic algorithms. A central technique used to tackle the difficulty of the above mentioned problems is fixed-parameter algorithms with polynomial dependency in the fixed parameter (P-FPT). Applying this technique to clique-width, an important graph parameter, remained to be done. In this paper we study several graph theoretic problems for which hardness results exist such as cycle problems, distance problems and maximum matching. We give hardness results and P-FPT algorithms, using clique-width and some of its upper-bounds as parameters. We believe that our most important result is an O(k4 · n + m)-time algorithm for computing a maximum matching where k is either the modular-width or the P4-sparseness. The latter generalizes many algorithms that have been introduced so far for specific subclasses such as cographs. Our algorithms are based on preprocessing methods using modular decomposition and split decomposition. Thus they can also be generalized to some graph classes with unbounded clique-width.

Communication overhead is the most commonly used performance metric for the operation complexity of distributed algorithms in message-passing environments. However, aside with communication, many distributed operations utilize complex computations to reach their desired outcomes. Therefore, a most accurate operation latency measure should account of both computation and communication metrics. In this paper we focus on the efficiency of read and write operations in an atomic read/write shared memory emulation in the message-passing environment. We examine the operation complexity of the best known atomic register algorithm, that allows all read and write operations to complete in a single communication round-trip. Such operations are called fast. At its heart, the algorithm utilizes a predicate to allow processes to compute their outcome. We show that the predicate used is computationally hard, by devising a computationally equivalent problem and reducing that to Maximum Biclique, a known NP-hard problem. To improve the computational complexity of the algorithm we derive a new predicate that leads to a new algorithm, we call ccFast, and has the following properties: (i) can be computed in polynomial time, rendering each read operation in ccFast tractable compared to the read operations in the original algorithm, (ii) the messages used in ccFast are reduced in size, compared to the original algorithm, by almost a linear factor, (iii) allows all operations in ccFast to be fast, and (iv) allows ccFast to preserve atomicity. A linear time}algorithm for the computation of the new predicate is presented along with an analysis of the message complexity of the new algorithm. We believe that the new algorithm redefines the term fast capturing both the communication and the computation metrics of each operation.

RNA-Seq technology offers new high-throughput ways for transcript identification and quantification based on short reads, and has recently attracted great interest. This is achieved by constructing a weighted DAG whose vertices stand for exons, and whose arcs stand for split alignments of the RNA-Seq reads to the exons. The task consists of finding a number of paths, together with their expression levels, which optimally explain the weights of the graph under various fitting functions, such as least sum of squared residuals. In (Tomescu et al. BMC Bioinformatics, 2013) we studied this genome-guided multi-assembly problem when the number of allowed solution paths was linear in the number of arcs. In this paper, we further refine this problem by asking for a bounded number k of solution paths, which is the setting of most practical interest. We formulate this problem in very broad terms, and show that for many choices of the fitting function it becomes NP-hard. Nevertheless, we identify a natural graph parameter of a DAG G, which we call arc-width and denote ⟨G⟩, and give a dynamic programming algorithm running in time O(W(k)⟨G⟩(k)(⟨G⟩+ k)n) , where n is the number of vertices and W is the maximum weight of G. This implies that the problem is fixed-parameter tractable (FPT) in the parameters W, ⟨G⟩, and k. We also show that the arc-width of DAGs constructed from simulated and real RNA-Seq reads is small in practice. Finally, we study the approximability of this problem, and, in particular, give a fully polynomial-time approximation scheme (FPTAS) for the case when the fitting function penalizes the maximum ratio between the weights of the arcs and their predicted coverage.