Jun
26
comment How expensive may it be to destroy all long s-t paths in a DAG?
Sorry, I misunderstood the question. Thanks for the other reference.
Jun
25
comment How expensive may it be to destroy all long s-t paths in a DAG?
Length bounded flows and cuts are closely related to the questions you ask. I recommend looking at the thesis of Baier. ftp.math.tu-berlin.de/pub/Preprints/combi/…
Jun
18
comment Reservoir sampling of distinct values
Papers on $\ell_0$ sampling, namely sampling distinct elements are what you may be looking for. Here is one paper: arxiv.org/abs/1012.4889
Jun
9
comment Structure of graphs that exclude a perfect matching on four vertices as an induced graph
Want to add here an important property of the $2K_2$-free graphs, namely that the number of maximal independent sets in such graphs is polynomial in the number of vertices. In fact for any fixed $t$ $tK_2$-free graphs have a polynomial number of maximal independent sets. See following ref for more information. "Complexity results on graphs with few cliques." Discrete Mathematics and Theoretical Computer Science 9.1 (2007): 127-135.
Jun
8
awarded Enlightened
Jun
7
awarded Nice Question
Jun
5
awarded Scholar
Jun
5
comment Structure of graphs that exclude a perfect matching on four vertices as an induced graph
Thanks David. I predicted that you would answer it :).
Jun
5
accepted Structure of graphs that exclude a perfect matching on four vertices as an induced graph
Jun
5
awarded Student
Jun
5
asked Structure of graphs that exclude a perfect matching on four vertices as an induced graph
May
20
answered Multidimensional knapsack STRONGLY NP-complete
May
19
comment Approximate distance preserving sparse graph representation that are not necessarily subgraphs
Julia Chuzhoy has a paper on sparsifiers that exploit the fact that Steiner nodes can help. See arxiv.org/abs/1204.2844
May
19
comment Multidimensional knapsack STRONGLY NP-complete
Multidimensional knapsack is essentially the same as what are called packing integer programs (PIPs) which captures max independent set as a special case, as you observe.
May
18
comment Set cover approximation ratio as a function of m (number of sets)
See this note by Jelani Nelson. eccc.hpi-web.de/eccc-reports/2007/TR07-105/revisn01.pdf
May
5
awarded Civic Duty
May
5
comment Complexity of max problem
What is known in terms of upper bounds for approximation?
Apr
27
awarded Revival
Apr
25
answered What is the relationship between $\mathsf{APX}$ and $\mathsf{MaxSNP}$ classes?
Apr
6
comment How does Camerini's algorithm for minimum-bottleneck-spanning-tree run in linear time?
Isn't this a home work problem in my course?
1 2 3 4 5