New answers tagged graphs
1
Set $V_i' = V_i \cap V'$. You can solve this by finding the maximum matching using at most $k$ vertices from $V_1'$ and at most $x-k$ from $V_2'$ for all $k \in [0, x]$. This in turn can be found with maximum flow.
To find this maximum matching, we modify the usual reduction to maximum flow. Let $s$ be the source and $t$ the sink. Let $l$ and $r$ be ...
0
Let us build the tripartite graph $G = (S := U\dot\cup V \dot\cup W, E)$, where $U := \{u_1, \dots u_n\}$ and similarly $V := \{v_1, \dots v_n\}$ and $W := \{w_1, \dots w_n\}$. Define $E$ as follows:
For $i, j \in [n]$, we add $(u_i, v_j)$ to $E$ for $u_i \in U$ and $v_j \in V$, if and only if $X_{ij} = 1$. Similarly we add $(v_i, w_j)$ to $E$ for $v_i \in V$...
0
Initially
dist[i][j] = AdjacentMatrix[i][j] //all directly reachable nodes are the base case.
How more can we improve on the base case?
Two possible algorithms which can work.
Find dist[i][j] = For all k { dist[i][k] + dist[k][j] }
This doesn't work because dist[i][k] can still be INF and is not finalized.
Fix one intermediate node k1 & find all ...
2
Disclaimer This solution assumes that the language $\text{Acyclic}$ is the language that contains exactly all acyclic directed graphs.
It is impossible to achieve this in polynomial time unless $\operatorname{P}=\operatorname{NP}$. The reason is that the problem you have to solve is NP-hard. It is called the directed feedback arc set problem. It is one of ...
0
The important part is that you start with an MST for the original graph. With this extra piece of information, you can build a proof by contradiction, as follows:
Construct the new tree as described (add the edge, check the cycle, remove the edge with the largest weight), now assume for contradiction that this tree is not an MST. This may be for several ...
0
It seems you consider intervals totally contained in others or disjoint only. Intervals can overlap partially, e.g. $[1, 3), [2, 4)$.
Scheduling in the general case (any value function for tasks, where you look for the maximum sum of values) is hard (the corresponding decision problem is NP-complete). There is copious literature on algorithms to solve this, ...
1
The language-theoretic answer:
Convert each regexp to a DFA, then use the product construction to take the intersection of their languages. Check whether the resulting DFA accepts any word (i.e., whether its language is non-empty). This might take exponential time in the worst case.
The pragmatic answer:
Every pattern has the form $\alpha \texttt{*} \...
1
The Kernighan-Lin algorithm tries to find a partition. As far as I can tell, the partition it finds might or might not be connected; I don't see any guarantee that it will output a connected partition. There is also no guarantee that it finds the optimal partition. Even if the optimal partition is connected, I don't think there is any guarantee that the ...
1
I think you mean partial order, as if you only have a preorder then there might not even exist any total order that is compatible with it.
Your argument seems to be missing something about how you construct your topological sort, as it implies that any topological sort works, which you disproved yourself. In your example $x,y,x',y'$ could be a topological ...
4
Kind of. But we're going to use the usual computer sciency way of describing this, using the language of binary relations.
You're probably already familiar with binary relations, like equality $=$, less-than-or-equal-to $\le$, subset $\subseteq$, and so on. In general, a binary relation $R$ over a set $X$ is a subset $R \subseteq X \times X$. If $(x,y) \in ...
0
Assume the graph is a directed acyclic graph throughout.
The algorithm is correct
In the first recursion, the algorithm finds a node $u$ that has no incoming edges.
In the second recursion, the algorithm checks whether $p(u)=n$, where for each node $v$, $p(v)$ is 1 plus the length of the longest path starting from that node.
There is a path that reaches ...
5
Deciding if a topological ordering with working set of size $\le k$ exists is NP-complete, even in bipartite graphs.
We can reduce pathwidth computation to this problem. Let $G$ be a undirected graph, whose pathwidth we want to compute. Now create an directed graph $H$, with vertex $v'$ for each vertex $v$ of $G$. For each edge $(u, v)$ of $G$, create a ...
1
Unfortunately, your algorithm is not correct.
Let us call a directed graph where each vertex has exactly one outgoing edge a unique-outgoing graph.
What does a unique-outgoing graph look like?
It consists of some directed tree and some directed cycles, all of which are disjoint except that every root of the trees is also a vertex of some cycle. Or, it ...
4
This is called the line graph of $G$. It actually has a wide variety of uses, as seen on that Wikipedia page, and the terminology is sufficiently standard that you should be able to mention it in a paper without defining it.
1
We can solve the problem in $\mathcal{O}(E \log V)$ by binary search.
We can identify the strongly connected components in a graph in linear ($\mathcal{O}(V + E)$) time. Thus we can check if the graph is strongly connected in linear time.
If $G(t_{0}) = (V, E(t_{0}))$ is strongly connected, so is $G(t) = (V, E(t))$ for $t \geq t_{0}$. Further, if $G(t_{0})$...
3
I know an example of a problem that is missing two of the four features you ask for - it is not NP-complete, and it is not a problem on graphs.
Buchfuhrer and Umans (2011) show that the minimum equivalent expression problem in Boolean logic is complete for $\Sigma^P_2$ under polynomial-time Turing reductions.
Given a Boolean $(\wedge;\vee;\neg)$-formula $F$...
1
You could try reducing your problem to the directed $s$-$t$ cut problem.
That is, given an instance $G=(V,A)$ of your problem, construct a graph $H$ that is initially a copy of $G$. Then, add to $H$ two new vertices $x$ and $y$, add an arc from $x$ to each $a \in A$ and from $y$ to each $b \in B$; all with a large weight (say $m+1$, where $m = |A|$). The ...
2
There can be exponentially many such subgraphs, so any such algorithm will necessarily be slow.
To enumerate all of them, choose any number $i$ in the range $[1,k]$, choose any subset $S$ of $i$ of the vertices, discard all edges that have an endpoint not in $S$, choose any subset of the remaining edges, then check if the graph with vertex set $S$ and the ...
0
One way to proceed may be to store for each node a list of parents so $parents[v_i]$ becomes an array of lists. There is also the same array of distance from $s$, $d[v_i]$ initially infinite for all $v_i$ but $s$ ($d[s] = 0$).
So like standard version of Dijkstra's algorithm, you maintaint a priority queue $q$ (sorted by $d$). When $v_i$ is depiled from the ...
Top 50 recent answers are included
