# Vinicius dos Santos

Age: 29

 Sep 20 awarded Supporter Aug 18 awarded Yearling Aug 18 awarded Yearling Aug 14 comment Has anybody studied the problem of finding maximal weighted rooted spanning DAGs?Are the weights positive? Aug 12 comment NP-Hardness reductionI'm not sure I really got your idea. You defined a new problem \$\Pi_2^k\$, which can be shown NP-complete (from a reduction from \$\Pi_2\$, right? But how does the reduction in (2), from \$\Pi_1\$ to \$\Pi_2^k\$, help? I think I would need a reduction in the opposite direction, right? Aug 10 awarded Student Aug 9 asked NP-Hardness reduction Jul 18 comment Pebbling ProblemI agree that if the number of pebbles on each vertex is polynomially bounded by the the size of the graph than it is trivially in NP. But I think this assumption is not necessary, although without it the proof gets harder. May 31 accepted What is the importance of a TCS researcher in a mostly applied CS department? May 29 comment What is the importance of a TCS researcher in a mostly applied CS department?I'm not in the US, and I was interested in the academic point of view, i.e. how a TCS researcher would increase the average quality (and maybe quantity) of research of such a department. The only reason I can think of is related to attracting students interested in theory. May 29 asked What is the importance of a TCS researcher in a mostly applied CS department? May 15 awarded Caucus May 11 awarded Yearling May 11 answered tree that approximates the distances and total weight in graphs May 6 comment Pebbling ProblemBut we can assume that the number of pebbles is in binary, right? In this case, the size of the input is logarithmic on the number of pebbles. I still think there is a short certificate for the problem but, as far as I understand, the list of moves is not one. May 5 comment Pebbling ProblemIs it that simple to show that the problem is in NP? Can't the number of moves be exponential on the input size? May 4 awarded Yearling May 1 comment Is there a problem that is easy for cubic graph but hard for graphs with maximum degree 3?I think you should ask this as a new question, and link this older question if you think it's related enough. Apr 17 comment Eccentricity of vertices in a graphSince k >= |V(G)|/2, if you take non-adjacent vertices u and v, you have |N(u)|+|N(v)|>= |V(G)|. Note that the total number of vertices is as big as the vertex set, hence, since they are not adjacent, there must be a repetition between the vertices of N(u) and N(v). Apr 10 answered Eccentricity of vertices in a graph