daniello's user avatar
daniello's user avatar
daniello's user avatar
daniello
  • Member for 9 years, 5 months
  • Last seen more than a week ago
18 votes

Are there interesting graph classes where the treewidth is hard (easy) to compute?

17 votes
Accepted

Does treewidth $k$ imply the existence of a $K_{1,k}$ minor?

16 votes
Accepted

For what c is division by c in AC0?

10 votes
Accepted

Can a hereditary graph class contain almost all, but not all, n-vertex graphs?

10 votes

k-Vertex Cover problem is in parameterized Log space

9 votes
Accepted

W[1]-hard problems with FPT time approximation algorithms

8 votes
Accepted

Isomorphism of ‘ordered’ DAGs / acyclic semiautomata

8 votes
Accepted

Reductions between languages of different densities?

8 votes
Accepted

Reference request: complexity of $k$-partite $k$-SAT

8 votes
Accepted

Hadwiger number under matching contraction

7 votes

Can we fast generate perfectly uniformly mod 3 or solve NP problem?

7 votes

What's the correlation between treewidth and instance hardness for random 3-SAT?

6 votes
Accepted

Using master theorem when there is a constant in the recursive term

6 votes
Accepted

What is the complexity of decision tree complexity?

6 votes
Accepted

The relationship between degree of vertex and size of dominating set

6 votes
Accepted

Number of local maxima in MAX-2-SAT

6 votes
Accepted

Something-Treewidth Property

6 votes

Pulling a graph across a partition

6 votes

Hard problems for bounded vertex cover

5 votes
Accepted

Upperbound for max degree of k-tree completion

5 votes

Is the reduction from a parametrized proplem to the problem kernel just a kind of Karp reduction (polynomial-time reduction)?

5 votes

Extending cographs with product operation

5 votes
Accepted

Question about algorithm for enumerating minimal AB-separators

5 votes
Accepted

Minimal polynomial reduction of dominating set to max clique

5 votes

Exact Algorithms for r-Dominating Set on Bounded Treewidth Graphs

5 votes

What is the minimum over all distributions of unit vectors of the variance of the dot product of the vectors?

5 votes
Accepted

Natural maximization problems in FPT

5 votes

Minimum Tree-width of circuit for MAJORITY

5 votes

Finding optimal subset for quadratic function

4 votes
Accepted

Hardness of Subgraph isomorphism problem for sparse pattern graph