Algorithms on graphs, excluding heuristics.

learn more… | top users | synonyms (1)

2
votes
1answer
59 views

Finding a random regular graph with degree d

I'm trying to find undirected random graphs $G(V,E)$ with $|V|$ = $d^2$ for $d \in \mathbb{N}$ such that $\forall v \in V: deg(v) = d$. For $d \in 2\mathbb{N} +1$ this trivially is impossible as no ...
1
vote
1answer
59 views

Finding all possible simple cyclic paths in a digraph

I have a strongly connected component with over 200 vertices and more than 600 edges. I need to iterate through each simple cycle in the graph exhaustively, without specifying a particular node. Is ...
4
votes
0answers
69 views

Polynomial Time Delay Enumeration of Maximal Bipartite Subgraphs

Let $G=(V, E)$ be an undirected simple graph. Is it known how to list all the maximal bipartite subgraphs of $G$, without repetitions, and with a polynomial time delay and a polynomial space ...
3
votes
0answers
48 views

Statistical Algorithms vs Convex Relaxations - Planted Clique

I am trying to understand exactly what the lower bounds for the query complexity of statistical algorithms imply for convex relaxations for the planted clique problem ? A recent paper by Feldman, ...
0
votes
2answers
73 views

Finding a set of hubs in a graph

Suppose, we are given a graph $G = (V,E,d)$, where $V$ is the set of vertices, $E$ is the set of edges, and $d$ is a distance function $d: E \mapsto \mathbb{R^+}$. Let $S$ be the set of source ...
0
votes
1answer
53 views

Length bounded minimum cardinality cut in DAGs

Suppose I have a DAG with non-negative edge lengths. The problem is to compute the minimum number of edges which disconnects all paths of length L or less. We call this L-length bounded minimum ...
-2
votes
0answers
43 views

BFS to find nearest point in a set of points

Suppose that you have a set of nodes in a weighted undirected graph $S$. For every node $u \not \in S$, we want to find $(w_i, \delta_i)$, namely the node $w$ in $S$ that minimizes $d(u, w)$ and the ...
6
votes
1answer
166 views

Embedding a graph in the euclidean space

Given a graph $G=(V,E)$, find a mapping $f\colon V \rightarrow \mathbb R^d$ such that for every edge $(u,v) \in E$ we have that $||f(u)-f(v)|| \leq r$; and for every $(u,v) \not \in E$, we have the ...
-1
votes
0answers
43 views

Find multiple non-adjacent paths in a graph

Consider a non-directed graph. I want to find as many non-adjacent paths as possible from a source $s$ to a destination $t$. Two paths $P_1$ and $P_2$ are said to be non-adjacent to each other if none ...
-4
votes
0answers
41 views

Complexity of finding a clique of given size in a directed graph?

Given a directed graph G and 2 vertex V1 and V2 are strongly connected. i.e. there is an edge from V1 to V2 and also an edge from V2 to V1. If we try to find weather they are member of a clique of k ...
0
votes
0answers
38 views

Approximate distance preserving sparse graph representation that are not necessarily subgraphs

I am looking for a type of graph sparsifier that I think I have seen somewhere but now I can't find the paper anymore. I think the paper referred to it as a spanner, but that term is used for so many ...
3
votes
2answers
165 views

Runtime of Tucker's algorithm for generating a Eulerian circuit

What is the time complexity of Tucker's algorithm for generating a Eulerian circuit? The Tucker's algorithm takes as input a connected graph whose vertices are all of even degree, constructs an ...
0
votes
1answer
75 views

TSP heuristics for limited distance information

this is my first question on Theoretical CS. :) I've posted a similiar question on Mathoverflow and a friendly user advised me to post my question on this site. Problem: I'm looking for TSP ...
3
votes
1answer
160 views

Paths and Probabilities for a Random Walk on a Graph

I'm working on a problem about $N$ nodes that are randomly positioned on a rectangular grid. I want to take a sample of $n\leq N$ nodes by randomly selecting the first node then visiting the nearest ...
1
vote
2answers
228 views

Shortest path in DAG with path dependent arc costs

I've got the following problem Consider a DAG $G=(V,E)$ with $V=[v_1,…,v_n]$, and edge-set $E=[e_1,…,e_m]$, with associated costs $c_1,…,c_m$. The problem is to find the shortest paths from an ...
0
votes
0answers
163 views

How to solve such a graph optimization problem?

I have a graph optimization problem which is hard to describe in the title. There is a component based system which consists of components and data transmissions between components(components and ...
0
votes
1answer
70 views

Clique-Percolation Algorithm's “corner cases”

I'm programming an implementation of the Clique-Percolation algorithm, but I have many doubts about some corner cases. Imagine we want to find the communities of a graph using $k=4$. We are lucky and ...
0
votes
1answer
144 views

Is finding whether k different perfect matchings exist in a bipartite graph co-NP?

Few definitions first. The co-NP problem is a decision problem where the answer "NO" can be verified in polynomial time. The perfect matching in a bipartite graph is a set of pairs of nodes (a pair is ...
5
votes
1answer
148 views

Matching problems that are easy for bipartite graphs but hard for general graphs

Are there variants of matching problem (decision or optimization problem) that are polynomial time solvable for bipartite graphs but are NP-hard for general graphs?
2
votes
1answer
110 views

Topological sort with alternative choices of predecessors

I have a family of directed graphs over the same set of nodes $V$ defined as follows. Each node $v \in V$ has $k_v$ alternative choices for its set of predecessors. In other words, I am given a ...
3
votes
1answer
99 views

What is the best way to find an induced cycle basis of a graph?

My question is essentially what comes in the subject line: what is the best way to find an induced cycle basis of a graph (i.e., a cycle basis of the graph in which each cycle is an induced subgraph ...
5
votes
0answers
135 views

Approximating the clique size of the graph

Let $G=(V,E)$ be a graph. For a given $\rho \leq |V|$ and $\epsilon$ with $(0<\epsilon<1)$, is there any sublinear query algorithm known/possible to decide if the graph has a clique of size ...
9
votes
1answer
217 views

Simple path on dag with backward edges

What is the complexity of the following problem ($\in$ P? NP-hard?): Input: a directed acyclic graph $D=(V,E)$, a set of backward edges $E'\subset V\times V$, and two distinct nodes $s$ and $t$. ...
4
votes
1answer
126 views

Special properties of bipartite expanders

It is well known that expanders, and often the special case of bipartite expanders, have found many uses in derandomization, coding, etc. However, I am curious if there are any special properties of ...
0
votes
1answer
121 views

What is the intuition behind “hardness of approximation”? [closed]

I am reading a paper about graph matching problem. Which is, to some extent, an optimization version of the graph isomorphism problem. To my surprise, some closely related NP-hard problems are quite ...
5
votes
1answer
176 views

How does Camerini's algorithm for minimum-bottleneck-spanning-tree run in linear time?

I'm having a difficult time understanding Camerini's algorithm because there are very few clear explanations online. The goal is to find a minimum-bottleneck spanning tree in linear time. Camerini's ...
15
votes
0answers
254 views

Can short-distance connectivity be harder than connectivity?

Has anybody seen the following (or similar) question being considered: Can it be easier to determine the presence/absence of $s$-$t$ paths than to determine the presence/absence of short $s$-$t$ ...
2
votes
0answers
51 views

Hardness of approximately counting independent sets with a PRAS, rather than FPRAS

It is known that approximately counting the independent sets of a graph is hard, even if randomness can be used, and even if we restrict ourselves to bounded degree graphs with degree bound at least ...
0
votes
0answers
53 views

Applications of network clustering coefficient

Consider the global clustering coefficient of a graph as defined here . The clustering coefficient describes how likely it is for a random connected triplet of vertices to be closed. My question ...
8
votes
0answers
178 views

Are there sparsifiers that approximate vertices rather than edges?

Originally introduced by Benczur and Karger, cut sparsifiers let one take a dense graph $G=(V,E)$ and produce a weighted sparse graph on the same vertex set, where - only knowing the sparse graph ...
0
votes
0answers
85 views

CSP-problem, based on context-free grammar

I'm trying to solve a CSP (Constraint-Satisfaction-Problem), which is based on arbitrary context-free grammars. A quick example: Let's say we have a context-free grammar with the following production ...
1
vote
0answers
55 views

About the sparsest-cut question

Can someone kindly help clarify as to exactly what is the generally accepted definition of the "sparsest cut" problem for a graph? (Isn't the set which achieves the Cheeger constant for a graph, ...
0
votes
0answers
74 views

Efficient generation of Tournament Graphs

How to generate all non-isomorphic tournament graphs of order $n$ in an "efficient" way ? nauty (http://cs.anu.edu.au/~bdm/nauty/) can generate non-isomorphic tournaments, what is the complexity of ...
13
votes
2answers
723 views

Time complexity of counting triangles in planar graphs

Counting triangles in general graphs can be done trivially in $O(n^3)$ time and I think that doing much faster is hard (references welcome). What about planar graphs? The following straightforward ...
7
votes
2answers
315 views

Generalized Geography on graphs of bounded treewidth

Generalized Geography (GG) is played on a directed graph where a token is moved along arcs alternatively by two players. The vertices from which the token leaves are deleted. When a player cannot play ...
6
votes
1answer
88 views

Maximum number of geometrically disjoint paths - is the complexity known?

Let $G$ be an undirected graph, given with a planar drawing. We do not assume $G$ is a planar graph, we just fix a planar representation of it, such that each vertex is represented by a distinct ...
4
votes
1answer
115 views

Does it help for clique if the vertices are partitioned into 3 cliques?

A graph is $(p,q)$-colorable if its vertices can be partitioned into $p$ cliques and $q$ independent sets. For $(2,0)$-colorable graphs clique is polynomial. I am interested how easier (if any) is ...
24
votes
2answers
522 views

Why is “topological sorting” topological?

Why is "topological sorting" called "topological"? Is it just because it determines an order without altering any vertices or edges -- like a doughnut and coffee cup are topologically equivalent? Why ...
4
votes
1answer
100 views

Generalized geography on solid grid graphs

A post here For which families of graphs is Generalized Geography in $P$? mentioned that generalized geography on solid grid graphs is open. Is the question still open? A quick search on Google shows ...
2
votes
1answer
152 views

Efficient recalculation of the maximum flow when edge capacities are reduced

Assume that we have a (directed) graph $G(V \cup \{s, t\}, E)$ and an (integer) capacity function $c : E \mapsto \mathbb{N}$. Let $f : E \mapsto \mathbb{N}$ be a maximum $s-t$ flow on this graph. ...
0
votes
1answer
117 views

Many-one reduction from inequality problem to equality problem

Let the k-inequality-MIS problem be the decision problem whether an arbitrary graph $G=(V, E)$ contains a maximal independent set of at least size $k$, that is the corresponding language is: ...
2
votes
2answers
368 views

Has this formulation of pursuit evasion been researched? Similar to Helicopter Cops and Robbers Game

There are pursuers and evaders in the vertices of a directed graph G with one component. Each vertex must have atleast one outgoing edge (can be a loop). At each time t: The evaders must move ...
0
votes
0answers
47 views

Detect highly weighted but also densely inter-connected subnetworks

In a connected / undirected / node weighted (with both positive and negative weights) network, there are many papers studied about the 'Maximum weight connected subgraph' problem. But are there any ...
4
votes
3answers
590 views

Fastest polynomial time algorithm for solving minimum cost maximum flow problems in bipartite graphs

Orlin's algorithm is known to solve minimum cost maximum flow problems in $O(|E|^2 \log |V| + |E| \; |V| \log^2 |V|)$ time, where $|E|$ and $|V|$ respectively denote the cardinalities of the edge and ...
1
vote
0answers
61 views

Transitive reduction not provably minimal

Working on finding minimal equivalent graphs, which unlike transitive reductions only allows for edge removals from the original graph. I was under the impression that if you allow for new edges to be ...
7
votes
0answers
114 views

Is 4-colors precoloring extension for planar graphs fixed parameter tractable?

Given a planar graph $G=(V,E)$, there exists a quadratic algorithms for 4-coloring $G$ (and $G$ is surely 4-colorable). Assume you are given a set of $k$ constraints of the form "$v_i \text{ is ...
3
votes
1answer
139 views

Finding a minimum directed cut that splits a weakly connected bipartite graph into two such non-edgeless graphs

Consider a directed, weakly connected bipartite graph $G = (U, V, E)$ where $U$ and $V$ are sets comprising the nodes of $G$, and $E \subseteq U \times V$ is the set of edges. The task is to find a ...
2
votes
1answer
173 views

Algorithms for computing the minimal vertex separator of a graph

Background: Let $u,v$ be two vertices of an undirected graph $G=(V,E)$. A vertex set $S\subseteq V$ is a $u,v$-separator if $u$ and $v$ belong to different connected components of $G−S$. If no proper ...
2
votes
1answer
96 views

Maximum flow for all edges in an undirected graph

I was wondering if the following problem has been studied in the past, and what are some of the best ways people can come up with to solve it: Let $G=(V,E)$ be an undirected graph, which we use as a ...
0
votes
1answer
118 views

What is the Algorithm to find all the possible chordal graphs which can be formed by a given 'n' number of vertices

A chordal Graph is a connected graph which contains no chord-less cycle of size greater than three. They are also called as Triangulated graphs. All Paths are Chordal Graphs (No cycles). All Trees ...