1,720,997 research outputs found
Double Exponential Lower Bound for Telephone Broadcast
Full text linkConsider the Telephone Broadcast problem in which an input is a connected
graph on vertices, a source vertex , and a positive integer
. The objective is to decide whether there is a broadcast protocol from
that ensures that all the vertices of get the message in at most
rounds. We consider the broadcast protocol where, in a round, any node aware of
the message can forward it to at most one of its neighbors. As the number of
nodes aware of the message can at most double at each round, for a non-trivial
instance we have . Hence, the brute force algorithm that checks all
the permutations of the vertices runs in time 2^{2^{\calO(t)}} \cdot
n^{\calO(1)}. As our first result, we prove this simple algorithm is the best
possible in the following sense.
Telephone Broadcast does not admit an algorithm running in time 2^{2^{o(t)}}
\cdot n^{\calO(1)}, unless the \ETH\ fails.
To the best of our knowledge, this is only the fourth example of \NP-Complete
problem that admits a double exponential lower bound when parameterized by the
solution size. It also resolves the question by Fomin, Fraigniaud, and Golovach
[WG 2023]. In the same article, the authors asked whether the problem is \FPT\
when parameterized by the feedback vertex set number of the graph. We answer
this question in the negative.
Telephone Broadcast, when restricted to graphs of the feedback vertex number
one, and hence treewidth of two, is \NP-\complete.
We find this a relatively rare example of problems that admit a
polynomial-time algorithm on trees but is \NP-\complete\ on graphs of treewidth
two
Romeo and Juliet meeting in forest like regions
No full textThe game of rendezvous with adversaries is a game on a graph played by two players: Facilitator and Divider. Facilitator has two agents and Divider has a team of k?1 agents. While the initial positions of Facilitator's agents are fixed, Divider gets to select the initial positions of his agents. Then, they take turns to move their agents to adjacent vertices (or stay put) with Facilitator's goal to bring both her agents at same vertex and Divider's goal to prevent it. The computational question of interest is to determine if Facilitator has a winning strategy against Divider with k agents. Fomin, Golovach, and Thilikos [WG, 2021] introduced this game and proved that it is PSPACE-hard and co-W[2]-hard parameterized by the number of agents.
This hardness naturally motivates the structural parameterization of the problem. The authors proved that it admits an FPT algorithm when parameterized by the modular width and the number of allowed rounds. However, they left open the complexity of the problem from the perspective of other structural parameters. In particular, they explicitly asked whether the problem admits an FPT or XP-algorithm with respect to the treewidth of the input graph. We answer this question in the negative and show that Rendezvous is co-NP-hard even for graphs of constant treewidth. Further, we show that the problem is co-W[1]-hard when parameterized by the feedback vertex set number and the number of agents, and is unlikely to admit a polynomial kernel when parameterized by the vertex cover number and the number of agents. Complementing these hardness results, we show that the Rendezvous is FPT when parameterized by both the vertex cover number and the solution size. Finally, for graphs of treewidth at most two and girds, we show that the problem can be solved in polynomial time
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Revisiting token sliding on chordal graphs
No full textIn this article, we revisit the complexity of the reconfiguration of independent sets under the token sliding rule on chordal graphs. In the \textsc{Token Sliding-Connectivity} problem, the input is a graph G and an integer k, and the objective is to determine whether the reconfiguration graph TSk(G) of G is connected. The vertices of TSk(G) are k-independent sets of G, and two vertices are adjacent if and only if one can transform one of the two corresponding independent sets into the other by sliding a vertex (also called a \emph{token}) along an edge. Bonamy and Bousquet [WG'17] proved that the \textsc{Token Sliding-Connectivity} problem is polynomial-time solvable on interval graphs but \NP-hard on split graphs. In light of these two results, the authors asked: can we decide the connectivity of TSk(G) in polynomial time for chordal graphs with \emph{maximum clique-tree degree} d? We answer this question in the negative and prove that the problem is \para-\NP-hard when parameterized by d. More precisely, the problem is \NP-hard even when d=4. We then study the parameterized complexity of the problem for a larger parameter called \emph{leafage} and prove that the problem is \co-\W[1]-hard. We prove similar results for a closely related problem called \textsc{Token Sliding-Reachability}. In this problem, the input is a graph G with two of its k-independent sets I and J, and the objective is to determine whether there is a sequence of valid token sliding moves that transform I into J
Dispelling the Myths Behind First-author Citation Counts
Full text linkWe conducted a full-scale evaluative citation analysis study of scholars in the XML research field to explore just how different from each other author rankings resulting from different citation counting methods actually are, and to demonstrate the capability of emerging data and tools on the Web in supporting more realistic citation counting methods. Our results contest some common arguments for the continued
use of first-author citation counts in the evaluation of scholars, such as high correlations between author rankings by first-author citation counts and other citation
counting methods, and high costs of using more realistic citation counting methods that are not well-supported by the ISI databases. It is argued that increasingly available digital full text research papers make it possible for citation analysis studies to go beyond what the ISI databases have directly supported and to employ more
sophisticated methods
On the Parameterized Complexity of Contraction to Generalization of Trees
No full textFor a family of graphs F, the F-Contraction problem takes as an input a graph G and an integer k, and the goal is to decide if there exists S⊆E(G) of size at most k such that G/S belongs to F. Here, G/S is the graph obtained from G by contracting all the edges in S. Heggernes et al.~[Algorithmica (2014)] were the first to study edge contraction problems in the realm of Parameterized Complexity. They studied F-Contraction when F is a simple family of graphs such as trees and paths. In this paper, we study the F-Contraction problem, where F generalizes the family of trees. In particular, we define this generalization in a "parameterized way". Let Tℓ be the family of graphs such that each graph in Tℓ can be made into a tree by deleting at most ℓ edges. Thus, the problem we study is Tℓ-Contraction. We design an FPT algorithm for Tℓ-Contraction running in time O((2(√ℓ))O(k+ℓ)⋅nO(1)). Furthermore, we show that the problem does not admit a polynomial kernel when parameterized by k. Inspired by the negative result for the kernelization, we design a lossy kernel for Tℓ-Contraction of size O([k(k+2ℓ)](⌈α/α−1⌉+1))
- …
