Algorithms on graphs, excluding heuristics.

learn more… | top users | synonyms (1)

0
votes
0answers
2 views

Adversarial Search Algorithms

What are the best adversarial search algorithms? I understand that this may seem like a subjective question. However, I am asking for what situations are different algorithms best for. In particular, ...
2
votes
0answers
38 views

Claw finding using quantum walk: superposition for Szegedy's framework

Within Claw Finding Algorithms Using Quantum Walk there is the subroutine $claw_{detect}$ described. As in above paper: Let $J_f(N, l)$ and $J-G(M, m)$ be Johnson graphs. Let $F$ and $G$ be vertices ...
4
votes
1answer
83 views

Minimum weight matching in general graphs with additional input specifying the number of matched edges

We know of the minimum weight perfect matching problem in general graphs which can be solved using a primal-dual algorithm. Assume, we have an additional constraint specifying the exact number of ...
0
votes
0answers
62 views

Find the number of vertices that belong to all the maximum matchings of a general connected graph [duplicate]

The given graph is connected but not necessarily bipartite. Please describe the complete approach with useful links , I read stuff related to augmenting paths but could not comprehend well. An O(VE) ...
2
votes
0answers
17 views

centralized deterministic Spanner construction with low degree and low stretch

Does there exist a centralized deterministic spanner construction with low degree and low stretch both independent of the graph diameter (no log D factor), but can be dependent on the number of nodes. ...
12
votes
1answer
237 views

Gentle introduction to the algorithmic aspects of tree-depth

Treewidth and pathwidth are popular parameters, measuring the closeness of a graph to a tree or a path, respectively. Indeed, it seems treewidth is so popular it is featured in many papers, books, and ...
4
votes
0answers
70 views

Graph factors of maximum weight

I am trying to find references to a weighted version of the graph factor problem for the case when the "target degree" is a set of integers with "gaps" of size at most one. The unweighted version of ...
2
votes
1answer
137 views

Complexity of simple undirected graph isomorphism problem

We define a simple undirected graph as a graph where no vertex has a loop and there is only zero or one undirected, unweighted edge between any pair of vertices. My question: What is the complexity ...
11
votes
2answers
328 views

Number of vertices present in all maximum matchings

Given a graph $G$, we need to find the cardinality of the largest set of vertices so that each of them are present in every maximum matching possible. Is there a solution beside the obvious remove ...
2
votes
1answer
90 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
71 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
74 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
50 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
78 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
55 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 ...
7
votes
1answer
171 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 ...
0
votes
0answers
39 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
166 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
79 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
216 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
235 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
170 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
74 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
148 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
152 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
114 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
102 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
137 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
279 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
129 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
122 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
182 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
256 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
57 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
183 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
88 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
730 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
319 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
91 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
117 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 ...
25
votes
2answers
536 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
104 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
158 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
121 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
372 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
48 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
680 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 ...