Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

Filter by
Sorted by
Tagged with
2
votes
1answer
442 views

Maximum difference between two shortest paths

My problem is the following maximization problem: Given: A graph $G=(V,E)$, lower bounds $l \in \{0,1,..,K\}^E$ and upper bound $u \in \{0,1,..,K\}^E$ for the edge weights, a source $s$ and two ...
3
votes
2answers
4k views

How to solve the Shortest Hamiltonian Path problem on Sparse Graphs?

Problem: Given a positive-weighted undirected graph, find the shortest path (in terms of total sum of edges) that visits each node exactly once. For a subset $S$ of nodes and a node $i\in S$, let $D[...
1
vote
0answers
100 views

Counting the number of connected components in a dynamic plane graph

I'm working on the following problem: let $G = (V, E)$ be a connected, planar graph. Our goal is to find a $d$-partition of $G$, $P = \{V_1, \ldots, V_d\}$, such that $G[V_i]$ is connected, and $\min_{...
2
votes
0answers
94 views

Unbalanced connected partition

Let $G = (V, E)$ be a connected graph with (possibly negative) vertex weights $w(v)\in\mathbb{Z}$. We want to partition the vertices into two parts such that the induced graphs $G'$ and $G''$ are ...
7
votes
1answer
432 views

Why isn't the Charikar algorithm for finding the densest subgraph optimal?

I read about the algorithm in Greedy Approximation Algorithms for Finding Dense Components in a Graph by Moses Charikar, and I tried to find an instance/graph where the algorithm returns a different ...
0
votes
1answer
369 views

How to design an algorithm which turns an undirected graph into directed with all nodes of indegree higher than 0? [closed]

Given an undirected graph $G=(V,E)$ devise an algorithm that will check whether its edges can be directed in such a way that the vertices of the resulting directed graph will all have indegree higher ...
7
votes
3answers
1k views

What are graph grammars?

I have found information on graph grammars and graph rewriting, but the papers that I find on it are a bit thick. Can someone give a quick overview of what graph grammars are, as well as an overview ...
1
vote
0answers
40 views

Are query-dependent ranking algortihms for web search doomed to be impractical? [closed]

Algorithms like HITS and SALSA are query dependent, and I've been given the impression that this makes them able to retrieve more accurate results. However, the query-dependent nature of these ...
1
vote
1answer
139 views

What are some techniques for “balancing” a tree beside heavy-light and centroid decomposition?

The only techniques i know are those in the title.
7
votes
1answer
164 views

Complexity of finding semi-ordered Eulerian tours in a 4-regular graph

I'm trying to figure out the time-complexity of the problem I describe below, which I call the semi-ordered Eulerian tour problem or the SOET problem. Either finding an efficient algorithm for this ...
1
vote
0answers
129 views

Cluster Assignment in the Stochastic Block Model

Recently, numerous papers have been published about the stochastic block model (SBM). In the literature about SBMs, a plethora of different settings are considered. I am interested in how vertices are ...
2
votes
2answers
231 views

One Generalization of Graph Isomorphism Problem

Say I generalize the language which consists of pairs of isomorphic graphs to take the following form: $GI(f) = \{ (G, H) \mid \exists \psi : V_G \rightarrow V_H, Pr_{a, b \in V_G} ((a, b) \in E_G \...
1
vote
0answers
60 views

\alpha-path on Euclidean graphs

Consider the following problem: Suppose we are given a G=(V, E) Euclidean Graph in the plane and a real $\alpha > 0$. For simplicity assume, there exists only one path whose summation of weights ...
-2
votes
1answer
84 views

Algorithm finding path with maximal ratio of white vertices [closed]

Recently I encountered an interesting graph problem and couldn't find proper solution: given undirected graph G = <V, E>, each vertex is either white or black....
8
votes
1answer
210 views

Decomposition of edges of eulerian graph into maximum number of cycles

I'm interested in the following problem. Given an eulerian graph $G=(V,E)$, we are to find a partition of its edges $C_1, C_2, \ldots, C_k$ ($\cup_i C_i=E$ and $i \neq j \leftrightarrow C_i \cap C_j =...
2
votes
1answer
273 views

Algorithm for computing unordered tree edit distance

I am trying to compute the edit distance between two dendrograms, one produced from hierarchical clustering, and the other manually constructed from some tree structure. In this setting, the rename ...
4
votes
0answers
749 views

Optimizing Maximum Weighted Matching (Edmonds Blossom)

Background: I've ported Edmonds Blossom Algorithm with Maximum Weighted Matching to Java: https://github.com/simlu/EdmondsBlossom/blob/master/src/Blossom.java The original Python implementation ...
2
votes
0answers
65 views

Complexity consequence of logarithmic boolean width of co-bounded degree graphs?

The paper On graph classes with logarithmic boolean-width claims that the boolean width of co-k-degenerate graphs is at most $k\log{n}$ and a lot of graph vertex partition problems can be solved in ...
4
votes
1answer
1k views

Minimal Cost of Eulerian Path

Problem: Given a planar (undirected and mostly sparse) graph with an Eulerian Path, we introduce a cost function f: (v, e1, e2) for all two edges e1 and e2 that share a vertex v. The function also ...
4
votes
1answer
349 views

Modifying Edmonds' Blossom Algorithm

Given a connected road network on an Island without one-way streets, where should I para-shoot in and what route should I take to deliver mail to all houses on the island (being picked up again by ...
1
vote
1answer
544 views

Clique cover problem

Consider the following graph problem. We are given a graph $\mathcal{G} = (\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ is the set of vertices and $\mathcal{E}$ is the set of edges. For each vertex $...
1
vote
1answer
204 views

Max weight travel on a graph with deadline

Given a deadline $D>0$ and a complete graph $K_n$ (with loops) in which each edge $e_{ij}$ has a weight $w(e_{ij}) \ge 0$ and a travel time $l(e_{ij}) > 0$. Starting from one of the nodes, we ...
1
vote
1answer
204 views

Max-weight connected & co-connected subgraph problem

The max-weight connected subgraph problem (MWCS) may be described as follows: given a simple graph $G=(V,E)$ and a weight function $w:V\to\mathbb{R}$, one seeks for a subset $L\subseteq V$ for which ...
5
votes
1answer
91 views

What is known about learning a maximal independent set in a (very) sparse graph?

Maximal independent set is known to be hard in many meanings (hard to approximate, $W[1]$-hard, etc.). But if the number of edges is very small, then the problem becomes simpler. Here, I'm interested ...
1
vote
1answer
207 views

Does a weighted graph have a path with weight zero?

Given a weighted digraph $G=(V,E)$, where each edge is associated with a weight (could be positive, negative, or zero). We define the weight of a path to be the sum of the weights along this path. ...
3
votes
0answers
130 views

Efficiently computing the union of all minimal unsatisfiable constraint sets in a first-order unification problem

Suppose we are given a standard first-order unification problem, represented as a set $D$ of term equality constraints, such that the system $D$ as a whole is unsatisfiable. Consider the minimal ...
2
votes
0answers
168 views

Approximating the Radius of a (Dense) Graph

For a (dense) graph, computing its radius is as hard as computer "All Pairs Shortest Paths" (APSP) [1]. So we can focus on approximating the radius. A $(1+\epsilon)$-approximating of APSP for a ...
-1
votes
1answer
132 views

A conceptual question regarding hardness proofs by reduction [closed]

If we restrict the input domain of a known NP-hard problem P so that this restricted domain is equal to the input domain of another problem S, then show that we can reduce a solution to P given input ...
0
votes
1answer
83 views

Complexity status of restricted k-clique [closed]

Restricted $k$-clique: Input: $(G,v,k)$ where $v$ is vertex in $V$ Output: k-clique containing vertex $v$. What is the space and time complexity status of this Restricted $k$-clique problem? Is ...
3
votes
0answers
97 views

Restricted k-set cover is in NL or L

Restricted $k$-set cover: Input: $(U,S_1,S_2,\cdots, S_n, k)$, $U=[n]$ and $S_i\subseteq U$ for all $1\leq i \leq n$. Output: $\bigcap_{i\in I}S_i$ where $I=\{1,i_1,i_2\cdots,i_k\}, i_1=min(S_1),i_2=...
3
votes
1answer
278 views

Solving a “tree-equation”?

Given two trees A and B, each of their nodes except some leaves have a "type" (which also determines the number of children, the node has, having that type). The leaves which don't have a type are ...
0
votes
1answer
98 views

Reachability in Dynamic Line Graph

Given a directed line graph $G = v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_n$, there are two operators, namely $\mathsf{move}(v_i, v_j)$: this operator moves $v_i$ to the position ...
2
votes
2answers
76 views

Maximal non-reducible vertex cover of a graph

Let $G=(V,E)$ be a graph (i.e. an undirected simple finite graph). We say that a vertex cover $V'$ of $G$ is non-reducible if any $V''$ with $V''\subsetneq V'$ is not a vertex cover of $G$. We say ...
1
vote
0answers
57 views

parametrized logspace algorithm for k-dominating set for planar graphs

$k$-Dominating set: Given a graph $G=(V,E)$ where $V$ is a set of vertices and $E$ a set of edges, and an integer $k$, the $k$-Dominating set problem determines if there exists a subset of vertices $...
0
votes
1answer
55 views

How to check whether graph of n vertex contains n/k disjoint k - complete graph by linear programming? [closed]

Edges are given in form of $X_{ij}$, which denotes whether there is edge in between $i^{th}$ and $j^{th}$ vertex. I am solving integer optimization problem and want to add this constraint to it.
1
vote
0answers
258 views

Can Lexicographic BFS be implemented in logspace?

Input: Given graph $G=(V,E)$ vertex labeling in some order Output: Change the labeling of vertices's such that labeling start $v_1$ as $u_1$, next label the neighbors of $v_1$ as $u_2,u_3,u_4,...$ ...
5
votes
2answers
233 views

Log space algorithms for modular decomposition tree

Can we have log space algorithms for modular decomposition tree (see definition) for any graph? If not, can we have log space algorithms for modular decomposition tree for any particular graph class? ...
2
votes
0answers
150 views

Paper regarding the complexity of the longest path problem on weighted directed graphs of bounded treewidth

I would like to cite a paper/report/etc that solves the following problem polynomially in $n$: Given a weighted directed graph $G=(V,E)$, $|V|=n$, of bounded treewidth $k \in \mathbb{N}$ and a source-...
1
vote
0answers
196 views

Algorithms for finding all cliques of a given degree in a graph

Consider a graph with $n$ vertices and maximum degree $Δ$. I would like to obtain all $s$ cliques, where $s≤Δ$ and both of them are small compared to $n$. Bron-Kerbosch algorithm gives all maximal ...
5
votes
0answers
96 views

Optimal polynomial time algorithm to determine if a random graph is $k$-colorable

Let $G(n, d/n)$ be an Erdos-Renyi graph with edge probablity $p = d/n$. For any fixed $k$ sufficiently large, it is known that $d_{k-col} \sim 2 k\log k$ is the sharp threshold for $G(n, d/n)$ to be $...
2
votes
0answers
878 views

Is there a better than brute-force solution to the shortest simple path problem?

Given as input graph which can possibly contain negative weight cycles, we can still ask for the weight of the shortest simple path between two vertices (i.e., a path that does not visit any vertex ...
14
votes
2answers
529 views

Add a matching to a Hamiltonian path to reduce the max distance between given pairs of vertices

What is the complexity of the following problem? Input: $H$ a Hamiltonian path in $K_n$ $R \subseteq [n]^2$ a subset of pairs of vertices a positive integer $k$ Query: is there a matching $M$ such ...
5
votes
0answers
81 views

Finding almost minimum cycle

Given an undirected unweighted graph, the almost minimum cycle is defined as the cycle whose length is greater than that of a minimum cycle by at most one. Itai and Rodeh in a seminal paper in 1978 ...
8
votes
0answers
271 views

Embedding a graph with specified edge lengths in d-dimensional space

Given any undirected edge-weighted graph (with weights > 0) and some dimension d, is there a way to assign positions in $\mathbb{R}^d$ to those vertices such that all of the edges between them have ...
2
votes
0answers
81 views

What can i learn about a graph about which only certain properties are known [closed]

1) Suppose we are given the following facts about a graph. What can we conclude/compute beyond these facts? The fact that graph $G(V,E)$ is planar, and thus that it is 4-colorable, The degree of each ...
4
votes
1answer
144 views

Hardness of Subgraph isomorphism problem for sparse pattern graph

Subgraph isomorphism problem is a well studied problem: given graphs $G$ and $H$, one needs to answer if $H$ contains $G$ as a subgraph. It was proven that this problem requires $|H|^{\theta(|G|)}$ ...
2
votes
0answers
151 views

Computational Complexity of cycle double cover

Let $\mathcal{G}$ be the set of all finite simple graphs. Let graph $G\in \mathcal{G}$ and $C_G=\left <C_1,...,C_m \right >$ be a sequence of cycles of $G$ for some $m$. For every edge $e$ of $G$...
2
votes
0answers
52 views

Examples of “Sandpile” TSP Instances

This question is closely related to this MO question. I would like to know, whether any (planar Euclidean) TSP instances are known, that exhibit avalanche effects similar to those ecountered in ...
2
votes
0answers
186 views

zero-sum path problem on a digraph

Consider a digraph $G=(V,A)$ with each arc weighted by either $+1$ or $-1$. A path is called a zero-sum path, if and only if all the arcs in its first half have weight $+1$, and all the arcs in the ...
7
votes
3answers
569 views

Hard problems for bounded vertex cover

We know that list coloring problem is W[1]-hard when parameterized by vertex cover. Are there any other problems which are also W[1]-hard parameterized by vertex cover?