1,721,195 research outputs found
Preface [to SOFSEM 2020: Theory and Practice of Computer Science. 46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, Limassol, Cyprus, January 20–24, 2020, Proceedings]
No full textFinding disjoint paths on edge-colored graphs: more tractability results
No full textThe problem of finding the maximum number of vertex-disjoint uni-color paths in an edge-colored graph (called MaxCDP) has been recently introduced in literature, motivated by applications in social network analysis. In this paper we investigate how the complexity of the problem depends on graph parameters (namely the number of vertices to remove to make the graph a collection of disjoint paths and the size of the vertex cover of the graph), which makes sense since graphs in social networks are not random and have structure. The problem was known to be hard to approximate in polynomial time and not fixed-parameter tractable (FPT) for the natural parameter. Here, we show that it is still hard to approximate, even in FPT-time. Finally, we introduce a new variant of the problem, called MaxCDDP, whose goal is to find the maximum number of vertex-disjoint and color-disjoint uni-color paths. We extend some of the results of MaxCDP to this new variant, and we prove that unlike MaxCDP, MaxCDDP is already hard on graphs at distance two from disjoint paths
An FPT algorithm for timeline cover
Full text linkOne of the most studied problem in theoretical computer science, VERTEX COVER, has been recently considered in the temporal graph framework. Here we study a VERTEX COVER variant, called k-TIMELINECOVER. Given a temporal graph k-TIMELINECOVER asks to define an interval for each vertex so that for every temporal edge existing in a timestamp t, at least one of the endpoints has an interval that includes t. The goal is to decide whether it is possible to cover every temporal edge while using vertex intervals of total span at most k. k-TIMELINECOVER has been shown to be NP-hard, but its parameterized complexity has not been fully understood when parameterizing by the span of the solution. We settle this open problem by giving an FPT algorithm that combines two techniques, a modified form of iterative compression and a reduction to DIGRAPH PAIR CUT
Correcting gene trees by leaf insertions: complexity and approximation
Full text linkGene tree correction has recently gained interest in phylogenomics, as it gives insights in understanding the evolution of gene families. Following some recent approaches based on leaf edit operations, we consider a variant of the problem where a gene tree is corrected by inserting leaves with labels in a multiset M. We show that the problem of deciding whether a gene tree can be corrected by inserting leaves with labels in M is NP-complete. Then, we consider an optimization variant of the problem that asks for the correction of a gene tree with leaves labeled by a multiset M′, with M′ ⊇ M, having minimum size. For this optimization variant of the problem, we present a factor 2 approximation algorithm
Covering a Graph with Densest Subgraphs
No full textFinding densest subgraphs is a fundamental problem in graph mining, with several applications in different fields. In this paper, we consider two variants of the problem of covering a graph with k densest subgraphs, where k≥2. The first variant aims to find a collection of k subgraphs of maximum density, the second variant asks for a set of k subgraphs such that they maximize an objective function that includes the sum of the subgraphs densities and a distance function, in order to differentiate the computed subgraphs. We show that the first variant of the problem is solvable in polynomial time, for any k≥2. For the second variant, which is NP-hard for k≥3, we present an approximation algorithm that achieves a factor of 37. The approximation algorithm is obtained by showing that a related problem, that of finding k distinct densest subgraphs can be solved in polynomial time
On the complexity of temporal arborescence reconfiguration
Full text linkIn this contribution we study the ARBORESCENCE RECONFIGURATION on temporal digraphs (TEMPORAL ARBORESCENCE RECONFIGURATION). The problem, given two temporal arborescences in a temporal digraph, asks for the minimum number of arc flips, i.e., arc exchanges, that result in a sequence of temporal arborescences transforming one into the other. We analyze the complexity of the problem, taking into account also its approximation and parameterized complexity, even in restricted cases. First, we solve an open problem showing that TEMPORAL ARBORESCENCE RECONFIGURATION is NP-hard for two timestamps. Then we show that even if the two temporal arborescences differ only by two pairs of arcs, then the problem is not approximable within factor bln|V(D)|, for any constant 0<1, where V(D) is the set of vertices of the temporal arborescences. Finally, we prove that TEMPORAL ARBORESCENCE RECONFIGURATION is W[1]-hard when parameterized by the number of arc flips needed to transform one temporal arborescence into the other
Exact and approximation algorithms for covering timeline in temporal graphs
Full text linkWe consider a variant of vertex cover on temporal graphs that has been recently defined for summarization of timeline activities in temporal graphs. The problem has been proved to be NP-hard, even for several restrictions of the time domain and vertex degree. We present novel algorithmic contributions for the problem and we give an approximation algorithm of factor O ( T log n ) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}\end{document} , on a temporal graph of T timestamps and n vertices. We focus then on the NP-hard restriction of the problem, where at most one temporal edge is defined in each timestamp. For this restriction we present a 4 ( T - 1 ) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}\end{document} approximation algorithm and a parameterized algorithm (a reduction to kernel) for parameter the cost, called span, of the solution
On the Tractability of Covering a Graph with 2-Clubs
Full text linkCovering a graph with cohesive subgraphs is a classical problem in theoretical computer science, for example when the cohesive subgraph model considered is a clique. In this paper, we consider as a model of cohesive subgraph the 2-clubs, which are induced subgraphs of diameter at most 2. We prove new complexity results on the Min 2-Club Cover problem, a variant recently introduced in the literature which asks to cover the vertices of a graph with a minimum number of 2-clubs. First, we answer an open question on the decision version of Min 2-Club Cover that asks if it is possible to cover a graph with at most two 2-clubs, and we prove that it is W[1]-hard when parameterized by the distance to a 2-club. Then, we consider the complexity of Min 2-Club Cover on some graph classes. We prove that Min 2-Club Cover remains NP-hard on subcubic planar graphs, W[2]-hard on bipartite graphs when parameterized by the number of 2-clubs in a solution, and fixed-parameter tractable on graphs having hounded treewidth
Computing the k densest subgraphs of a graph
No full textComputing cohesive subgraphs is a central problem in graph theory. While many formulations of cohesive subgraphs lead to NP-hard problems, finding a densest subgraph can be done in polynomial-time. As such, the densest subgraph model has emerged as the most popular notion of cohesiveness. Recently, the data mining community has started looking into the problem of computing k densest subgraphs in a given graph, rather than one. In this paper we consider a natural variant of the k densest subgraphs problem, where overlap between solution subgraphs is allowed with no constraint. We show that the problem is fixed-parameter tractable with respect to k, and admits a PTAS for constant k. Both these algorithms complement nicely the previously known O (nk) algorithm for the problem. (c) 2022 Elsevier B.V. All rights reserved
- …
