Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.

learn more… | top users | synonyms (1)

0
votes
0answers
20 views

Community detection algorithms in Complex Networks (Graphs)

I need a definition (formal or informal) about what is "Robustness" in a community detection algorithm. How can we measure "robustness"? I couldn't find this on literature. Intuitively speaking for ...
4
votes
1answer
145 views

Local Graph Isomorphism to construct Global Graph Isomorphism

Does there exist a Graph Isomorphism Algorithm that uses Local Isomorphism to construct a Global Isomorphism? For example, two graphs are given, say, $H, G$. it is asked to determine whether $G\simeq ...
5
votes
1answer
126 views

Classes of graphs with superconstant treewidth

There are several interesting classes of graphs with bounded treewidth. For instance, trees (treewidth 1), series parallel graphs (treewidth 2), outerplanar graphs (treewidth 2), $k$-outerplanar ...
1
vote
1answer
113 views

Graph class with easy chromatic number, but NP-hard coloring

Is there a graph class for which the chromatic number can be computed in polynomial time, but finding an actual $k$-coloring with $k=\chi(G)$ is NP-hard? Without any further restriction the answer ...
6
votes
0answers
144 views

Is there a special name for the following type of graphs?

Weighted graphs such that if $x$ and $y$ are nodes in the graph, and $p$ and $p'$ are two paths in the graph between $x$ and $y$, then the weight of $p$ equals the weight of $p'$.
5
votes
2answers
145 views

The relationship between degree of vertex and size of dominating set

I was wondering is there any relationship between degree of vertex and size of dominating set. For example, if I know the number of vertices is $n$, and I could know each vertex in the graph has ...
-2
votes
0answers
47 views

Hamiltonian path in 3-connected graph [closed]

I have tried to find answer for my question, but I did not get result. I have a question:"Does there exist HAMILTONIAN PATH in 3-connected graph?" Thank you very much!!!
0
votes
0answers
84 views

How to efficiently generate a random 0-1 matrix of a given rank

How to efficiently generate a random $n\!\times\!n$ $0$-$1$ matrix of rank $k<n$?
6
votes
1answer
158 views

Complexity of a graph-rewriting problem

I recently came across the following problem which seems to fall in the context of graph rewriting problems: Input: A graph $G=(V,E)$ with maximum degree 3, an edge $e_0 \in E$ and pairs of graphs ...
5
votes
1answer
139 views

Canonical way of coloring graphs (individualization) for isomorphism purpose

Stefan Kratsch and Pascal Schweitzer in their paper Graph Isomorphism for Graph Classes Characterized by two Forbidden Induced Subgraphs give a characterization of graphs on which Graph Isomorphism ...
20
votes
1answer
246 views

Minor closed properties that are explicitly MSO expressible

Below, MSO denotes the monadic second order logic of graphs with vertex-set and edge-set quantifications. Let $\mathcal{F}$ be a minor closed family of graphs. It follows from Robertson and ...
1
vote
0answers
45 views

Optimal distribution of integer edge weights

I am not sure whether the following problem has been studied. Any help would be greatly appreciated. I have $L$ sets, $S_1, S_2,...,S_L$, each of $n$ elements, taken from a universe of $N$ elements. ...
2
votes
1answer
117 views

Does such model exists?

I have a problem on distributed graph, with the following model: 1. There is a Global Graph $G=(V,E)$ 2. There are $k$ computers. 3. Each computer $1 \leq i \leq k$ knows ALL the nodes of the ...
3
votes
2answers
165 views

Generate connected induced subgraphs as the satisfying assignments to a SAT instance

I want a SAT instance (in CNF) whose set of satisfying assignments are the connected induced subgraphs of a given input graph. A general solution would be helpful, but I really only need this when the ...
0
votes
1answer
91 views

Fractional but not integer multi-commodity minimum cost flow

I'm searching for an example digraph for the multi-commodity minimum cost flow problem with integer demand. There shouldn't be an integer but fractional optimal solution. I found here a similar ...
0
votes
0answers
74 views

Find max weight induced graph in a multipartite graph with one vertex from each part

Consider the follow problem: Input: $G=(V,E)$, a weighted $k$-partite graph with $n$ vertices. Output: $U \subseteq V$, one vertex from each part, maximizing the total weight of the induced graph ...
-5
votes
1answer
153 views

Is graph isomorphism still open for bounded clique width or bounded rank width? 2015 paper claims it is polynomial [closed]

To my knowledge, graph isomorphism for graphs with bounded clique width or bounded rank width is open. 2015 arxiv paper claims it is polynomial: Isomorphism Testing for Graphs of Bounded Rank Width ...
4
votes
2answers
199 views

Partition graph into 2 or more claw-free subgraphs

Is it NP-hard to partition the vertex set of graph G into k subsets so that they induce k claw-free subgraphs of G?
7
votes
1answer
493 views

Probability of two vertices being connected by some path in a random directed graph

Define $G(n, p)$ as a random directed graph ($n$ vertices; we put edge between two vertices with probability $p$). What are the known results for the following problem: Fix two vertices $v$ and ...
3
votes
0answers
67 views

Embedding distortion under group quotient

The high level question is as follows: Suppose some group (here assumed to be a vector space of $\mathbf{F}_2^n$) has a low-distortion embedding into $l_1$. Under what condition does the quotient of ...
3
votes
5answers
361 views

How to constrain a finite automaton (NFA and DFA) to a tree?

I have a finite automaton by the standard model Hopcroft & Ullman define: $$ M = (Q, \Sigma, \delta, q_0, F) $$ Where $\delta$ is the transition function mapping $Q \times \Sigma \mapsto Q$, such ...
1
vote
1answer
80 views

Is the topsort from “Structuring Depth-First Search Algorithms” guaranteed to be (reverse) stable?

In "Structuring Depth-First Search Algorithms in Haskell", implemented in Data.Graph in the Haskell standard library, an algorithm for topologically sorting graphs is given: ...
1
vote
0answers
113 views

Vertices adjacent to Exterior region of a Planar Graph(Algorithm)

Problem: I am looking for an algorithm which finds all vertices that are adjacent to exterior region of a planar graph(For a planar graph, any region=face can be considered as the exterior region ...
2
votes
2answers
196 views

Submatrix of small rank

Let $G=(V,E)$ be a graph with adjacency matrix $M=(m_{ij};i,j \in V )$ over $\mathbb{F}_2$ and $k \in \mathbb{Z^+}$. How can we find in polynomial time a subset $A \subseteq V$ such that The rank ...
6
votes
1answer
130 views

Graph that maximizes minimum hitting time?

Let $G$ be some connected bidirectional (or undirected) graph. We define a random walk as a walk that begins at a vertex chosen uniformly at random, and at each step proceeds to one of its current ...
15
votes
0answers
215 views

When does adding edges decrease the cover time of a graph?

When first learning about random walks on a graph $G$, one may have an intuitive feeling that adding edges to $G$ will decrease its cover time $C(G)$. However, this is not the case. The path graph ...
-1
votes
1answer
50 views

Reconstructing a 2D lattice graph from an unordered adjacency list

Is there any kind of algorithm that can map a set of points and their unordered adjacent neighbours to a 2D lattice graph that would then be addressable using X, Y coordinates? For example, given the ...
1
vote
0answers
42 views

Multicuts (or multiway cuts) for 3 Terminals of Minimum Capacity

For each fixed $k \geq 3$, the following well-known problem is NP-complete. k-Multicut (aka "Multiway Cut", "k-Way Cut", "Multicut") Input: $(N,l)$ where $N=(V,E,T,c)$ is an undirected $k$-terminal ...
3
votes
1answer
188 views

Approximation algorithms for the maximum $2$-independence set problem

I am interested in approximating the maximum $2$-independent set problem in arbitrary graphs. In a graph $G$ a set $I$ of vertices is called $2$-independent if the distance between any two distinct ...
15
votes
2answers
376 views

Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?

The $k$-cycle problem is as follows: Instance: An undirected graph $G$ with $n$ vertices and up to $n \choose 2$ edges. Question: Does there exist a (proper) $k$-cycle in $G$? Background: For any ...
2
votes
0answers
200 views

Complexity of counting spanning subgraphs that have cycle properties

Let $G = (V, E)$ be a connected undirected graph. I am interesting in counting the number of connected subgraphs having: $\ge 1$ cycle each (but can have any number of cycles), Exactly $k \ge 1$ ...
16
votes
0answers
220 views

Which graph parameters are NOT concentrated on random graphs?

It is well known that many important graph parameters show (strong) concentration on random graphs, at least in some range of the edge probability. Some typical examples are the chromatic number, ...
0
votes
1answer
42 views

Minimal-size extending set in a directed graph

Let $G=(V,E)$ be a directed graph, i.e. $V$ is a finite set and $E\subseteq V\times V$. We call a subset $J\subseteq V$ extending if for every $v\in V\setminus J$ there is a directed path from some ...
0
votes
0answers
59 views

What's the fastest algorithm to compute Max{max flow with single source and multiple sinks}

Given an arbitrary directed graph(not planar, cycles included), a source node $S$ and constant constraints on edges, for each sink node $t_i$, the maximum flow from $S$ to $t_i$ is denoted by ...
7
votes
1answer
346 views

Random walk and mean hitting time in a simple undirected graph

Let $G=(V,E)$ be a simple undirected graph on $n$ vertices and $m$ edges. I'm trying to determine the expected running time of Wilson's algorithm for generating a random spanning tree of $G$. There, ...
-1
votes
1answer
132 views

Graph isomorphism problem with invertible adjacency matrices

This question is supplementary to the question asked here. One of the answers give a class of graphs for which the adjacency matrices are invertible which is defined as follows. Given a ...
7
votes
1answer
143 views

Directed multigraphs as minimal automata

Given a regular language $L$ on alphabet $A$, its minimal deterministic automaton can be seen as a directed connected multigraph with constant out-degree $|A|$ and a marked initial state (by ...
0
votes
1answer
49 views

weighted directed Walk in a graph

I have a problem in graph theory and search the name and the complexity of the following problem : Let $G = (V,A)$ be a directed graph, $p : A \rightarrow \mathbb{N}$ be a weight on the arcs of $G$ ...
5
votes
1answer
168 views

About some possible optimality properties of Ramanujan graphs

The Ramanujan graphs are optimal from the Alon-Bopanna point of view but.. Is there any sense in which one can call Ramanujan graphs to be the "optimal" spectral sparsifiers? (Reference : ...
21
votes
1answer
394 views

Is it still open to determine the complexity of computing the treewidth of planar graphs?

For a constant $k \in \mathbb{N}$, one can determine in linear time, given an input graph $G$, whether its treewidth is $\leq k$. However, when both $k$ and $G$ are given as input, the problem is ...
5
votes
1answer
89 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 ...
5
votes
1answer
185 views

About a random walk with constant spectral gap

The existence of a graph with certain strange-looking properties will imply a counterexample to something I am playing with. I'm stuck on figuring out whether such a graph can exist and so I thought ...
2
votes
2answers
95 views

Are there Similar Distance Binary Error Correcting Codes?

I'm trying to find a low distortion embedding of the trivial metric space into hamming space. It seems this should be doable by using a large set of low dimensional vectors, with approximately equal ...
2
votes
2answers
116 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 ...
10
votes
1answer
171 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$ ...
2
votes
1answer
114 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 ...
-2
votes
1answer
146 views

A sufficient condition for non existance of hamiltonian cycle

I think i have a sufficient condition for non existance of hamiltonian cycle in a graph, I want to check if it has already been found, I tried googling for it and didnt find anything so far, how can i ...
15
votes
1answer
355 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 ...
13
votes
4answers
245 views

Does the infinite graph of diagonals have an infinite component?

Suppose we connect the points of $V = \mathbb{Z}^2$ using the set of undirected edges $E$ such that either $(i, j)$ is connected to $(i + 1, j + 1)$, or $(i + 1, j)$ is connected to $(i, j + 1)$, ...
2
votes
1answer
525 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 ...