Questions tagged [graph-theory]

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

312 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4
votes
0answers
118 views

A variant of hitting set: finding a matching to hit all edge sets

In general, the hitting set problem is given a family $\cal S$ of sub-sets, $\{S_1, \cdots, S_h\}$, and a universal set $U = \bigcup_{i\in [1,h]} S_i$. It asks for a minimum set $H \subseteq U$ ...
4
votes
0answers
127 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
128 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
768 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
140 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
185 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
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
246 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
369 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
128 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
146 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
328 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
351 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
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
434 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
93 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
104 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
181 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
234 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
223 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
87 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
132 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
74 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
50 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
90 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$...
3
votes
0answers
280 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
82 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
90 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
207 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
583 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,...
3
votes
0answers
135 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
445 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 ...
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
104 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
179 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
434 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 ...
3
votes
0answers
59 views

APx hardness of Multiterminal Cut Problem

In a Multiterminal Cut problem input is a graph G=(V,E) and a set of k terminals T which is a subset of vertex set V. There is a weight w(e) associated with each edge in the graph. The question is to ...
3
votes
0answers
104 views

Online bridge and nonbridge counting (identification)

I was wondering if there is any efficient (possibly armortized poly-logarithmic) online algorithm which supports counting (identification) of bridges- and non-bridges online, i.e. during a sequence of ...
3
votes
0answers
379 views

Finding modular decomposition of graph

I am trying to learn how to find modular decomposition of graph using the method given in the paper Simpler Linear-Time Modular Decomposition via Recursive Factorizing Permutations. I am unable to ...
3
votes
0answers
229 views

Bipartite small-world networks

The Watts-Strogatz model describes a mechanism of generating small-world networks. The idea is to start from a ring network in which each node is connected a fixed number of its closest neighbors. ...
3
votes
0answers
251 views

Independent Sets that are Odd Covers

I am interested in a certain type of independent set I call an "odd cover". A set of vertices is independent if no two vertices in the set are connected with an edge. A set of vertices is an "odd ...
3
votes
0answers
146 views

Bound on a graph diameter, considering the minimal vertex degree

Let $G$ be a connected (strongly connected) graph (digraph). Assume that the minimal vertex degree (in/out degrees) of the graph is $\delta$ (are $\delta^-,\delta^+$). What is the maximal diameter ...
3
votes
0answers
165 views

Is there any equivalent for Bondy-Chvátal theorem for directed graphs?

Bondy-Chvátal theorem cannot be applied for directed graphs, is there any equivalent theorem that can be applied for them?
3
votes
0answers
108 views

Intractability of restricted decomposition of connected bridgeless cubic graphs

A 2-factor of graph $G(V, E)$ is a set of vertex-disjoint cycles that cover $V$. It is known that every connected bridgeless cubic graph contains a 2-factor (and a disjoint perfect matching). I'm ...
3
votes
0answers
115 views

Concentration of Stationary Distribution on Random Directed Graphs

We consider a random directed graph with fixed out-degree $d$. Each vertex chooses $d$ neighbors with replacement, uniformly and independently. Self-loops and multiple arcs are allowed in this model. ...
3
votes
0answers
284 views

Generating random graphs using the preferential attachment model with degree bounds

I am interested to know the structure of random graphs generated by the preferential attachment model with degree bounds. Specifically, when a vertex is chosen with a probability proportional to its ...
3
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 ...

1 2 3 4 5 7