A (k,n)-superimposed code is a well known and widely used combinatorial structure that can be represented by a t×n binary matrix such that for any k columns of the matrix and for any column c chosen ...among these k columns, there exists a row in correspondence of which column c has an entry equal to 1 and the remaining k−1 columns have entries equal to 0. Due to the many situations in which superimposed codes find applications, there is an abundant literature that studies the problem of constructing (k,n)-superimposed codes with a small number t of rows. Motivated by applications to conflict-free communication in multiple-access networks, group testing, and data security, we study the problem of constructing superimposed codes that have the additional constraints that the number of 1's in each column of the matrix is constant, and equal to an input parameter w. Our results improve on the known literature in the area. We also extend our findings to other important combinatorial structures, like selectors, generalized superimposed codes, and z-error correcting superimposed codes.
Motivated by applications in sociology, economy and medicine, we study variants of the Target Set Selection problem, first proposed by Kempe, Kleinberg and Tardos. In our scenario one is given a ...graph G=(V,E), integer values t(v) for each vertex v (thresholds), and the objective is to determine a small set of vertices (target set) that activates a given number (or a given subset) of vertices of G within a prescribed number of rounds. The activation process in G proceeds as follows: initially, at round 0, all vertices in the target set are activated; subsequently at each round r⩾1 every vertex of G becomes activated if at least t(v) of its neighbors are already active by round r−1. It is known that the problem of finding a minimum cardinality Target Set that eventually activates the whole graph G is hard to approximate to a factor better than O(2log1−ϵ|V|). In this paper we give exact polynomial time algorithms to find minimum cardinality Target Sets in graphs of bounded clique-width, and exact linear time algorithms for trees.
Given two discrete random variables <inline-formula> <tex-math notation="LaTeX">X </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">Y </tex-math></inline-formula>, with ...probability distributions <inline-formula> <tex-math notation="LaTeX">p=(p_{1}, \ldots , p_{n}) </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">q=(q_{1}, \ldots , q_{m}) </tex-math></inline-formula>, respectively, let us denote by <inline-formula> <tex-math notation="LaTeX">{\mathcal{ C}}(p, q) </tex-math></inline-formula> the set of all couplings of <inline-formula> <tex-math notation="LaTeX">p </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">q </tex-math></inline-formula>, that is, the set of all bivariate probability distributions that have <inline-formula> <tex-math notation="LaTeX">p </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">q </tex-math></inline-formula> as marginals. In this paper, we study the problem of finding a joint probability distribution in <inline-formula> <tex-math notation="LaTeX">{\mathcal{ C}}(p, q) </tex-math></inline-formula> of minimum entropy (equivalently, a coupling that maximizes the mutual information between <inline-formula> <tex-math notation="LaTeX">X </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">Y </tex-math></inline-formula>), and we discuss several situations where the need for this kind of optimization naturally arises. Since the optimization problem is known to be NP-hard, we give an efficient algorithm to find a joint probability distribution in <inline-formula> <tex-math notation="LaTeX">{\mathcal{ C}}(p, q) </tex-math></inline-formula> with entropy exceeding the minimum possible at most by 1 bit, thus providing an approximation algorithm with an additive gap of at most 1 bit. Leveraging on this algorithm, we extend our result to the problem of finding a minimum-entropy joint distribution of arbitrary <inline-formula> <tex-math notation="LaTeX">k\geq {2} </tex-math></inline-formula> discrete random variables <inline-formula> <tex-math notation="LaTeX">X_{1}, \ldots , X_{k} </tex-math></inline-formula>, consistent with the known <inline-formula> <tex-math notation="LaTeX">k </tex-math></inline-formula> marginal distributions of the individual random variables <inline-formula> <tex-math notation="LaTeX">X_{1}, \ldots , X_{k} </tex-math></inline-formula>. In this case, our algorithm has an additive gap of at most <inline-formula> <tex-math notation="LaTeX">\log k </tex-math></inline-formula> from optimum. We also discuss several related applications of our findings and extensions of our results to entropies different from the Shannon entropy.
This paper deals with the complexity of some natural graph problems parameterized by some measures that are restrictions of clique-width, such as modular-width and neighborhood diversity. We ...introduce a novel parameter, called iterated type partition number, that can be computed in linear time and nicely places between modular-width and neighborhood diversity. We prove that the Equitable Coloring problem is W1-hard when parameterized by the iterated type partition number. This result extends to modular-width, answering an open question on the complexity of Equitable Coloring when parameterized by modular-width. On the contrary, we show that the Equitable Coloring problem is FPT when parameterized by neighborhood diversity.
Furthermore, we present a scheme for devising FPT algorithms parameterized by iterated type partition number, which enables us to find optimal solutions for several graph problems. As an example, in this paper, we present algorithms parameterized by the iterated type partition number of the input graph for some generalized versions of the Maximum Clique, Minimum Graph Coloring, (Total) Minimum Dominating Set, Minimum Vertex Cover and Maximum Independent Set problems. Each algorithm outputs not only the optimal value but also the optimal solution. We stress that while the considered problems are already known to be FPT with respect to modular-width, the novel algorithms are both simpler and more efficient. We finally show that the proposed scheme can be used to devise polynomial kernels, with respect to iterated type partition number, for the decisional version of most of the problems mentioned above.
Abstract Parameterized complexity, introduced to efficiently solve NP‐hard problems for small values of a fixed parameter, has been recently used as a tool to speed up algorithms for tractable ...problems. Following this line of research, we design algorithms parameterized by neighborhood diversity () for several graph theoretic problems in : Maximum ‐ Matching , Triangle Counting and Listing , Girth , Global Minimum Vertex Cut , and Perfect Graphs Recognition . Such problems are known to admit algorithms parameterized by modular‐width () and consequently—as is a special case of —by . However, the proposed novel algorithms allow for improving the computational complexity from time —where and denote, respectively, the number of vertices and edges in the input graph—to time which is only additive in the size of the input. Then we consider some classical NP‐hard problems ( Maximum independent set , Maximum clique , and Minimum dominating set ) and show that for several classes of hereditary graphs, they admit linear time algorithms for sufficiently small—nonnecessarily constant—values of the neighborhood diversity parameter.
Identifying the most influential spreaders is an important issue for the study of the dynamics of information diffusion in complex networks. In this paper we analyze the following spreading model. ...Initially, a few nodes know a piece of information and are active spreaders of it. At subsequent rounds, spreaders communicate the information to their neighbors. Upon receiving the information, a node becomes aware of it but does not necessarily become a spreader; it starts spreading only if it gets the information from a sufficiently large number of its neighbors. A set of initial spreaders that guarantees that all the nodes become aware of the information is called a perfect seed set. We study the problem of choosing a perfect seed set of minimum size. We provide hardness results and show that the problem becomes tractable on trees. In case of general graphs, we provide an efficient algorithm and validate its effectiveness (in terms of the solution size) on real-life networks. We also study perfect seed sets in dense graphs and derive a bound on the size of a dominating set in Ore graphs.
Dual domination problems in graphs Cordasco, Gennaro; Gargano, Luisa; Rescigno, Adele A.
Journal of computer and system sciences,
September 2022, 2022-09-00, Letnik:
128
Journal Article
Recenzirano
We introduce a novel domination problem, which we call Dual Domination (DD). We assume that the nodes in a network are partitioned into two categories: Positive nodes (V+) and negative nodes (V−). We ...study the Maximum Bounded Dual Domination, where, given a bound k, the problem is to find a set D⊆V+, which maximizes the number of nodes dominated in V+, dominating at most k nodes in V−. We show that such problem is hard to approximate to a factor better than (1−1/e). We give a polynomial time algorithm with approximation guaranteed (1−e−1/Δ), where Δ represents the maximum number of neighbors in V+ of any node in V−, and an O(|V|k2) time algorithm to solve the problem on trees. We also study two related problems named Maximum Dual Domination and minimum Negative Dual Domination. For both problems, we show hardness results and provide O(|V|) time algorithms on trees.
We consider conflict-free colorings of graph neighborhoods: Each vertex of the graph must be assigned a color so that for each vertex v there is at least one color appearing exactly once in the ...neighborhood of v. The goal is to minimize the number of used colors. We consider both the case of closed neighborhoods, when the neighborhood of a node includes the node itself, and the case of open neighborhoods when a node does not belong to its neighborhood. In this paper, we study complexity aspects of the problem. We show that the problem of conflict-free coloring of closed neighborhoods is NP-complete. Moreover, we give non-approximability results for the conflict-free coloring of open neighborhoods. From a positive point of view, both problems become tractable if parameterized by the vertex cover number or the neighborhood diversity number of the graph. We present simple algorithms which improve on existing results.
PDF
