Michael Lampis's user avatar
Michael Lampis's user avatar
Michael Lampis's user avatar
Michael Lampis
  • Member for 12 years, 11 months
  • Last seen this week
15 votes

Integer linear programming in logarithmic number of variables

15 votes
Accepted

Does Hadwiger conjecture imply that NP = coNP?

12 votes

Inappoximability status of Max One in Three SAT for satisfiable instances

10 votes

Finding number of cycles of length $k$ in a graph

10 votes

Problems that are easy on unweighted graphs, but hard for weighted graphs

10 votes
Accepted

Generalized Geography on graphs of bounded treewidth

10 votes

What is known about this TSP variant?

10 votes
Accepted

Is there a gadget that reduces generalized geography to undirected graphs?

9 votes

If SAT is in PCP, for some constant q, then P = NP

9 votes

Nonstandard dual parametrization of graph problems

8 votes

Is there a SETH (Strong Exponential Time Hypothesis) for CSP (Constraint Satisfaction Problem)?

7 votes

Hard problems for bounded vertex cover

7 votes

NP-hard problems on trees

7 votes

In-approximability results in severely restricted graph classes

7 votes
Accepted

Balanced Max-2-SAT NP-Hardness

6 votes
Accepted

Inapproximability of $(\alpha, \beta)$ bi-criteria approximation

6 votes

Clique-width expressions with logarithmic depth

6 votes
Accepted

Is there a W[1]-hard problem that can be solved in $2^{o(n)}$ time?

6 votes

Is Hamiltonian cycle fixed parameter tractable with parameter clique cover?

6 votes

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

5 votes
Accepted

Standard Name for a vertex removal like operation

4 votes
Accepted

ETH-Hardness of $Gap\text-MAX\text-3SAT_{c}$

4 votes

Hardness of FPT problems

3 votes

Instance of FPT-reductions that is not a polynomial-time reduction

3 votes

Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs

3 votes
Accepted

Consequences of a distillation algorithm for PSPACE

2 votes

Is there simple reduction Dominating Set to Vertex Cover?

2 votes

Path coloring in general graphs

2 votes

reference for a special modular decomposition

2 votes

Problems with Unknown Single Exponential Time Agorithms