Algorithms on graphs, excluding heuristics.

learn more… | top users | synonyms (1)

1
vote
1answer
31 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
80 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
108 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 ...
19
votes
1answer
303 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
60 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
52 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
117 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 ...
-1
votes
0answers
39 views

Maximal-clique to domination number

Suppose for a graph family, i have an algorithm to compute all the maximal cliques in polynomial time. Is it possible to compute the Dominating set in polynomial time? So far, i have tried to use the ...
-4
votes
0answers
82 views

Preserving connectivity from a vertex by edges deletion [migrated]

Given a connected graph $G$ and a vertex $v$, is it polynomially solvable to find a maximal cardinality set of edges incident to $v$, which deletion (still) leaves vertex $v$ to be connected with all ...
-2
votes
0answers
39 views

Data structures in Clauset-Newman-Moore algorithm for finding community structure in networks?

I am trying to implement the Clauset-Newman-Moore algorithm for discovering community structure in python. The paper describing the algorithm is in the comments because I cannot post more than 2 links ...
5
votes
2answers
644 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 ...
4
votes
0answers
61 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
48 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
78 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 ...
-1
votes
0answers
33 views

Need an optimal algorithm for the following set related problem

Suppose we are given a finite collection of sets $\mathcal{G}$ where each set has $k$ elements. Let $V(\mathcal{G}) = \cup_{B \in \mathcal{G}} B$ denote the vertex set. For example if $\mathcal{G} = ...
2
votes
1answer
105 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
756 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
97 views

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

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
227 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
115 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
446 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
39 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
144 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
66 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
75 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
99 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
133 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
123 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
81 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
135 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
64 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?
2
votes
1answer
220 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
205 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
200 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
79 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
371 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
467 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
131 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
163 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
97 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 ...
31
votes
4answers
914 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
200 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 ...
5
votes
0answers
113 views

Approximate c-chromatic number, each color class is P4-free (cograph)

The classic chromatic number of graph, $\chi(G)$, describes the minimum number of colors needed so that each color class is an independent set. There are many other graph coloring definitions. One of ...
7
votes
1answer
166 views

Tight examples for approximating the feedback vertex set problem

There are several 2-approximation algorithms for the UNWEIGHTED feedback vertex set problem (FVS), which are summarized in [4]. Note that the reduction from vertex cover to FVS is ...
2
votes
0answers
45 views

Eulerian Triangulations

Hi i am looking for algorithms to decide whether a planar pointset has a eulerian triangulation i.e. a triangulation that makes every vertex of even degree. I cam across this page ...
7
votes
2answers
148 views

Do graphs with large number of paths contain large chain minor?

Definition: A "$k$-chain" is a multi-graph obtained from a path of length $k$ by duplicating every edge. Note that the number of paths between two endpoints of a $k$-chain is $2^k.$ Question: Let ...