Skip to main content
Laakeri's user avatar
Laakeri's user avatar
Laakeri's user avatar
Laakeri
  • Member for 5 years, 6 months
  • Last seen this week
13 votes
Accepted

Best parameterized algorithm for maximum clique

9 votes
Accepted

Implication of solving 3SUM problem of a certain size on the Exponential Time Hypothesis

8 votes
Accepted

Is the isomorphism problem between posets represented by DAGs GI-complete?

7 votes

Finding simple fixed length paths in directed graphs

7 votes

When does a bipartite graph have bounded treewidth?

6 votes

conversion to DAG

6 votes
Accepted

Complexity of induced Steiner Tree problem

4 votes
Accepted

Independent set queries with preprocessing

4 votes

On $\text{ETH}$ with $m$ as parameter: consequences of algorithm running in time $2^{\delta m}$ where $\delta \to 0$ as $k \to \infty$

4 votes
Accepted

Find the shortest s-t trail(edge disjoint path) in a graph with negative weight edges

4 votes
Accepted

Does replacing each vertex of $G$ by $H$ increase treewidth of $G$ by at most $\Delta(G)$?

4 votes
Accepted

Parameterized complexity of tree/branch decomposition

4 votes
Accepted

Extracting coefficients of polynomials given by straight line programs

3 votes
Accepted

Is a grid graph a vertex-minor of a complete graph?

3 votes
Accepted

Reduction graph to planar bounded treewidth and bounded diameter graph

3 votes

Treewidth for hypergraphs that specify connectedness requirements

3 votes
Accepted

Is Maximum Independent Set polynomial-time solvable in $(p,1)$-colorable graphs for general $p$?

3 votes
Accepted

What is the treewidth of the 3D-grid (mesh or lattice) with sidelength n?

2 votes

Is counting the union of power sets NP-complete?

2 votes
Accepted

Minimum vertex cover and odd cycles

2 votes

Complexity of MAX-ONEs Monotone 2-SAT with $n^{3/2}$ or $C n^2$ clauses?

2 votes
Accepted

Obtaining Sets of Ancestors Quickly in a Directed Acyclic Graphs

2 votes
Accepted

Complexity of the Complete (3,2) SAT problem?

1 vote
Accepted

Is there FPT or XP algorithms known for Shortest Steiner cycle and $(a,b)$-Steiner path problem

1 vote

On structure of graphs with average degree equal to maximum average degree

1 vote
Accepted

Is homogeneity required in Hyafil's arithmetic circuit decomposition theorem when applied to monotone circuits?

1 vote
Accepted

Neighborly properties in a bipartite graph

1 vote
Accepted

What is known about the complexity of Network Diversion?