Algorithms on graphs, excluding heuristics.

learn more… | top users | synonyms (1)

-2
votes
0answers
53 views

Knowing Topology and a question about it [on hold]

I have this question. Assume that the nodes know that the topology G is either a hypercube or a tree. Assuming a unique initiator, design an algorithm to discover the topology. In other words, ...
2
votes
1answer
90 views

Max flow: either saturate an edge or avoids

Is there a way to create a max flow graph such that it satisfies the condition that a flow either saturates an edge or completely avoids it. It can't have half its flow through one edge and half ...
-2
votes
1answer
81 views

Finding an exactly weighted st-path in a digraph [on hold]

I have a weighted digraph graph $G = (V,E)$ where the weights are positive and negative integers. The graph $G$ is not necessarily acyclic. The question is: given 2 nodes $v_1$ and $v_2$, is there a ...
4
votes
0answers
65 views

Indexing structure for all-pairs min-cuts in a huge DAG

I have a huge DAG - e.g., the dependency graph of all packages in a linux distribution. Suppose I'd like to make a user-friendly tool that makes it very easy to understand how to break the transitive ...
6
votes
1answer
194 views
9
votes
1answer
258 views

Finding similar vectors in subquadratic time

Let $d:\{0,1\}^k\times \{0,1\}^k \to \mathbb{R}$ be a function which we refer to as the similarity function. Examples of similarity function are cosine distance, $l_2$ norm, Hamming distance, Jaccard ...
7
votes
2answers
296 views

MAX 1 in 2 SAT Algorithm

The maximum satisfiability problem (Max-Sat) is the problem of finding the maximum number of clauses that can be satisified in a Boolean satisfiability instance. The exactly 1 in 2 Sat problem asks, ...
4
votes
2answers
181 views

Algorithms for online clique detection

Are there any algorithms which let you detect cliques when adding/deleting edges based on previously detected cliques? What would be the time/memory complexity of this approach?
0
votes
0answers
74 views

Highway dimension

I'm interested in understanding some recent theoretical results on pathfinding. Specifically this paper: http://research.microsoft.com/apps/pubs/default.aspx?id=201061 I understand from the paper ...
8
votes
1answer
192 views

Fast algorithm for weighted bipartite matching problem

I have a set of $n$ agents and a set of $n$ tasks, and I need to assign each agent to exactly one task such that a cost is minimised. Some agents are incompatible with some tasks. I have an ...
1
vote
0answers
60 views

Pruning a graph by removing vertices not part of any minimal Steiner tree

Given a sizable graph $G = (V, E)$, with $|V| \approx 1400$ vertices and $|E| \approx 1600$ edges, I have an optimization problem to find a connected subgraph of $G$ of size $k$ such that a given ...
1
vote
1answer
80 views

Node-weighted steiner problem with few terminals

Consider the node-weighted steiner problem: Input: a graph $G=(V,E)$, a set $T\subseteq V$ of terminals, a weight function $w: V\setminus T \to \mathbb{R}_+$. Output: a minimum weight ...
1
vote
0answers
97 views

Complexity of an algorithm for deciding 3-colorability of graph by the chromatic polynomial modulo $x-3$

As explained on MO computing the chromatic polynomial $P(G,x)$ modulo $x-3$ is enough for deciding 3-colorability. For non adjacent vertices $u$ and $v$, $G+uv$ is the graph with the edge $uv$ added ...
8
votes
1answer
234 views

DAG reachability with O(n log n) space and O(log n)-time queries?

For a directed acyclic graph ${\langle}V,E{\rangle}$, is there a data structure that allows for reachability queries without requiring quadratic space or linear time? Ideally I seek an algorithm ...
23
votes
1answer
346 views

The randomized query complexity of the conjoined trees problem

An important 2003 paper by Childs et al. introduced the "conjoined trees problem": a problem admitting an exponential quantum speedup that's unlike just about any other such problem that we know of. ...
0
votes
0answers
71 views

Graph database indexing

Graph databases are usually defined as index-free adjacency and that applies mostly to many current implementations - for example Neo4j - My question is: Is there are any references or papers with ...
2
votes
0answers
58 views

Weighted graph as average of many unweighted graphs

I have a measure $L(G)$ that is only valid for unweighted graphs because is based on discrete distributions and can't be extended to weighted graphs. My idea is that if I consider a weighted graph as ...
-1
votes
1answer
126 views

All pairs shortest paths in a DAG [closed]

I have studied the Floyd-Warshall and Johnson algorithms. I am trying to understand if the all pairs shortest paths research in a directed graph G can be implemented in a more efficient way if I ...
5
votes
2answers
665 views

Shortest path hitting a given vertex

I believe this problem to be NP-Complete, but I'm unable to find any references on possible reductions. Given a weighted graph (either undirected or directed, I cannot find results for either but am ...
5
votes
0answers
96 views

Spectrum of absorbing random walk for regular graphs

I have a symmetric Markov chain given by the matrix $P$. Let $M$ be a set of special states of the chain (called marked states, they correspond to solutions to some problem). We can write $P$ as ...
0
votes
0answers
50 views

Graph Propagation Times

Consider the following simple rule for propagation: given a (for simplicity) grid $G$ of size $nxm$ containing integers, and set of starts $s = S_i, s_x, s_y\in \{ 0, 1, 2, 3, ...\}, s_x < n, s_y ...
2
votes
0answers
79 views

What is the name for this special case of the Travelling Salesman involving dynamic edge costs?

This is a modeling / taxonomy question. Is there a name for this type of problem? I came up with the following graph problem for a pizza delivery truck, which starts with zero dollars and enough fuel ...
2
votes
1answer
111 views

When replacing an edge with a graph gadget preserves graph isomorphism?

The transformation replacing an edge by a graph gadget is widely used in graph theory. As an example, in an answer Marzio De Biasi subdivided edges which increases the girth while preserving GI. A ...
27
votes
4answers
772 views

What is simplest polynomial algorithm for PLANARITY?

There are several algorithms that decide in polynomial time whether a graph can be drawn in the plane or not, even many with a linear running time. However, I could not find a very simple algorithm ...
-1
votes
1answer
100 views

What can we say about all cycles in graphs (connected undirected graph) [closed]

I am considering one optimization problem who is known to be NP hard in the general setting. But there is application of this problem on the cylces of graph. This problem involves several sets and ...
10
votes
1answer
237 views

Identifying useless edges for shortest path

Consider a graph $G$ (the problem makes sense both for directed and undirected graphs). Call $M_G$ the matrix of distances of $G$: $M_G[i, j]$ is the shortest path distance from vertex $i$ to vertex ...
4
votes
0answers
127 views

K-path cover problem for a DAG

I am doing a little literature review and I was trying to know if, for a directed acyclic graph, the minimum k-path cover problem is solvable in polynomial time. A k-path cover is a set of paths with ...
7
votes
4answers
473 views

Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs

Crossposted from MO. Let $C$ be a graph class defined by a finite number of forbidden induced subgraphs, all of which are cyclic (contain at least one cycle). Are there NP-hard graph problems ...
1
vote
0answers
42 views

Minimum Clique edge cover to cilque vertex cover

Suppose, there is an algorithm for enumerating minimum clique edge cover. Is it always possible to convert the algorithm to enumerate clique vertex cover ?
4
votes
0answers
67 views

Why is it necessary to maintain a collection of forests in the dynamic graph data structure?

In their paper "Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity", Holm, de Lichtenberg, and Thorup describe a data structure ...
3
votes
2answers
146 views

Is optimal equal-point graph splitting NP-Complete?

The problem is "Given a graph G with kn points, divide it into k pages of n points such that the number of edges between points on different pages is minimal." (I've worked on it with undirected ...
0
votes
0answers
67 views

planted cliques in continuous graphs?

The question is pretty simple (almost the same as that mentioned in the title). Is there an equivalent definition of the planted clique problem for Continuous graphs ...
1
vote
1answer
88 views

Reducing the bandwidth of non-symmetric matrix

Is there an efficient algorithm to reduce the bandwidth of a directed graph's adjacency matrix? Something like the reverse Cuthill-McKee, but for non-symmetric matrices.
0
votes
0answers
102 views

Distance oracles in trees

Given an unweighted tree $T=(V,E)$ what is the minimum number of distance oracles that allow to detect the position in the graph of every node $v$? A distance oracle is "special node" $u$ of the ...
2
votes
0answers
143 views

Independent Sets that are Odd Covers

I am interested in a certain type of independent set I call an "odd cover". A set of vertices is independent if no two vertices in the set are connected with an edge. A set of vertices is an "odd ...
9
votes
1answer
133 views

Complexity of counting graph endomorphisms

A homomorphism from a graph $G = (V, E)$ to a graph $G' = (V', E')$ is a mapping $f$ from $V$ to $V'$ such that if $x$ and $y$ are adjacent in $E$ then $f(x)$ and $f(y)$ are adjacent in $E'$. An ...
4
votes
0answers
84 views

What is the complexity of minimum weight odd T-join?

Let $G=(V,E)$ be an undirected graph and let $T \subseteq V$. A subset $J$ of $E$ is called a $T$-join if $T$ is equal to the set of vertices of odd degree in the graph $(V, J)$. Further $J$ is an odd ...
3
votes
0answers
138 views

Standard reference for efficient computation of non-intersecting Eulerian circuit

A plane graph $G$ defines a cyclic ordering $O(v) = \langle v_1, v_2, \dotsc, n_{\deg(v)}\rangle$ on the neighborhood $N(v)$ of each vertex $v \in V(G)$. A non-intersecting Eulerian circuit $C$ is an ...
5
votes
0answers
66 views

Computing diameter of a 3D polyhedron

A polyhedron is given as a set of its vertex coordinates. Is it possible to find its diameter faster than $O(n^2)$? Or, maybe, some another common polyhedron representation would help fasten this?
3
votes
1answer
264 views

Hardness of 3-dimensional matching variant

I am thinking about a variant of 3-dimensional matching. In normal 3d matching, we have three sets of vertices $X$, $Y$ and $Z$, and a set of edges $E \subseteq X \times Y \times Z$. We want to choose ...
8
votes
2answers
210 views

For which families of graphs is Generalized Geography in $P$?

As @Marzio mentioned, the following game is known as Generalized Geography. Given a graph $G=(V,E)$ and a starting vertex $v \in V$, the game is defined as follows: At each turn (two players ...
3
votes
1answer
207 views

Algorithm to find s-t min paths in a weighted graph

Given a directed graph with $n$ vertices with non-negative edge weights, I would like to find first $n^2$, $s$-$t$ minpaths with minimum sum of non-negative weights. By using Dijkstras shortest path ...
3
votes
1answer
224 views

Definition of fractional in theoretical CS

What is the definition of the word "fractional" in algorithms? I have encountered the word in phrases like "fractional algorithm", "fractional node routing problem". Note: English is not my native ...
0
votes
1answer
92 views

Finding distances in graphs where shortest path has a large number of nodes

I was wondering what is the most efficient way to find the shortest distances between all pairs of vertices in a graph where the shortest path between those vertices has length $\geq L$. The only way ...
0
votes
0answers
43 views

Competitive throughput model definition

I am reading a paper on optimal node routing and it is mentioning the phrase "competitive throughput model". I have searched for a definition, but I didn't find anything. Could anybody give me a ...
19
votes
2answers
380 views

Is it necessary to call matrix multiplication $n$ times to find a claw

A claw is a $K_{1,3}$. A trivial algorithm will detect a claw in $O(n^4)$ time. It can be done in $O(n^{\omega+1})$, where $\omega$ is the exponent of fast matrix multiplication, as follows: take the ...
1
vote
1answer
509 views

Run Dijkstra's algorithm twice to detect negative-weight cycles?

Dijkstra's algo (for finding single-source shortest path) assumes that once a vertex has been chosen for expansion (aka exploration), its shortest path has been found. This can only be true if there ...
8
votes
0answers
134 views

Complexity of unique coloring of graphs

The Isolation lemma of Mulmuley, Vazirani, and Vazirani can be used to show that certain $\mathsf{NP}$-complete problems can be reduced via randomized polytime reductions to the unique solution ...
4
votes
2answers
168 views

Shortest distance/path between two households

If you wanted to know the shortest distance/path between two household addresses, which data structure(s) would you use to return the answer efficiently? Say you are considering the set of all ...
2
votes
0answers
109 views

Graph partition with objective over intra-partition weights

I have a problem in which I need to find an optimal graph cut that maximizes an objective over weights not on the cut. I have looked at the literature but have not been able to find any similar ...