Bidirectional graph theory reduction

>>9021911
please clarify when you can remove a node and which nodes can be removed in the example

My current approach is to do something like this:
for each node:
....if node.alive && node.has_live_parents && !node.is_dependant_on:
........node.kill()

- has_live_parents is true if a node has 1+ alive nodes pointing towards it
- is_dependant_on is true if 1+ of the nodes children only have this node as their only alive parent

This problem with this is that if node E is processed before the rest then it's removed then A,B,C or A,B,D are required making the size of the graph 3.

>>9021916
A node can be remove if 1 or more nodes that are still alive are pointing to it.
In the example, the 3 red nodes(B,C,D) are removed

>>9021921
you can also remove B C D E
the solution is doing a toposort of the SCC DAG, and you can probably remove all nodes but one at every toposort root SCC. haven't proved it, but you should try that

>>9021916
In the example given the optimal solution removes B,C,D leaving one 2 nodes A,E.
If we choose to remove E 1st then it would be impossible to have less than 3 nodes remaining

>>9021924
>>9021921
actually, clarify more. are nodes removed one at a time (which I'm assuming) or do you only have one single group removal?

>>9021924
E is required as there are no LIVING nodes pointing to it

>>9021926
Whatever you want. Imaging there's a large amount of nodes and you're writing an algorithm to remove them

>>9021927
then you're wrong. first remove E, then D, then C, then B.

>>9021929
Sorry, to clarify more, you can remove E then D, then when you try to remove C you can't as E is depending on it.

>>9021929
The goal is for at the end, every node must be either alive OR being pointed at by 1+ other alive nodes.

>>9021935
>>9021937
then you can only make ONE batch removal. the problem's completely different than what I said with SCCs now. You're looking for the min vertex cover of the graph, it's a well known problem

File: graph_example_reason.jpg (60KB, 798x633px) Image search: [Google]

60KB, 798x633px

>>9021944
Thanks that sounds promising! I don't have a background in graph theory at all and I came across the problem in a project I'm working on. Any info pointing me in the right direction is great
btw here's more details(see pic)

>>9021944
Why only ONE? I can imaging an algorithm where on a 1st pass you remove all outer nodes with no children, then more passes where you remove more inner nodes

turn it into a adjacency matrix and mark for removal every node that has more than one edge pointing to it?

>>9021965
competitive programmers (people doing ICPC style competitions) know how to solve this kind of problem. the classical min vertex cover happens in an undirected graph, but what you have is a directed graph with some special properties. it's a problem in a topic known as "network flows", where problems are usually NP in the general case but where efficient algorithms are known for many discrete cases. I don't know if this particular one is easy or not

you could make a post in codeforces asking about it (ask in a smarter way, something like "looking for the directed min vertex cover where my graph has these special properties"), I'll ask my flows guy

>>9021973
it's equivalent because >>9021937
>>9021979
any greedy algorithm has no chance of working

>>9021989
What background of math do you need for competitive programming?

>>9021979
>>9021989
Cheers! Btw the context behind this problem is that some sites allow multiple passwords.
e.g. if your password was 'PASS'
Entering 'pass' would work as you might have had caps lock one
Entering 'pASS' would work as some old phones toggle the case of the 1st letter
Entering 'PASS1' would work as you might have pressed a key beside enter by mistake.
(I know these rules are silly, I didn't make them up, but it's what some sites and applications do)
My goal is to take a dump of the N most common passwords and see how few I could use to cover all of them. E.g.
there would be no point in guessing 'PASS' and 'pass' because if 'PASS' didn't work then we know it's not 'pass' or 'pASS' or 'PAS'

If anyone has a better way to represent the problem either let me know!!

>>9022009
at first, nothing. it's all about the classical theory of algorithms, and many algorithms are elementary. you can learn a whole bunch about graph theory and dynamic programming and get quite far with very few prerequisites.

let's say the math you need later on is very specific. eventually you need a bit of number theory, things about modular arithmetic and prime number manipulation. you need a bit of linear algebra, for solving linear equations, etc etc.

it's a very fun sport, a great book to get started or see a big chunk of it right away is Competitive Programming 3 by Halim (it's online).

okay so it's actually not vertex cover it's dominating set

it's np complete in the classical formulation, and there's research done in directed graphs. your particular graph may be easier

>>9022226
>dominating set
Cheers, I found a nice answer here:
https://cs.stackexchange.com/a/70701

>>9022017
Excellent, thanks.