#StackBounty: #ds.algorithms #graph-theory #graph-algorithms #directed-acyclic-graph Finding nodes with enough unique ancestors

Bounty: 50

Given a DAG $G = (V, E)$, let $T subseteq V$ be a set of nodes of $V$ that is computed via the following process. Assuming the nodes of $G$ are sorted in topological order, $v_1, dots, v_n$. We process the nodes in this topological order. Suppose we are processing vertex $v_i$ in the order. Let $r(v_i)$ be the set of ancestors of $v_i$. We add $v_i$ and all ancestors of $v_i$ into $T$ if and only if the number of ancestors of $v_i$ (including $v_i$ itself) that are not in $T$ is at least $frac{|r(v_i)| + 1}{f}$ where $f$ is some constant $f > 1$ provided as part of the input. If a vertex is added to $T$, then all its ancestors are also added into $T$. Any algorithm that computes $T$ must satisfy the following invariant: any vertex $v_i$ added into $T$ must have at least $frac{|r(v_i)| + 1}{f}$ of its ancestors (including itself) not in $T$ when it was added, and any vertex $v_i$ not added into $T$ must have $< frac{|r(v_i)| + 1}{f}$ of its ancestors (including itself) not in $T$.

Problem: Provide an algorithm that runs in $tilde{O}(m + n)$ time (meaning ignoring polylogarithmic factors) that provides a valid set $T$ given an input graph $G = (V, E)$ and the processing order of the vertices is the toposort order. Approximation (meaning constant error on the $frac{r(v_i)+1}{f}$ condition) and Las Vegas algorithms are welcome also. You may preprocess the graph but the preprocessing time must also be $tilde{O}(m + n)$.

Trivial Solution in More Time We can do this trivially in $O(nm)$ time. For each $v_i$, we find via BFS its set of ancestors and check whether each one is in $T$. From this we can compute the exact fraction that is not in $T$ and either put $v_i$ and $r(v_i)$ in $T$ or not.

Example Problem: Suppose you have the following trivial DAG (below) and $f= 2$.

a -> b -> c

Then, $T = {a, b}$. $a$ is processed first and $T = emptyset$ at first so $a$ is added into $T$. Then, $b$ is processed after $a$ and is added to $T$ since $1/2$ of the vertices in ${a, b}$ are not in $T$. Finally, $c$ is processed and not added to $T$ since it has at most $1/3$ of the vertices in ${a, b, c}$ are not in $T$. Note that in this example, a trivial $O(n)$ algorithm for any line is to keep a counter $c$ of the index of the last element added to $T$ (since adding the element at $c$ also means adding all its ancestors) and add the $i$-th element of the line to $T$ if $frac{i-c}{i} geq frac{1}{f}$. However, this problem is much less trivial for general graphs.

Has anyone seen a problem similar to this in the literature or algorithms which solve similar problems?


Get this bounty!!!

#StackBounty: #cc.complexity-theory #ds.algorithms #graph-theory #linear-algebra #max-flow-min-cut Complexity of Encoding a Matroid Flo…

Bounty: 50

Context:
Take a directed graph $G$ with a specified subset of source vertices $S$ and target vertices $T$.
We say a subset $Isubseteq T$ of size $r$ is independent if there exist $r$ distinct vertices in $S$ which can be connected to distinct vertices of $I$ via a collection of $r$ vertex-disjoint paths in $G$. In other words, there is a flow of size $r$ from $S$ to $I$.

It turns out that a graph together with independent subsets of vertices defined in this way forms a structure known as a gammoid, which is itself a special case of a structure known as a matroid.
Many algorithms that work with matroids take as input a linear representation of the matroid. In the context of this problem, this representation is a matrix $M$ whose column vectors $vec{v}u$ are indexed by vertices $u$ in $G$, with the property that a subset $I$ of vertices is independent if and only if the corresponding list of column vectors ${vec{v}_u}{uin I}$ is linearly independent.

Several sources (see here and here for example) observe that is well-known that given $G$, $S$, and $T$, one can build a matrix representation of the associated gammoid in randomized polynomial time. However, I have not been able to find any reference to the precise running time of this algorithm.
This motivates the following question.

Question: Given a graph $G$ with source set $S$ and target set $T$, how quickly can we build a matrix representation of the associated gammoid? Randomness is allowed.

I’m mainly interested in the dependence on the the number of vertices $n$ in the graph, but it would be good to know the dependence on the number of source vertices $|S| = k$ as well.


Get this bounty!!!

#StackBounty: #cc.complexity-theory #graph-theory #sat #counting-complexity #planar-graphs Disproving $oplus$ETH by reducing $oplus k…

Bounty: 100

In this question and its answer, they discuss about reducing CNF-SAT with $n$ variables and $m$ clauses to a (problem on) planar graph $G=(V,E)$ with $|V|$ as small as possible. It is said that the best known reduction has $|V| = m^2$, and that if a better reduction with $|V| in o(m^2)$ is found, that would refute ETH.


There is a reduction from $oplus k$-SAT with $n$ variables and $m$ clauses to $oplus$VERTEX COVER where the output graph $G=(V,E)$ is planar and has $|V| = 51(k+1)nm$. Such reduction clearly meets the $|V| in o(m^2)$ requirement when $k$ is a constant and $m$ is superlinear in $n$.


Question
Can the same line of reasoning made within the linked question be applied here in order to refute $oplus$ETH, or am I missing some important detail?


Get this bounty!!!

#StackBounty: #cc.complexity-theory #graph-theory #sat #counting-complexity #planar-graphs Disproving $oplus$ETH by reducing $oplus k…

Bounty: 100

In this question and its answer, they discuss about reducing CNF-SAT with $n$ variables and $m$ clauses to a (problem on) planar graph $G=(V,E)$ with $|V|$ as small as possible. It is said that the best known reduction has $|V| = m^2$, and that if a better reduction with $|V| in o(m^2)$ is found, that would refute ETH.


There is a reduction from $oplus k$-SAT with $n$ variables and $m$ clauses to $oplus$VERTEX COVER where the output graph $G=(V,E)$ is planar and has $|V| = 51(k+1)nm$. Such reduction clearly meets the $|V| in o(m^2)$ requirement when $k$ is a constant and $m$ is superlinear in $n$.


Question
Can the same line of reasoning made within the linked question be applied here in order to refute $oplus$ETH, or am I missing some important detail?


Get this bounty!!!

#StackBounty: #cc.complexity-theory #graph-theory #sat #counting-complexity #planar-graphs Disproving $oplus$ETH by reducing $oplus k…

Bounty: 100

In this question and its answer, they discuss about reducing CNF-SAT with $n$ variables and $m$ clauses to a (problem on) planar graph $G=(V,E)$ with $|V|$ as small as possible. It is said that the best known reduction has $|V| = m^2$, and that if a better reduction with $|V| in o(m^2)$ is found, that would refute ETH.


There is a reduction from $oplus k$-SAT with $n$ variables and $m$ clauses to $oplus$VERTEX COVER where the output graph $G=(V,E)$ is planar and has $|V| = 51(k+1)nm$. Such reduction clearly meets the $|V| in o(m^2)$ requirement when $k$ is a constant and $m$ is superlinear in $n$.


Question
Can the same line of reasoning made within the linked question be applied here in order to refute $oplus$ETH, or am I missing some important detail?


Get this bounty!!!

#StackBounty: #cc.complexity-theory #graph-theory #sat #counting-complexity #planar-graphs Disproving $oplus$ETH by reducing $oplus k…

Bounty: 100

In this question and its answer, they discuss about reducing CNF-SAT with $n$ variables and $m$ clauses to a (problem on) planar graph $G=(V,E)$ with $|V|$ as small as possible. It is said that the best known reduction has $|V| = m^2$, and that if a better reduction with $|V| in o(m^2)$ is found, that would refute ETH.


There is a reduction from $oplus k$-SAT with $n$ variables and $m$ clauses to $oplus$VERTEX COVER where the output graph $G=(V,E)$ is planar and has $|V| = 51(k+1)nm$. Such reduction clearly meets the $|V| in o(m^2)$ requirement when $k$ is a constant and $m$ is superlinear in $n$.


Question
Can the same line of reasoning made within the linked question be applied here in order to refute $oplus$ETH, or am I missing some important detail?


Get this bounty!!!

#StackBounty: #cc.complexity-theory #graph-theory #sat #counting-complexity #planar-graphs Disproving $oplus$ETH by reducing $oplus k…

Bounty: 100

In this question and its answer, they discuss about reducing CNF-SAT with $n$ variables and $m$ clauses to a (problem on) planar graph $G=(V,E)$ with $|V|$ as small as possible. It is said that the best known reduction has $|V| = m^2$, and that if a better reduction with $|V| in o(m^2)$ is found, that would refute ETH.


There is a reduction from $oplus k$-SAT with $n$ variables and $m$ clauses to $oplus$VERTEX COVER where the output graph $G=(V,E)$ is planar and has $|V| = 51(k+1)nm$. Such reduction clearly meets the $|V| in o(m^2)$ requirement when $k$ is a constant and $m$ is superlinear in $n$.


Question
Can the same line of reasoning made within the linked question be applied here in order to refute $oplus$ETH, or am I missing some important detail?


Get this bounty!!!

#StackBounty: #cc.complexity-theory #graph-theory #sat #counting-complexity #planar-graphs Disproving $oplus$ETH by reducing $oplus k…

Bounty: 100

In this question and its answer, they discuss about reducing CNF-SAT with $n$ variables and $m$ clauses to a (problem on) planar graph $G=(V,E)$ with $|V|$ as small as possible. It is said that the best known reduction has $|V| = m^2$, and that if a better reduction with $|V| in o(m^2)$ is found, that would refute ETH.


There is a reduction from $oplus k$-SAT with $n$ variables and $m$ clauses to $oplus$VERTEX COVER where the output graph $G=(V,E)$ is planar and has $|V| = 51(k+1)nm$. Such reduction clearly meets the $|V| in o(m^2)$ requirement when $k$ is a constant and $m$ is superlinear in $n$.


Question
Can the same line of reasoning made within the linked question be applied here in order to refute $oplus$ETH, or am I missing some important detail?


Get this bounty!!!

#StackBounty: #cc.complexity-theory #graph-theory #sat #counting-complexity #planar-graphs Disproving $oplus$ETH by reducing $oplus k…

Bounty: 100

In this question and its answer, they discuss about reducing CNF-SAT with $n$ variables and $m$ clauses to a (problem on) planar graph $G=(V,E)$ with $|V|$ as small as possible. It is said that the best known reduction has $|V| = m^2$, and that if a better reduction with $|V| in o(m^2)$ is found, that would refute ETH.


There is a reduction from $oplus k$-SAT with $n$ variables and $m$ clauses to $oplus$VERTEX COVER where the output graph $G=(V,E)$ is planar and has $|V| = 51(k+1)nm$. Such reduction clearly meets the $|V| in o(m^2)$ requirement when $k$ is a constant and $m$ is superlinear in $n$.


Question
Can the same line of reasoning made within the linked question be applied here in order to refute $oplus$ETH, or am I missing some important detail?


Get this bounty!!!

#StackBounty: #cc.complexity-theory #graph-theory #sat #counting-complexity #planar-graphs Disproving $oplus$ETH by reducing $oplus k…

Bounty: 100

In this question and its answer, they discuss about reducing CNF-SAT with $n$ variables and $m$ clauses to a (problem on) planar graph $G=(V,E)$ with $|V|$ as small as possible. It is said that the best known reduction has $|V| = m^2$, and that if a better reduction with $|V| in o(m^2)$ is found, that would refute ETH.


There is a reduction from $oplus k$-SAT with $n$ variables and $m$ clauses to $oplus$VERTEX COVER where the output graph $G=(V,E)$ is planar and has $|V| = 51(k+1)nm$. Such reduction clearly meets the $|V| in o(m^2)$ requirement when $k$ is a constant and $m$ is superlinear in $n$.


Question
Can the same line of reasoning made within the linked question be applied here in order to refute $oplus$ETH, or am I missing some important detail?


Get this bounty!!!