Algorithms on graphs, excluding heuristics.

learn more… | top users | synonyms (1)

25
votes
1answer
402 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
0answers
87 views

Is finding the longest cycle in a directed graph vs undirected graph NP hard? [closed]

To find the girth or the shortest cycle in a directed/undirected graph one can for edge edge, remove it from the graph and find the shortest distance between the end points. The shortest such distance ...
3
votes
0answers
90 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
193 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
102 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 ...
4
votes
1answer
110 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
38 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
135 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 ...
2
votes
1answer
78 views

Upperbound the order of P3-free partition of P4-free graphs

A graph $G$ is $P_k$-free if and only if $G$ does not have an induced subgraph isomorphic to a path of $k$ vertices. Thus, $P_2$-free graphs are exactly independent sets (or stable sets). $P_4$-free ...
4
votes
0answers
70 views

Is minimum weight simple cycles through specified vertics fixed parameter tractable?

The problem formulation is as follows: Input: Undirected graph $G=(V,E)$, a set of vertices $S\subseteq |V|$, a weight function $w:E\to \mathbb{R}$ and a threshold $T\in \mathbb{R}$. ...
0
votes
0answers
82 views

Help with a special case for Hungarian algorithm

I am working on a problem and it appears to be a special case of Hungarian algorithm. In Hungarian algorithm for assignment problem, there are n people and n jobs. Each person can do any of n jobs ...
-2
votes
1answer
37 views

AVL-tree T: can T be a chain (linear BST) according to the definition?

AVL-tree T: can T be a chain (linear BST) according to the definition ? The definition of an AVL-tree is as follows: A binary search tree (BST) is called an AVL-tree if for every internal node ...
1
vote
4answers
151 views

Turing-complete computation models on graphs

There are many Turing complete computation models and new ones are devised all the time. I am looking for Turing-complete computation models based on graphs?
-1
votes
0answers
35 views

minimum cut versus sparsest cut?

My question is that I'm trying to find the sparsest cut in a connected, undirected graph (all weights are = 1). Basically, I am looking trying to find the smallest cut (i.e., number of edges cut since ...
0
votes
0answers
38 views

Are there any implementations of a graph crossing algorithm?

This is much more focused version of this question: Are there good implementations for easy subclasses of NP-hard graph problems Computing the graph-crossing number $cr(G)$ for a simple graph is ...
1
vote
0answers
82 views

Predicting the growth of a social network

I am building a predictive model for the growth of the amount of users of a new p2p protocol inspired by bitcoin and I would like to use historical data collected from the growth of major social ...
3
votes
1answer
141 views

Complexity of a parametrized min-cost flow problem

Consider the following min-cost flow variant: Input: a positively-weighted complete bipartite graph $G = (S, T, c)$ and extra vertices $s, t$ edges from $s$ to $S$ and from $T$ to $t$. lower ...
-5
votes
1answer
53 views

Efficient algorithm to create a directed dependency graph

I am looking for an efficient algorithm to create a graph like this: Initially the graph is filled with x then hs then ...
3
votes
1answer
86 views

Polynomial-time distinguishability threshold of planted clique

I have a basic question regarding the best known polynomial-time "distinguishing advantage" for the planted clique problem. By this, I'm referring to the problem of distinguishing the distribution ...
0
votes
0answers
128 views

A* in triangulated search space

I have a question regarding the optimality of a specific A* in triangulated search spaces (planar). Suppose I have some convex polygon (the boundary) with some number of obstacles (other convex ...
7
votes
3answers
160 views

On the size of P4-transversals of graphs

A subset $T$ of vertices of a graph $G$ is called a $P_4$-transversal if $T$ intersects every $P_4$ of $G$. In the context of this question, we consider $P_4$ as an induced path on 4 vertices. ...
4
votes
0answers
37 views

Has there been any work done on incremental connectivity in path graphs?

This set of lecture notes describes a data structure for decremental connectivity in path graphs that supports queries and removals in amortized O(1) each. Has there been any work done on incremental ...
1
vote
1answer
63 views

What graph properties only consider neighbours of a node in their calculations?

I'm looking for graph properties which only consider neighbours of a node and do not go beyond that. For example, nodes degree only considers neighbours or clustering coefficient also consider only ...
0
votes
1answer
78 views

Comparing two graphs

I have a quite big graph which has millions of nodes and edges. I modify the graph using an algorithm which only changes small portion of edges. At then end, I'd like to investigate how the algorithm ...
1
vote
1answer
81 views

Finding a special cut-set in an weighted undirected graph

I encountered this sub-problem while working on a problem about robustness of networks against link failures. Suppose we have an undirected graph $G=(V,E)$ such that edges in $E$ have weights taking ...
5
votes
0answers
65 views

Computing a transitive completion / path existance oracle

There has been a few questions (1, 2, 3) about transitive completion here that made me think if something like this is possible: Assume we get an input directed graph $G$ and would like to answer ...
5
votes
1answer
160 views

Grover's search algorithm for 3 coloring

According to Arora & Barak (pdf), pg. 186, for a polynomial-time computable function $f: \{0,1\}^n \to \{0,1\}$ (represented as a circuit computing $f$), Grover's algorithm finds in ...
1
vote
1answer
119 views

Figuring EasyVer problems - problems whose witness can be verified in time independent on the instance size

In a related question I've defined a class of graph problems which are verifiable using a time related only on the size of the witness: $EasyVer=\{L\subset \mathcal{G}\times \mathbb{N}| $ a witness ...
5
votes
0answers
77 views

Extending the definition of network surprise to weighted graphs

Recent research in graph clustering (also called community detection in other contexts) has shown that a definition beyond the traditional modularity (introduced by Newman, 2004) can be useful to ...
6
votes
2answers
204 views

NPI-candidate hereditary graph property?

A graph property is called hereditary if it is closed with respect to deleting vertices. There are many interesting hereditary graph properties. Moreover, a number of nontrivial general facts are ...
3
votes
0answers
75 views

Multi-Agent Pathfinding

Quoting from Wang and Botea 2011: An instance is characterized by a graph representation of a map, and a non-empty collection of mobile units $U$. Units are homogeneous in speed and size. Each ...
11
votes
3answers
310 views

NP-complete graph property that is hereditary, but not additive?

A graph property is called hereditary if it closed with respect to deleting vertices (i.e., all induced subgraphs inherit the property). A graph property is called additive if it is closed with ...
8
votes
1answer
101 views

Complexity of counting the number of edge covers of a graph

An edge cover is a subset of edges of a graph such that every vertex of the graph is adjacent to at least one edge of the cover. The following two papers say that counting edge covers is #P-complete: ...
2
votes
0answers
27 views

Hungarian Search and min net-cost-length paths

Consider the Hungarian Search algorithm for max/min weighted bipartite matching. Let G be a bipartite graph weighted by $w:E\rightarrow\mathbb{R}$ and let $M$ be a matching in $G$, let $S$ be a subset ...
16
votes
1answer
199 views

A good Library for testing whether a minors exists in a graph?

I would like to know if there are any free graph libraries for testing whether a specific set of minors exists in a given graph?
2
votes
0answers
57 views

Maximum number of triangles in a constrained delaunay triangulation

I'm looking for an upper bound for the number of triangles in a constrained planar delaunay triangulation. I know for d=2 delaunay triangulation, there are at most n+1 triangles where n is the number ...
0
votes
1answer
116 views

Number of “3-edge” triangles in a planar triangulation

I'm working on a triangle partitioning problem, and I'm trying to find and prove some properties of specific triangulations. The triangulations I'm dealing with are constrained delaunay triangulations ...
1
vote
0answers
51 views

Repartitioning a binary tree

Suppose I have a binary tree $G = (V, E)$ (with undirected edges) that is partitioned into sets of k vertices, where each set of vertices is a connected subgraph of $G$. Additionally, if there are ...
3
votes
2answers
247 views

Crown Rule Reduction In Parameterized Complexity - Vertex Cover - Notion Question

I am reading the paper "Kernelizations for Parameterized Counting Problems", and had a question regarding some of the notation in the paper ...
0
votes
0answers
108 views

Minimum Parity Weight Path - what is the complexity?

Consider an undirected graph, with non-negative weights on the edges, and two distinguished nodes $s\neq t$. If $P$ is a simple $s-t$ path in this graph, let $W_1(P)$ denote the sum of the weights ...
5
votes
2answers
88 views

Testing $H$ a topological minor of $G$ — algorithms that scale with $H$?

I am trying to find about algorithms that, given graph $H, G$, determine if $H$ is a topological minor of $G$ (and if so, exhibit this explicitly). Most of the literature on this topic seems to be ...
1
vote
1answer
134 views

minimal cycles in undirected graph

My initial problem is geometric, but I've reformulated it to a graph: In the graph above I need to find the set of minimal simple cycles that form the whole graph. The initial problem was to ...
13
votes
1answer
229 views

Is DAG subset sum approximable?

We are given a directed acyclic graph $G=(V,E)$ with a number associated with each vertex ($g:V\to \mathbb{N}$), and a target number $T\in \mathbb{N}$. The DAG subset sum problem (might exist under a ...
9
votes
7answers
414 views

Problems that are easy on unweighted graphs, but hard for weighted graphs

Many algorithmic graph problems can be solved in polynomial time both on unweighted and weighted graphs. Some examples are shortest path, min spanning tree, longest path (in directed acyclic graphs), ...
0
votes
3answers
157 views

Comparing graphs

I am looking for a kick in the right direction. What i am trying to do is to compute "similarity" between two graphs, where I define "similarity" as the number of shared paths. example: ...
3
votes
2answers
124 views

Clique graph of bipartite graphs

The clique graph $C$ of a given graph $G$ has the maximal cliques of $G$ as vertices and their is an edge between two vertices in $C$ iff the corresponding cliques share some vertices. Now for ...
7
votes
4answers
322 views

Partitioning graphs while minimizing inter-partition edges

I'm working on trying to partition a triangulated graph into connected subgraphs with some guarantees on the number of inter-partition edges. Here's an example of a triangulated graph that has been ...
12
votes
3answers
459 views

What is the complexity of this path problem?

Instance: An undirected graph $G$ with two distinguished vertices $s\neq t$, and an integer $k\geq 2$. Question: Does there exist an $s-t$ path in $G$, such that the path touches at most $k$ ...
21
votes
3answers
591 views

Optimization problems with good characterization, but no polynomial-time algorithm

Consider optimization problems of the following form. Let $f(x)$ be a polynomial-time computable function that maps a string $x$ into a rational number. The optimization problem is this: what is the ...
1
vote
0answers
35 views

Partition planar graph of vertices with at most degree 3 into connected subgraphs

I'm currently working on my thesis which deals with pathfinding over a Delaunay triangulated graph. I want to be able to partition my Delaunay triangulation into disjoint (regarding vertices) ...