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 ...
- 5,534
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,700
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