Computer Science

« first day (2206 days earlier) ← previous day next day → last day (2219 days later) »

Paradox

12:05 AM

Hi is anybody here familiar with polynomial reductions?

vzn

12:47 AM

@Paradox yes

Paradox

@vzn I am trying to do a polynomial reduction from vertex cover where:

VertexCover = {<G,k> | G is an undirected graph that has a k-node vertex cover} and a vertex cover C is a set of vertices where for all vertices (u,v), u is an element of C or v is an element of C

Total Union = {<U,S,k> | OVer U and S There exists a total union of size k or less}.
A total union takes sets U and S where S is a set of subsets of U and finds the smallest subset of S, denoted by T, such that the union of all the elements of T equals U

For example, let U = {a,b,c,d,e,f,g} and S={{a,b,c},{b,d},{f,g},{e,g},{c,d,e},{e,f},{a}} then T = {{a,b,c},{c,d,e},{f,g}} since {a,b,c} Union {c,d,e} Union {f,g} = U

I have been stuck on this problem for several days now. I first thought of using U = V and S = edges but then that would be choosing vertices to cover the edges of the graph. But if I used U = edges and V = vertices then it still wouldn't work because total union wouldn't be creating subsets through unioning..

vzn

1:15 AM

@Paradox did you mean for all edges (u,v)?

Paradox

@vzn yes, my mistake

vzn

@Paradox dont have the idea yet but hint: try iterating vertex cover over many specially-constructed graphs to get a total union.

Paradox

What do you mean by iterating vertex cover, since we don't have a decider for vertex cover?

vzn

@Paradox is the problem reduce from vertex cover to total union?

Paradox

@vzn Yes, Vertex Cover <=p Total Union

So I can assume that I have a machine which solves Total Union

vzn

1:26 AM

@Paradox ok right then the other way around. iterate total union through multiple specially-constructed graphs (maybe not a single one). anyway have to think more myself to get it.

Paradox

@vzn Thank you for taking a look at it. I'll keep working at it too.

vzn

sure. btw what level class is this for?

Paradox

University comp complexity

2 hours later…

Bounty!

3:15 AM

Q: State of the Art in linear-time DFA minimization

What is the most complicated kind of deterministic finite-state automaton that can be minimized in $O(n)$ time? Here’s what I’ve been able to find so far: The acyclic case has been solved. So any acyclic DFA can be minimized in $O(n)$ time by the Revuz algorithm [2]. As for cyclic automata, an...