Algorithms on graphs, excluding heuristics.

learn more… | top users | synonyms (1)

7
votes
1answer
187 views
+50

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 ...
0
votes
0answers
54 views

k- maximally link disjoint paths and equations

This problem is NP-complete and also discussed to some extent in Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs from the level of my reading from various ...
7
votes
2answers
287 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
168 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
72 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 ...
-2
votes
1answer
61 views

Communities in a graph [on hold]

While studying about communities in a graph, i was curios regarding any algorithm which deals with projection of these communities in 2D/3D plane. Most of the algorithm i have studied were related to ...
8
votes
1answer
188 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
56 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
76 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 ...
5
votes
0answers
140 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
343 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
66 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
57 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
121 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
662 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
95 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
49 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
108 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
768 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
99 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
123 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
466 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
40 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
82 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
101 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
130 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
82 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
65 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
261 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
209 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
204 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
86 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
378 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
492 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
166 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
104 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 ...
32
votes
4answers
967 views

Examples where the uniqueness of the solution makes it easier to find

The complexity class $\mathsf{UP}$ consists of those $\mathsf{NP}$-problems that can be decided by a polynomial time nondeterministic Turing machine which has at most one accepting computational path. ...
3
votes
1answer
201 views

For which values of $k$ is minimum length undirected $k$-disjoint-paths in $\mathcal{P}$?

In a related question, Saeed and Super8 have mentioned the Robertson-Seymour theory which enables us to find $k$ disjoint paths between pairs of vertices $\{s_i,t_i\}_{i=1}^k$ in poly time for fixed ...
1
vote
2answers
220 views

For which values of $k$ is the $k$-disjoint paths problem in $\mathcal{P}$?

The $k$-Vertex-Disjoint Paths Problem ($k$-$\text{DPP}$) is defined as follows: Input: A graph $G=(V,E)$ and $k$ pairs of vertices $(s_1,t_1),\ldots,(s_k,t_k)$. Question: Does there exist ...