4 votes

Defining regular language classes with disjoint union

Interesting, I was recently writing a blog post on a related topic. Namely, you have probably seen the term rational languages used for regular languages. This is because the generating function (g.f.)...
  • 281
3 votes

Defining regular language classes with disjoint union

This question has indeed been studied: namely, from the perspective of representing regular languages as unions of so-called regular components that is, loop expressions of the form $uv^+w$, and a ...
3 votes

FPT algorithm for Partial k-tree Isomorphism

In the meantime, it was shown that Graph Isomorphism is FPT with respect to the treewidth of the graphs. Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh: Fixed-Parameter ...
1 vote

NP-hardness: (planar) directed feedback vertex set problem with bounded degree

Thanks to Prof. @Yixin Cao's construction of the reduction, I think I have found a way to show that Planar-DFVS remains $\textsf{NP}$-hard when $(\Delta_{in}, \Delta_{out}) = (2, 2)$. We use the ...
  • 397
1 vote

NP-hardness: (planar) directed feedback vertex set problem with bounded degree

Warning: this does not completely solve your question because the gadget is not planar. But since I could not find a proof of this, I think it might be worth posting. Speckenmeyer proved that the ...
  • 2,560
1 vote

Is the feedback vertex set problem on planar bounded degree graphs hard?

Here are the two gadgets Speckenmeyer used in his Ph.D. thesis. We can start from planar graphs with maximum degree six, by a reduction from the vertex cover problem on cubic planar graphs. (Actually, ...
  • 2,560

Only top scored, non community-wiki answers of a minimum length are eligible