115 research outputs found
Cluster Deletion on Interval Graphs and Split Related Graphs
No full textIn the Cluster Deletion problem the goal is to remove the minimum number of edges of a given graph, such that every connected component of the resulting graph constitutes a clique. It is known that the decision version of Cluster Deletion is NP-complete on (P_5-free) chordal graphs, whereas Cluster Deletion is solved in polynomial time on split graphs. However, the existence of a polynomial-time algorithm of Cluster Deletion on interval graphs, a proper subclass of chordal graphs, remained a well-known open problem. Our main contribution is that we settle this problem in the affirmative, by providing a polynomial-time algorithm for Cluster Deletion on interval graphs. Moreover, despite the simple formulation of the algorithm on split graphs, we show that Cluster Deletion remains NP-complete on a natural and slight generalization of split graphs that constitutes a proper subclass of P_5-free chordal graphs. Although the later result arises from the already-known reduction for P_5-free chordal graphs, we give an alternative proof showing an interesting connection between edge-weighted and vertex-weighted variations of the problem. To complement our results, we provide faster and simpler polynomial-time algorithms for Cluster Deletion on subclasses of such a generalization of split graphs
Maximizing the Strong Triadic Closure in Split Graphs and Proper Interval Graphs
No full textIn social networks the Strong Triadic Closure is an assignment of the edges with strong or weak labels such that any two vertices that have a common neighbor with a strong edge are adjacent. The problem of maximizing the number of strong edges that satisfy the strong triadic closure was recently shown to be NP-complete for general graphs. Here we initiate the study of graph classes for which the problem is solvable. We show that the problem admits a polynomial-time algorithm for two unrelated classes of graphs: proper interval graphs and trivially-perfect graphs. To complement our result, we show that the problem remains NP-complete on split graphs, and consequently also on chordal graphs. Thus we contribute to define the first border between graph classes on which the problem is polynomially solvable and on which it remains NP-complete
Parameterized Aspects of Strong Subgraph Closure
No full textMotivated by the role of triadic closures in social networks, and the importance of finding a maximum subgraph avoiding a fixed pattern, we introduce and initiate the parameterized study of the Strong F-closure problem, where F is a fixed graph. This is a generalization of Strong Triadic Closure, whereas it is a relaxation of F-free Edge Deletion. In Strong F-closure, we want to select a maximum number of edges of the input graph G, and mark them as strong edges, in the following way: whenever a subset of the strong edges forms a subgraph isomorphic to F, then the corresponding induced subgraph of G is not isomorphic to F. Hence the subgraph of G defined by the strong edges is not necessarily F-free, but whenever it contains a copy of F, there are additional edges in G to destroy that strong copy of F in G.
We study Strong F-closure from a parameterized perspective with various natural parameterizations. Our main focus is on the number k of strong edges as the parameter. We show that the problem is FPT with this parameterization for every fixed graph F, whereas it does not admit a polynomial kernel even when F =P_3. In fact, this latter case is equivalent to the Strong Triadic Closure problem, which motivates us to study this problem on input graphs belonging to well known graph classes. We show that Strong Triadic Closure does not admit a polynomial kernel even when the input graph is a split graph, whereas it admits a polynomial kernel when the input graph is planar, and even d-degenerate. Furthermore, on graphs of maximum degree at most 4, we show that Strong Triadic Closure is FPT with the above guarantee parameterization k - mu(G), where mu(G) is the maximum matching size of G. We conclude with some results on the parameterization of Strong F-closure by the number of edges of G that are not selected as strong
Author Correction: AGREE-S: AGREE II extension for surgical interventions: appraisal instrument (Surgical Endoscopy, (2022), 36, 8, (5547-5558), 10.1007/s00464-022-09354-z)
No full textThis article was updated to correct Alessandro Montedori’s name. Collaborative authorship: The GAP Consortium: Yasser Sami Abdel Dayem, Luca Bertolaccini, Pablo Alonso- Coello, Elie Akl, Manish Chand, John J. Como, Gert J. de Borst, Salomone Di Saverio, Sameh Emile, Bang Wool Eom, Ramon Gorter, George Hanna, Kaisa Immonen, Quirino Lai, Nicolaas Lumen, Joseph L. Mathew, Alessandro Montendori, Martin Moya, Gianluca Pellino, Alvaro Sanabria, Athanasios Saratzis, Neil Smart, Dimitrios Stefanidis, Giovanni Zaninotto
A Content-Based Publish/Subscribe Matching Algorithm for 2D Spatial Objects
No full textPart 5: Notification and StreamingInternational audienceAn important concern in the design of a publish/subscribe system is its expressiveness, which is the ability to represent various types of information in publications and to precisely select information of interest through subscriptions. We present an enhancement to existing content-based publish/subscribe systems with support for a 2D spatial data type and eight associated relational operators, including those to reveal overlap, containment, touching, and disjointedness between regions of irregular shape. We describe an algorithm for evaluating spatial relations that is founded on a new dynamic discretization method and region-intersection model. In order to make the data type practical for large-scale applications, we provide an indexing structure for accessing spatial constraints and develop a simplification method for eliminating redundant constraints. Finally, we present the results of experiments evaluating the effectiveness and scalability of our approach
Author Correction: AGREE-S: AGREE II extension for surgical interventions: appraisal instrument (Surgical Endoscopy, (2022), 36, 8, (5547-5558), 10.1007/s00464-022-09354-z)
No full textThis article was updated to correct Alessandro Montedori’s name. Collaborative authorship: The GAP Consortium: Yasser Sami Abdel Dayem, Luca Bertolaccini, Pablo Alonso- Coello, Elie Akl, Manish Chand, John J. Como, Gert J. de Borst, Salomone Di Saverio, Sameh Emile, Bang Wool Eom, Ramon Gorter, George Hanna, Kaisa Immonen, Quirino Lai, Nicolaas Lumen, Joseph L. Mathew, Alessandro Montendori, Martin Moya, Gianluca Pellino, Alvaro Sanabria, Athanasios Saratzis, Neil Smart, Dimitrios Stefanidis, Giovanni Zaninotto
A Content-Based Publish/Subscribe Matching Algorithm for 2D Spatial Objects
No full textPart 5: Notification and StreamingInternational audienceAn important concern in the design of a publish/subscribe system is its expressiveness, which is the ability to represent various types of information in publications and to precisely select information of interest through subscriptions. We present an enhancement to existing content-based publish/subscribe systems with support for a 2D spatial data type and eight associated relational operators, including those to reveal overlap, containment, touching, and disjointedness between regions of irregular shape. We describe an algorithm for evaluating spatial relations that is founded on a new dynamic discretization method and region-intersection model. In order to make the data type practical for large-scale applications, we provide an indexing structure for accessing spatial constraints and develop a simplification method for eliminating redundant constraints. Finally, we present the results of experiments evaluating the effectiveness and scalability of our approach
Inferring Tie Strength in Temporal Networks
No full textInferring tie strengths in social networks is an essential task in social
network analysis. Common approaches classify the ties as wea} and strong ties
based on the strong triadic closure (STC). The STC states that if for three
nodes, , , and , there are strong ties between and , as well as
and , there has to be a (weak or strong) tie between and . A
variant of the STC called STC+ allows adding a few new weak edges to obtain
improved solutions. So far, most works discuss the STC or STC+ in static
networks. However, modern large-scale social networks are usually highly
dynamic, providing user contacts and communications as streams of edge updates.
Temporal networks capture these dynamics. To apply the STC to temporal
networks, we first generalize the STC and introduce a weighted version such
that empirical a priori knowledge given in the form of edge weights is
respected by the STC. Similarly, we introduce a generalized weighted version of
the STC+. The weighted STC is hard to compute, and our main contribution is an
efficient 2-approximation (resp. 3-approximation) streaming algorithm for the
weighted STC (resp. STC+) in temporal networks. As a technical contribution, we
introduce a fully dynamic -approximation for the minimum weighted vertex
cover problem in hypergraphs with edges of size , which is a crucial
component of our streaming algorithms. An empirical evaluation shows that the
weighted STC leads to solutions that better capture the a priori knowledge
given by the edge weights than the non-weighted STC. Moreover, we show that our
streaming algorithm efficiently approximates the weighted STC in real-world
large-scale social networks
An Edge-Based Decomposition Framework for Temporal Networks
No full textInternational audienceA temporal network is a dynamic graph where every edge is assigned an integer time label that indicates at which discrete time step the edge is available. We consider the problem of hierarchically decomposing the network and introduce an edge-based decomposition framework that unifies the core and truss decompositions for temporal networks while allowing us to consider the network's temporal dimension. Based on our new framework, we introduce the -core and -truss decompositions, which are generalizations of the classic -core and -truss decompositions for multigraphs. Moreover, we show how -cores and -trusses can be efficiently further decomposed to obtain spatially and temporally connected components. We evaluate the characteristics of our new decompositions and the efficiency of our algorithms. Moreover, we demonstrate how our -decompositions can be applied to analyze malicious content in a Twitter network to obtain insights that state-of-the-art baselines cannot obtain
- …
