Theoretical Computer Science

Questions tagged [graph-theory]

Ask Question

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

344 questions with no upvoted or accepted answers
Newest
Active
Bountied
Unanswered
Filter by
Sorted by
Tagged with
5
votes
0answers
136 views

Sampling small separators

Is there a tractable way to define an approximate distribution over small vertex separators of the graph? I'm looking for something along the lines of [Bayati,2008], a way to turn a single "this is a ...
5
votes
1answer
214 views

Hardness of approximating chromatic number of triangle-free graphs

The chromatic number of graph, $\chi( G)$ is hard to approximate for general graphs. Are there results of hardness of approximating $\chi(G)$ for triangle-free graphs?
4
votes
0answers
130 views

Power law for degree distribution of random KNN graphs?

Setup Sample random points from say standard Gaussian (or uniform) distribution in $R^{d}$ for some "d" and consider a KNN (K-nearest neigbour) graph for some K. Look at the degree ...
4
votes
0answers
79 views

Complexity of Encoding a Matroid Flow Problem in a Matrix

Context: Take a directed graph $G$ with a specified subset of source vertices $S$ and target vertices $T$. We say a subset $I\subseteq T$ of size $r$ is independent if there exist $r$ distinct ...
4
votes
0answers
95 views

Counting quotient graphs, but not exactly

All graphs considered will be directed graphs $G=(V,E)$, with $E \subseteq V \times V$ (so possibly with self-loops). For $k \in \mathbb{N}_{\geq 1}$, I will write $[k]$ the set $\{1,\ldots,k\}$. A $k$...
4
votes
0answers
144 views

Is there a standard name for this way of modifying graphs?

Let $G = (V, E)$ be an undirected graph. Let me take an edge $\{x, y\}$ (in blue in the drawing) such that $x$ and $y$ have other incident edges. Among the incident edges we choose one edge $e_x = \{...
4
votes
0answers
179 views

What's the fastest known algorithm for finding the diameter of a graph?

Given a positively weighted graph what's the fastest algorithm for finding the diameter for that graph?
4
votes
0answers
976 views

Eigenvalues of adjacency matrix of a connected bipartite graph

Let $G=(V,E)$ is a connected d-regular bipartite graph with the same number of vertices on both sides of the bipartition. It's known that that the largest eigenvalue of its adjacency matrix would be d,...
4
votes
0answers
133 views

Reduce $m$-clause 3SAT to PLANAR-3SAT in $O(m^{2-\varepsilon})$

The classic reduction from 3SAT to PLANAR-3SAT requires a removal of $O(m^2)$ crossings from a rectilinear representation of 3SAT with $m$ clauses. However, the crossing number inequality suggests ...
4
votes
0answers
152 views

Girth of graphs that decompose into two disjoint union of spanning trees

Let $G$ be an $n$-node graph that can be decomposed into two disjoint union of spanning trees. In particular, $G$ has $2n-2$ edges. It is not hard to show that the girth of $G$ is at most $O(\log n)...
4
votes
0answers
1k 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 ...
4
votes
0answers
142 views

Graph Isomorphism Algorithm of Vertex Transistive Graphs and other

What are the best known Graph-Isomorphism algorithms for below graph classes- 1.vertex-transitive, 2. edge-transitive, 3.arc-transitive (or symmetric) 4.distance-transitive. Are they GI Complete? ...
4
votes
0answers
193 views

Graph Isomorphism of Strongly Regular Graph with fixed parameter

$G, H$ are strongly regular graphs with parameter $(n, r, \lambda, \mu)$ where $\lambda$ is constant. Here, $n$ is the number of total vertices. Each graph is $r$ regular. Every two adjacent ...
4
votes
0answers
516 views

Graph partition with weighted vertices and edges

I am searching for an algorithm to apply to a specific graph partition problem that I am interested in. It feels like a topic that people from CS may have worked on but it is also different from ...
4
votes
0answers
85 views

size bounds for circuits recognizing graph properties (reachability, cyclicity, …)

I am interested in the following. Let the inputs of the circuit correspond to the arcs of a directed graph. The circuit has to output 1 iff there is a directed path from a given node S to a given node ...
4
votes
0answers
254 views

Definition of Clique width of graph

The clique width of graph $G$ is defined as minimum number of labels required to construct $G$ by using four operations. I would like to know why the name clique width is given to this definition. ...
4
votes
0answers
400 views

The largest connected component of a random subgraph

Let a graph on $|V|$ vertices and $|E|$ edges. We randomly sample $s= c \cdot \frac{|V|}{{d_{\text{av}}}}$ vertices, without replacement, where $d_{\text{av}}$ is the average degree of $G$ and $c$ is ...
4
votes
0answers
129 views

Can we decide Red-blue cut problem in polynomial time?

Given a directed graph whose arcs are coloured red and blue and integers $r$ and $b$, can we decide in polynomial time whether the digraph has a cut with at most $r$ red arcs and at most $b$ blue arcs?...
4
votes
0answers
148 views

Recognition problem of cycle permutation graphs

A cycle permutation graph is a cubic graph composed from two $n$-cycles each labeled $1, 2,..., n$, with additional edges connecting vertex $i$ in the first cycle to vertex $\pi(i)$ in the second, ...
4
votes
0answers
355 views

#EXP-Complete problems

Let #EXP be the counting variant of NEXP, in the same way that #P is the counting variant of NP. Are there any known #EXP-complete problems? In particular, has #Succinct Sat (the natural candidate) ...
4
votes
0answers
414 views

How to go from a DAG model to bounded treewidth?

I am cross posting this question from CS.SE since I believe it is research-related question. Given a Bayesian Network DAG $G$, we can transform it into a junction tree $T_G$ by performing two steps:...
4
votes
0answers
2k views

DAG partitioning for parallel computing

Consider a set of processes ($P=\{p_1, p_2,\dots, p_n \}$) and their data dependencies. Each process $p_i$ has an execution runtime which is denoted by $d_i$. We are interested to parallelize these ...
4
votes
0answers
120 views

What is the complexity of decomposing 2k-regular multigraphs into k-stars?

Imagine we have a graph, which is 2k-regular, and we want to decompose it into copies of k-stars. Then we could just at first decompose the graph into 2-factors, orient each of the factors and then we ...
4
votes
0answers
149 views

Vertex Covers whose vertex induced subgraph has an even number of edges and no isolated vertices

Let $G$ be a graph, and let $C_{E,0}$ be the number of those vertex covers of $G$ satisfying both the following properties: Their corresponding vertex induced subgraph has an even number of edges. ...
4
votes
0answers
453 views

Dynamic shortest path data structure for DAG

Let $G$ be a dynamic DAG (directed acyclic graph) where new vertices and new edges can be inserted. I am looking for an efficient data structure/algorithm to maintain the shortest path from a fixed ...
4
votes
0answers
2k views

Can the Hungarian method be used with real edge weights?

I had a problem where I need to apply bipartite weighted matching on a graph where the edge weights are real (positive and negative). I have looked at several implementations of the Hungarian method ...
4
votes
0answers
94 views

Explicit combinatorial construction minimizing intersection of sets

I'd like to know if anything is known about the following problem: Suppose we choose positive integer $t$ to be constant. Let $S = \{1,2,\dots,n\}$, where $n$ is sufficiently large. Consider a ...
4
votes
0answers
105 views

Are there any conditions for which ($k$-)apexness is preserved under $Y-\Delta$ transformations?

Lately, something I've been interested in is finding the set of forbidden minors for the apex graphs. One thing I tried to do was to look at the graphs which were known, and try to find a pattern in ...
4
votes
0answers
185 views

Expansion of constant-size sets

My question refers to the expansion of constant size sets of an expander graph. Suppose we are given an expander graph with Cheeger constant $\alpha$. What can be said about the edge expansion of sets ...
4
votes
0answers
237 views

Ising Model and Eulerian Subgraphs

Let $\mathcal{X}= \{1,-1\}^n$, $E$ the set of edges and $J$ some real-valued matrix. Van der Waerden's theorem gives constant $c$ and set of edge weights such that $$\sum_\mathbf{x\in \mathcal{X}} \...
4
votes
0answers
224 views

Follow-up on Nair/Tetali's Correlation Decay Tree for hypergraphs?

I'm wondering if anybody has followed up on Nair/Tetali's correlation decay tree construction for hypergraphs. I didn't find anything relevant in back-citation on google scholar. Interesting question ...
3
votes
0answers
43 views

Counting subsets of bipartite graph part which admit an induced perfect matching

Given a bipartite graph $G=(U \sqcup V, E)$, count $U^\prime \subseteq U$ for which $\exists V^\prime \subseteq V$ such that the induced subgraph $G[U^\prime \sqcup V^\prime]$ contains a perfect ...
3
votes
0answers
65 views

Minimum feedback arc set for dense directed graph

This is really a matrix problem, but the theory I believe lies in graphs. Consider some matrix $A$ and permutation matrix $P$, where we define $\tilde{A}:= PAP^T$. I want to pick $P$ such that if $\...
3
votes
0answers
136 views

Uniquely 4-colorable Planar Graph Conjecture?

My question is on Uniquely 4-colorable Planar Graph Conjecture mentioned in On purely tree-colorable planar graphs (and other papers of same(?) team such as "Theory on Structure and Coloring of ...
3
votes
0answers
113 views

Graph problems in P with unknown lower bounds

I am looking for references to interesting graph problems, which are known to be in P, but their precise big-O lower bounds are elusive. I would split this into 2 classes: problems, where we know of ...
3
votes
0answers
93 views

Isomorphic subforest problem

I recently read that the following problem is NP-Complete: Given a tree $T$, and a forest $F$, is there a subgraph of $T$ isomorphic to $F$? The reference provide was to the textbook “Computers and ...
3
votes
0answers
114 views

How to approach the “traveling salesman problem” with cost changing every time salesman reaches a new city

Let's say instead of finding the shortest path we have to maximize the profit in a year of the salesman under the following constraints. Salesman can go to a different city only on weekends, all ...
3
votes
0answers
157 views

Enumerating Minimal (a,b) vertex separators in a DAG

A vertex subset $S \subseteq V$ is an $(a,b)$ separator for nonadjacent vertices $a$ and $b$ if the removal of $S$ from a graph $G$ separates $a$ and $b$ into distinct connected components. $S$ is a ...
3
votes
0answers
110 views

Earliest forbidden subgraph characterisation

I wonder, what was the first non-trivial graph class for which there was a forbidden (induced) subgraph characterisation ? Of course, bipartite graph is one example but I am considering it as trivial ...
3
votes
0answers
75 views

Embed graph in $\ell_2$ space so that edge and non-edge distances are separated by a constant factor

Suppose I have an undirected unweighted graph $G = (V,E)$. Is there a way to compute points $x_v \in \mathbb{R}^d$ for each vertex $v \in V$ such that $||x_v - x_u|| = 1$ whenever $(u,v) \in E$ and $ |...
3
votes
0answers
55 views

Problem of determining if a $4$ connected graph has $k$ Hamiltonian cycles

Definition: Define the $k$-HamiltonianCycles problem as the decision problem that asks if a given graph has at least $k$ distinct Hamiltonian cycles. Question: Is there some constant $k$ so that the $...
3
votes
0answers
423 views

Generating a random connected bipartite graph

A (n, m, k)-bipartite graph is a bipartite graphs with: independent sets of size $\{n, m\}$ a total of $k \geq n+m-1$ edges We want an algorithm to generate a (n, m, k)-bipartite selected uniformly ...
3
votes
0answers
85 views

PTIME or NP-Hardness of stochastic objective function

I will begin by linking a previous post where I asked a general question for a stochastic setting which I describe below. It turns out that my "proof" for a restricted case had a mistake and there is ...
3
votes
0answers
91 views

Showing hardness of maximizing stochastic objective function over graph

Consider a graph $G = (V, E)$ with $n$ vertices and $m$ edges. Each vertex $v_i$ can take positive value $a_i$ with probability $p_i$ and value $0$ with probability $1-p_i$. The challenge is to ...
3
votes
0answers
309 views

Hardness of Approximation for minimum path cover in an undirected graph?

Given an undirected graph $G = (V,E)$, a path cover is a set of disjoint paths such that every vertex $v\in V$ belongs to exactly one path. The minimum path cover problem consists of finding a path ...
3
votes
0answers
143 views

Maximize number of edges covered by an independent set of vertices

Smallest vertex cover which is also an independent set asks about finding an independent set that covers all edges. This problem is known as the independent vertex cover problem and is equivalent to ...
3
votes
0answers
104 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
0answers
105 views

How many neighbors does a vertex has which are closest to a source vertex in random regular graphs?

Let $G=(V,E)$ be an undirected, random $r$-regular graph. Let $s,t\in V$, and denote by $N(v)=\{u\in V\mid (u,v)\in E\}$ the neighborhood of $v$. I'm looking for the distribution of the number of ...
3
votes
0answers
181 views

$CIS_G$ problem deterministic lower bound

In notes, http://www.cs.toronto.edu/~toni/Courses/CommComplexity2/Lectures/clique-notes.pdf, it is mentioned towards end of section $4$ that http://dl.acm.org/citation.cfm?id=237817 shows that ...
3
votes
0answers
435 views

$NP$-complete problems on cubic Hamiltonian graphs

The class of cubic Hamiltonian graphs is well studied class. I came across the fact that independent set problem is $NP$-complete when restricting input to cubic Hamiltonian graphs. I am interested in ...

1 2
3
4 5
…
7