HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

How to determine the largest number of disconnected arcs in a graph?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
numberthegraphlargestdeterminehowarcsdisconnected

Problem

Given a directed graph $G=(V,E)$, I'm wondering if there's a way to determine the largest size of a set of edges that are disconnected pairwise. There is a similar problem for vertices (Maximum Independent Set). However, I'm unable to think of the corresponding problem for edges.

When I say "two disconnected edges" I mean the following:

  • $(u,v)$ to $(u,w)$ are "disconnected" since the tail of one does not equal the tip of the other.



  • $(u,v)$ to $(w,v)$ are "disconnected" since the tail of one does not equal the tip of the other.



  • $(u,v)$ to $(v,w)$ are "connected" since the tail of one does equal the tip of the other.



What is the name of this type of problem?

Solution

The problem can be reduced to the maximum independent set problem. Let $G = (V,E)$ be the input instance of the problem. Then, create a new graph $G'$ such that each vertex in $G'$ corresponds to an edge in $G$. Two vertices in $G'$ have an edge between them if and only if the corresponding edges are connected in $G$. The following claim follows easily.

Claim: There exists a set of $k$ pairwise-disconnected edges in $G$ if and only if $G'$ has an independent set of size $k$.

Context

StackExchange Computer Science Q#160847, answer score: 2

Revisions (0)

No revisions yet.