Skip to main content
Theoretical Computer Science

Nice Answer

 Nice Answer
Answer score of 10 or more. This badge can be awarded multiple times.

earned this badge 195 times.
Graph that maximizes minimum hitting time?
Awarded Jun 1 at 3:48
Polynomial time solvable in series parallel graph but NP-hard in graph with bounded treewidth
Awarded Oct 9, 2023 at 16:25
Time complexity of d-dimensional convex hull
Awarded Oct 8, 2023 at 14:19
Problems with big open complexity gaps
Awarded Dec 5, 2021 at 0:19
Finding vertex separator such that the induced subgraph has minimal number of edges
Awarded May 14, 2021 at 4:42
NP-Complete problems that admit an efficient algorithm under the promise of a unique solution
Awarded Apr 13, 2021 at 16:50
Problems with Unknown Single Exponential Time Agorithms
Awarded Oct 1, 2020 at 13:47
How to generate graphs with known optimal vertex cover
Awarded Sep 19, 2020 at 3:43
Parametrized Algorithm for Finding Bicliques
Awarded Aug 10, 2020 at 19:27
Can we compute $n$ from the bits of $3^n$ in $O(n)$ time?
Awarded Aug 3, 2020 at 2:31
In the neutral zone between polynomial and sub-exponential
Awarded Jun 21, 2020 at 11:50
Number of connected components of a random nearest neighbor graph?
Awarded Jun 14, 2020 at 4:50
Is feedback vertex set problem solvable in polynomial time for 3-degree bounded graphs?
Awarded May 14, 2020 at 11:21
Gentle introduction to the algorithmic aspects of tree-depth
Awarded Jan 30, 2020 at 6:30
Examples where the uniqueness of the solution makes it easier to find
Awarded Oct 13, 2019 at 8:45
Bipartite Graphs - Maximum subset of one partition with at most n neighbours - NP-hard?
Awarded Sep 16, 2019 at 13:45
Definition of Planar 3-SAT
Awarded Jun 1, 2019 at 12:10
What separates easy global problems from hard global problems on graphs of bounded treewidth?
Awarded May 9, 2019 at 22:10
Number of simple paths between two vertices in a DAG
Awarded Apr 23, 2019 at 23:45
Finding max of two elements in linear time with restriction
Awarded Apr 1, 2019 at 20:30
Finding odd holes in circulant Paley graphs
Awarded Apr 1, 2019 at 20:30
Generalized Priority Queues
Awarded Apr 1, 2019 at 20:30
Two papers give contradictory bounds on linear probing. How do I resolve the disparity?
Awarded Mar 30, 2019 at 11:30
Solving a "tree-equation"?
Awarded Mar 30, 2019 at 11:25
Subgraph isomorphism with a tree
Awarded Feb 15, 2019 at 8:00
What is the application of combinatorial game theory
Awarded Oct 24, 2018 at 6:45
enumerating all connected induced subgraphs
Awarded Jun 30, 2018 at 22:59
Anti bin packing
Awarded May 6, 2018 at 23:16
Reasons for which a graph may be not $k$ colorable?
Awarded Jan 30, 2018 at 3:47
Array slice reversing data-structure
Awarded Oct 26, 2017 at 13:35
Pathwidth of planarized drawing of $K_{3,n}$
Awarded May 20, 2017 at 17:13
Is intersection of $k \ge 3$ graphic matroids in P?
Awarded May 19, 2017 at 9:14
Maximum Polyhedron Volume in Given $n$ Points
Awarded May 11, 2017 at 17:31
The maximum number of induced cycles in a simple directed graph
Awarded Feb 12, 2017 at 18:08
Problems in quasi-polynomial time that could conceivably be in P (without causing collapses or violating widely held beliefs)
Awarded Feb 8, 2017 at 19:10
Lexicographically minimal topological sort of a labeled DAG
Awarded Jan 17, 2017 at 11:14
Pair of vertex disjoint cycles in a directed graph
Awarded Nov 28, 2016 at 7:23
Are there any heuristic-free NP complete problems?
Awarded Oct 26, 2016 at 9:31
Treewidth of deep Sierpiński Sieve Graph
Awarded Sep 8, 2016 at 12:29
Are there poly time algorithms to determine if a graph is almost bipartite?
Awarded Aug 30, 2016 at 14:00
Sorting "k-tonic" sequences
Awarded Aug 9, 2016 at 21:20
NP-hardness on Cayley graphs
Awarded Jun 21, 2016 at 17:24
Is it possible to find a non-cut vertex in O(|V|) time?
Awarded Jun 7, 2016 at 5:30
How do journals serve the TCS community?
Awarded May 14, 2016 at 18:07
Tree-decomposition with clique interfaces
Awarded Apr 15, 2016 at 19:18
Number of vertices present in all maximum matchings
Awarded Mar 19, 2016 at 22:38
Are regular languages closed under addition?
Awarded Mar 19, 2016 at 20:16
Classes of graphs with superconstant treewidth
Awarded Feb 15, 2016 at 15:51
Finding k nearest neighbors for all points
Awarded Feb 5, 2016 at 8:09
Book for self study of algorithms in group theory
Awarded Dec 12, 2015 at 16:53
Improved lower bounds or upper bounds on union-find structures since Tarjan?
Awarded Dec 6, 2015 at 18:28
Are there any known NP problems which are conjectured to be exponentially hard on average?
Awarded Dec 4, 2015 at 10:57
Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?
Awarded Nov 11, 2015 at 8:27
What's the simplest noncontroversial 2-state universal Turing machine?
Awarded Sep 23, 2015 at 5:21
Generalizing the "median trick" to higher dimensions?
Awarded Sep 16, 2015 at 15:10
Math talk: Theorem about git revision control system?
Awarded Aug 28, 2015 at 8:52
Permutations with forbidden subsequences
Awarded Aug 20, 2015 at 7:56
Finding witness in minkowski sum of integers
Awarded Jul 24, 2015 at 2:38
What greedy algorithm satisfies greedy choice property but does not have optimal substructure?
Awarded Jul 16, 2015 at 19:51
Structure of graphs that exclude a perfect matching on four vertices as an induced graph
Awarded Jun 6, 2015 at 17:27
1
2 3 4

Others with this badge