Questions tagged [bounded-degree]
The bounded-degree tag has no usage guidance.
17
questions
1
vote
0
answers
43
views
Maximum degree of the Sum of Squares certificate of a non-negative degree d polynomial on the boolean hypercube
Let $f: \{0, 1\}^n \rightarrow \mathbb R$ be a polynomial on the boolean hypercube. If $f$ is non-negative $(f \geq 0)$ i.e. $f(x) \geq 0, \forall x \in \{0, 1\}^n$ then $f$ always has a degree $2n$ ...
- 111
4
votes
2
answers
194
views
NP-hardness: (planar) directed feedback vertex set problem with bounded degree
My question is the directed version of this one. (I know the results and proofs about feedback vertex set in undirected graphs or undirected planar graphs; so I am concern about the directed feedback ...
- 421
11
votes
0
answers
161
views
Complexity of $(\Delta-1)$-coloring graphs of maximum degree $\Delta$
Suppose we have a graph $G$ with maximum degree $\Delta$. Deciding if $G$ can be colored with $\Delta$ colors is easy: Brooks' theorem says that this is always possible, unless $G$ is a clique or an ...
- 3,416
12
votes
1
answer
2k
views
Is the 3-coloring problem NP-hard on graphs of maximal degree 3?
Consider the 3-coloring problem: given an undirected graph $G = (V, E)$, decide if there is a 3-coloring of $G$, i.e., a function $f$ from $G$ to $\{1, 2, 3\}$ such that there is no edge $\{u, v\}$ in ...
- 8,896
1
vote
0
answers
117
views
Complexity of counting 3-colourings of planar bounded degree graphs
The following are known:
It is #P-complete to count the number of 3-colourings of a planar graph (with respect to randomized reductions) [1].
For all $d\geq 3$, it is #P-complete to count the number ...
- 1,723
2
votes
0
answers
54
views
The number of rooted ordered trees of max-out degree $k$
An ordered tree (also known as ordinal tree and plane tree) is a rooted tree in which the children of each node are ordered. It is known that the number of the ordered tree with $n$ edges is the $n$'...
2
votes
0
answers
150
views
Sensitivity and Low-Degree Approximation under Non-Uniform Distribution
I am searching for generalizations of analysis of Boolean functions when the input strings are distributed according to a general non-uniform distribution, possibly with arbitrary dependencies between ...
- 21
1
vote
0
answers
61
views
relations between the degrees of a boolean function and its absolute function
Given a boolean function $f:\{0,1\}^n\rightarrow\mathbb{R}$ of degree $d$, is there any upper bound in terms of $d$ on the degree of the function $|f|$, where $|f|(x)=|f(x)|$. Here the degree of $f$ ...
- 11
10
votes
2
answers
365
views
Finding subgraphs with high treewidth and constant degree
I am given a graph $G$ with treewidth $k$ and arbitrary degree, and I would like to find a subgraph $H$ of $G$ (not necessarily an induced subgraph) such that $H$ has constant degree and its treewidth ...
- 8,896
7
votes
0
answers
229
views
Bias of a random boolean low degree polynomial
What is the bias of a random Boolean function that can be represented as a low degree polynomial over the reals, i.e. has low Fourier degree?
More specifically, is it true that if we take a uniformly ...
- 1,907
6
votes
1
answer
444
views
Degree restriction for polynomials in $\mathsf{VP}$
why do we need the restriction on the degree for a polynomial to be in VP due to which $(\prod_{i=0}^{n} x_i)^{2^n}$ $\notin$ VP even though it has a poly-size circuit?
- 327
22
votes
1
answer
466
views
Random functions of low degree as a real polynomial
Is there a (reasonable) way to sample a uniformly random boolean function $f:\{0,1\}^n \to \{0,1\}$ whose degree as a real polynomial is at most $d$?
EDIT: Nisan and Szegedy have shown that a ...
- 1,907
13
votes
4
answers
2k
views
hardness of approximating the chromatic number in graphs with bounded degree
I am looking for hardness results on vertex coloring of graphs with bounded degree.
Given a graph $G(V,E)$, we know that for any $\epsilon>0$, it's hard to approximate $\chi(G)$ within a factor ...
- 271
3
votes
1
answer
187
views
bounded outdegree bipartite spanners
Given an undirected graph $G = (V,E)$ and an integer $k > 0$, our objective is to find a subgraph $G' = (V ,E')$ where $E' \subseteq E$ such that $G'$ has the three following properties :
$G'$ ...
- 644
21
votes
2
answers
1k
views
Is feedback vertex set problem solvable in polynomial time for 3-degree bounded graphs?
Feedback Vertex Set (FVS) is NP-complete for general graphs. It is known to be NP-complete for degree-$8$ bounded graphs due to a reduction from vertex cover.
The Wikipedia article says that it is ...
- 368
0
votes
2
answers
269
views
Complexity of finding if a degree bounded graph H is a subgraph of an unbounded graph G
You are given two graphs G and H , and want to know if H is a subgraph of G.
You know that H has a max vertex degree K (constant integer).
What can you say about the complexity of this?
I know that ...
- 143
10
votes
1
answer
475
views
Hardness of approximating fractional chromatic number on bounded degree graphs
Is it apx-hard to approximate fractional chromatic number on bounded degree graphs?
- 1,574