Skip to main content
Florent Foucaud's user avatar
Florent Foucaud's user avatar
Florent Foucaud's user avatar
Florent Foucaud
  • Member for 13 years, 8 months
  • Last seen more than a month ago
24 votes
1 answer
1k views

For which k is PLANAR NAE k-SAT in P?

24 votes
1 answer
879 views

What is the complexity of this covering problem?

19 votes
1 answer
3k views

Is the dominating set problem restricted to planar bipartite graphs of maximum degree 3 NP-complete?

13 votes
1 answer
814 views

Parameterized complexity of inclusion of regular languages

13 votes
3 answers
1k views

Relation between tree-width and clique number

13 votes
1 answer
280 views

The complexity of the dominating set problem in specific subclasses of chordal graphs

10 votes
2 answers
365 views

Complexity of digraph homomorphism to an oriented cycle

8 votes
2 answers
264 views

Nonstandard dual parametrization of graph problems

8 votes
0 answers
172 views

Can one find good distance-2-separators in planar graphs?

8 votes
0 answers
178 views

Is the dominating set problem constant-factor-approximable in undirected path graphs?

7 votes
2 answers
291 views

The complexity of recognizing optimal set systems for the V-C dimension

7 votes
1 answer
458 views

Petrank's proof for the APX-hardness of MAX k-VERTEX COVER on subcubic graphs

5 votes
1 answer
1k views

Is there an approximation algorithm for MAX k DOUBLE SET COVER?

0 votes
0 answers
79 views

"Fast" approximation algorithm for geometric hitting set of same-height rectangles