Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

1
vote
0answers
158 views

Optimization Problem on a Directed Graph

I have the following graph optimization problem. In a directed graph $G$, each node $i$ is endowed with a real value $v_i$ (input) that encodes the minimum "activation threshold" of that node. For ...
5
votes
1answer
95 views

Vertex ordering of an graph such that neighbourhood of each vertex occurs as bounded sequences

Given an Graph $G(V,E)$ with $|V|=n$ and $|E|=m$. The goal is to find a vertex ordereing $\sigma$ of V such that for each vertex $v\in V$, all neighbours of $v$ occur in $O(\sqrt{m})$ sequences in $\...
4
votes
1answer
208 views

Maximum size-k cut

Here's my problem, Problem: Given a weighted undirected graph $G=(V,E,w)$ with weight function $w:E\rightarrow\mathbb{R}$ and an integer $k$, find a cut $S$ of graph $G$ such that $|S| \leq k$ and ...
3
votes
2answers
195 views

Favorable graph decomposition for dense graphs to solve independent set problem

I have to solve an independent set problem (ISP) on dense graphs with many cliques. To tackle the problem, I'm considering to use graph decompositions such as tree-, modular decomposition or clique-...
11
votes
1answer
377 views

Minimum equivalent digraph with respect to sources and sinks

Given a DAG (directed acyclic graph) $D$, with sources $S$ and sinks $T$. Find a DAG $D'$, with sources $S$ and sinks $T$, with minimum number of edges such that: For all pairs $u \in S, v \in T$ ...
3
votes
1answer
149 views

Assigning edge weights under shortest path constraints

We are given a graph $G = (V,E)$ and we need to find an assignment of non-negative edge weights (You must give every edge a non-negative weight). We are also given a set $R\subseteq V$ and mapping $c_{...
16
votes
1answer
579 views

Reference for mixed graph acyclicity testing algorithm?

A mixed graph is a graph that may have both directed and undirected edges. Its underlying undirected graph is obtained by forgetting the orientations of the directed edges, and in the other direction ...
-3
votes
1answer
552 views

Weighted matching algorithm for minimizing max weight

Consider the following matching problem: Input: a complete weighted bipartite graph with $n+m$ vertices, given by $n$, $m$, and $w_{i}$ a permutation of $[m]$ for each $i \in [n]$. Output: a ...
3
votes
1answer
1k views

Longest path in a DAG that's not too long

The problem I am interested in is a simple variant of the longest path problem on DAGs: find a path between two chosen vertices in a DAG such that the sum of the weights of its constituent edges is ...
2
votes
1answer
160 views

H-representation of convex hull

Consider a set of polytopes $P_j\;\;j=1,2,\dots,r$ with the same structure as follows: $P_j=\Big\{(x_{j1},\dots, x_{jt})\Big| \sum_{i=1}^t x_{ji}=1, x_{ji}\in [a_{ji},b_{ji}]\subseteq [0,1]\Big\}$ ...
2
votes
0answers
90 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
205 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
64 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
35 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
317 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 ...
6
votes
1answer
157 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 ...
0
votes
2answers
392 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 ...
12
votes
2answers
557 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
113 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
333 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
89 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 ...
6
votes
0answers
166 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
452 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
136 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
286 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 ...
3
votes
2answers
509 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
134 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 ...
4
votes
1answer
1k 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
655 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
717 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
174 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 ...
1
vote
1answer
216 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
262 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
416 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
329 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 ...
6
votes
1answer
218 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 $\...
10
votes
1answer
446 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
205 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
138 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 ...
6
votes
1answer
2k 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
431 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
96 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 6....
8
votes
0answers
294 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
128 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
116 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, ...
15
votes
2answers
1k 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
447 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
111 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
130 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 ...
27
votes
2answers
1k 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 ...