Bidirectional graph theory reduction

I'm working on problem where each node can have a maximum of:
- 2 bidirectional edges
- 1 directed edge pointing away
- Infinite directed edges pointing towards it
If a node is being pointed at(by a bidirectional or directed edge) by 1+ remaining nodes, then it can be removed. [see pic]
I'm looking for an algorithm, formula or an approach to reduce a graph of any size in the most optimal way, meaning there is the fewest possible nodes remaining.

Other urls found in this thread:

cs.stackexchange.com/a/70701
twitter.com/NSFWRedditGif

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.

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

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

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

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

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

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

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

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.

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

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

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)

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?

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

it's equivalent because any greedy algorithm has no chance of working

What background of math do you need for competitive programming?

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!!

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

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

Excellent, thanks.