Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

965 questions
Filter by
Sorted by
Tagged with
461 views

Smallest set that intersects some given sets

Let $S_1,S_2,\ldots,S_n$ be sets that may have elements in common. I'm looking for a smallest set $X$ such that $\forall i,\,X\cap S_i \ne \emptyset$. Does this problem have a name? Or does it ...
143 views

Lower bound for orienting an asynchronous ring?

We require a lower message complexity bound of an asynchronous distributed algorithm that do the following: Given a undirected ring, with $n$ vertices, we want to let each node direct its edges to ...
1k views

Matching on bipartite graph - multiple edges

I have a weighted bipartite graph consisting of two sets $S$ and $P$. ($|S| > |P|$). I need to find a matching so that every node $s$ in $S$ matches a node of $P$. But a node $p$ in $P$ can match ...
416 views

Strongly Regular Graph and GI-Completeness

It is not known if graph isomorphism (GI) for strongly regular graphs (SRGs) is in P. Are there any hints that it might or might not be GI-Complete? Are there any strong consequences in such cases? (...
1k views

Is feedback vertex set problem solvable in polynomial time for 3-degree bounded graphs?

Feedback Vertex Set (FVS) is NP-complete for general graphs. It is known to be NP-complete for degree-$8$ bounded graphs due to a reduction from vertex cover. The Wikipedia article says that it is ...
388 views

Graph traversal with vertex and edge deadlines/windows

Hello the question was also posted on stackoverflow, but since this is theoretical oriented, thought I'd give it a try. I have an undirected graph similar to the one below, I need to implement a graph ...
197 views

Randomized rounding on a graph

Assume we are given an arbitrary undirected graph $G = (V, E)$ where $|V| = n$. We are also given real numbers $x_e \in [0, 1]$ for each $e \in E$. These numbers satisfy the following constraint: \...
357 views

Finding all-pairs anti-distance

Thanks for a great forum. This is my first post here. I am working on a signal processing application and the core of one the main algorithms reduces to a graph theoretical problem. Let $G=(V,E)$ ...
2k views

Count $k$-hop neighborhood for every vertex

For a node $v$ of a directed unweighted graph $G$, I define the $k$-hop neighborhood of $v$ as the set of vertices that are reachable from $v$ in $k$ hops or fewer (that is following a path with $k$ ...
2k views

Can the Hungarian method be used with real edge weights?

I had a problem where I need to apply bipartite weighted matching on a graph where the edge weights are real (positive and negative). I have looked at several implementations of the Hungarian method ...
529 views

Number of subgraphs with given edge parity

I would like to know whether counting number of induced (full) subgraphs (of an undirected graph) that have even number of edges is P or #P-complete. Additionally, is the problem easier if we assume ...
536 views

The ODD EVEN DELTA problem

Let $G = ( V, E )$ be a graph. Let $k \leq |V|$ be an integer. Let $O_k$ be the number of edge induced subgraphs of $G$ having $k$ vertices and an odd number of edges. Let $E_k$ be the number of edge ...
703 views

Number of subgraphs with a given number of nodes

Let $G = ( V_G, E_G )$ be a graph. Let $E_H \subseteq E_G$. The subgraph of $G$ edge-induced by $E_H$ is $H = ( V_H, E_H)$, where $V_H = \{ v \in V_G : \exists ( u, w ) \in E_H\ v = u \lor v = w \}$ ...
263 views

Finding a path with certain properties in a directed graph

Define a directed graph $G(V,E)$. We divide its vertex set $V$ into $t$ partitions: $p_1, p_2, \ldots, p_t$. Suppose we have a path $v_1 \to v_2 \to v_3 \to \ldots \to v_n$ where the same vertex can ...
118 views

Min-cut variation

I'm searching for an algorithm to do the following I have a graph $G = (V, E)$ and a set of terminal pairs $\{(s_i, t_i)\}$. I need to find a cut smaller than a given quantity $k$, such that there is ...
559 views

Choosing one number from each set so that the difference between maximum and minimum is minimized

Suppose I have four sets A={0, 4, 9}, B={2, 6, 11}, C={3, 8, 13}, and D={7, 12}. I need to choose exactly one number from each of these sets, so that the difference between the largest and smallest ...
185 views

411 views

In a random perfect matching of a regular bipartite graph, are all edges equally probable?

Consider a d-regular bipartite graph G, for d>=1. Obviously, G contains a perfect matching. Consider a perfect matching M in G chosen uniformly at random from all perfect matchings in G. Is it the ...
112 views

320 views

Do you know a shortest path algorithm for weighted graphs with hard time windows on the edges and waiting allowed?

Title says it all. I have a weighted Graph G={V,E,ETW} where V is the node set, E the edge set and ETW is a set of edge time windows. A edge time window is a 3-Tuple (edge, starttime, endtime) with ...
550 views

techniques or examples of analyzing a series of graphs

Let there be a sequence of graphs $G_1, G_2, G_3, ...$ constructed using some particular approach or algorithm. in this particular case $G_n$ is constructed by modifying $G_{n-1}$ in some "...
742 views

How to find the cycles which, together, involve the biggest number of non-shared edges in a directed graph?

I am not a computer science theorist, but think this real world problem belongs here. The problem My company have several units accross the country. We offered to employees the possibility to work ...